Overall dichotomy, a non data structure solution to data structure problems.
A very classic problem - the interval static number \ (k \) is small, and its solutions are also diverse.
For each query \ ((l,r,k) \), consider a dichotomous answer. Let the value of the current dichotomy be \ (mid \), and we find the number \ (x \) of the number less than or equal to \ (mid \) in the interval \ ([l,r] \). If \ (x\ge k \), it proves that the answer is less than or equal to \ (mid \); Otherwise, the answer is greater than \ (mid \). However, the total time complexity is \ (O(nm\log SIZE) \), which is unbearable. (\ (SIZE \) indicates value range)
Note that for each query, our binary \ (mid \) is the same, so can we put all queries together?
Specifically, we perform the following processes:
- Take all inquiries offline;
- For the binary answer \ (mid \), set all numbers less than or equal to \ (mid \) in the sequence \ (a \) to \ (1 \);
- Use the tree array to count the number less than or equal to \ (mid \) in the \ (i \) query interval, so as to determine the relationship between the answer of this query and the size of \ (mid \);
- Recursively solve all queries with answers less than or equal to \ (mid \);
- Recursively solve all queries with answers greater than \ (mid \). (in this way, the original problem is divided into two smaller subproblems, which can continue recursion)
For convenience, we can regard the number of \ (I \) in the sequence as a modification operation. If the modified number, i.e. \ (a_i\le mid \), this operation is divided into the set of queries with answers less than or equal to \ (mid \); Otherwise, row into the set of queries with answers greater than \ (mid \).
It should be noted that memset cannot be used to reset the tree array. All modification operations should be cancelled one by one, otherwise the complexity will explode.
#include<bits/stdc++.h>
using namespace std;
int n, m;
int a[200005];
struct node {int p, x, y, k, id;} q[400005], lq[400005], rq[400005];
int ans[200005];
int sum[200005];
inline int read() {
int x = 0, f = 1; char c = getchar();
while (!isdigit(c)) {if (c == '-') f = -1; c = getchar();}
while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
return f == 1 ? x : -x;
}
inline void update(int x, int val) {
for (; x <= n; x += x & -x)
sum[x] += val;
}
inline int query(int x) {
int res = 0;
for (; x; x -= x & -x)
res += sum[x];
return res;
}
inline void solve(int l, int r, int st, int ed) {//l. R represents the range of the answer, st and ED represent the range of the query
if (st > ed) return;
if (l == r) {
for (int i = st; i <= ed; ++i)
if (q[i].p == 2) ans[q[i].id] = l;
return;
}
int mid = l + r >> 1, cnt1 = 0, cnt2 = 0;
//lq stores all queries with answers < = mid, and rq stores queries with answers > mid
for (int i = st; i <= ed; ++i) {
if (q[i].p == 1) {//Modify operation
if (q[i].y <= mid) update(q[i].x, 1), lq[++cnt1] = q[i];
else rq[++cnt2] = q[i];
} else {//Query operation
int x = query(q[i].y) - query(q[i].x - 1);
if (x >= q[i].k) lq[++cnt1] = q[i];
else q[i].k -= x, rq[++cnt2] = q[i];
//If the answer to a query is greater than mid, you are actually looking for the k-x decimal after division
}
}
for (int i = st; i <= ed; ++i)
if (q[i].p == 1 && q[i].y <= mid) update(q[i].x, -1);//Undo all modifications
for (int i = 1; i <= cnt1; ++i) q[i + st - 1] = lq[i];
for (int i = 1; i <= cnt2; ++i) q[i + st + cnt1 - 1] = rq[i];//copy the two groups of queries back to the original array to prevent space explosion
solve(l, mid, st, st + cnt1 - 1); solve(mid + 1, r, st + cnt1, ed);//Recursive solution
}
int main() {
n = read(); m = read();
for (int i = 1; i <= n; i++)
q[i] = (node){1, i, read(), 0, 0};
for (int i = 1; i <= m; i++)
q[i + n] = (node){2, read(), read(), read(), i};//Take the inquiry offline
solve(-1e9, 1e9, 1, n + m);
for (int i = 1; i <= m; i++)
printf("%d\n", ans[i]);
return 0;
}
To analyze the time complexity of a wave. Each query will be recursively \ (\ log SIZE \) layer, and each recursion of an operation will be updated \ (\ log n \) in the tree array. After modification, we have a total of \ (n+m \) operations, so the total time complexity is \ (O((n+m)\log n\log SIZE) \).
Incidentally, the immortal practice of \ (O(n\log n) \): arrange all modification operations in order according to \ (a_i \); Divide all queries \ ([l,r] \) into \ ([1,l-1] \) and \ ([1,r] \), and then arrange the disassembled intervals in order according to the right endpoint. Therefore, when we find out how many numbers in \ ([l,r] \) are less than or equal to \ (mid \), we only need to sweep a pointer. This completes a single \ (\ log \). I won't give you the code. You can see it in more detail This blog.
Compared with the previous question, it just changes from static to dynamic. However, if we modify it directly according to the meaning of the question, we will need to discuss whether the number is greater than \ (mid \) in the original and greater than \ (mid \) after modification, which increases the code length and is easy to write and hang. Therefore, we need to treat one modification as two operations, that is, we remove a number with a value of \ (a_x \) from the position \ (x \) and increase a number with a value of \ (y \). So we don't need to discuss it by situation.
P.S.: when reading the modification operation, you must assign \ (a_x \) to \ (y \) and correctly maintain the \ (a \) sequence, otherwise only \ (5 \) points - this is the lesson of blood!
#include<bits/stdc++.h>
using namespace std;
int n, m;
int t, cnt;
int a[200005];
struct node {int p, x, y, k, id;} q[400005], lq[400005], rq[400005];
int ans[200005];
int sum[200005];
inline int read() {
int x = 0, f = 1; char c = getchar();
while (!isdigit(c)) {if (c == '-') f = -1; c = getchar();}
while (isdigit(c)) {x = (x << 3) + (x << 1) + (c ^ 48); c = getchar();}
return f == 1 ? x : -x;
}
inline void update(int x, int val) {
for (; x <= n; x += x & -x)
sum[x] += val;
}
inline int query(int x) {
int res = 0;
for (; x; x -= x & -x)
res += sum[x];
return res;
}
inline void solve(int l, int r, int st, int ed) {
if (st > ed) return;
if (l == r) {
for (int i = st; i <= ed; ++i)
if (q[i].p == 1) ans[q[i].id] = l;
return;
}
int mid = l + r >> 1, cnt1 = 0, cnt2 = 0;
for (int i = st; i <= ed; ++i) {
if (q[i].p == 0) {
if (q[i].y <= mid) update(q[i].x, q[i].k), lq[++cnt1] = q[i];
else rq[++cnt2] = q[i];
} else {
int x = query(q[i].y) - query(q[i].x - 1);
if (x >= q[i].k) lq[++cnt1] = q[i];
else q[i].k -= x, rq[++cnt2] = q[i];
}
}
for (int i = st; i <= ed; ++i)
if (q[i].p == 0 && q[i].y <= mid) update(q[i].x, -q[i].k);
for (int i = 1; i <= cnt1; ++i) q[i + st - 1] = lq[i];
for (int i = 1; i <= cnt2; ++i) q[i + st + cnt1 - 1] = rq[i];
solve(l, mid, st, st + cnt1 - 1); solve(mid + 1, r, st + cnt1, ed);
}//The same method
int main() {
n = read(); m = read();
for (int i = 1; i <= n; ++i) {
a[i] = read();
q[++t] = (node){0, i, a[i], 1, 0};
}
for (int i = 1; i <= m; ++i) {
char c; int x, y, k; cin >> c;
if (c == 'Q') {
x = read(); y = read(); k = read();
q[++t] = (node){1, x, y, k, ++cnt};
} else {
x = read(); y = read();
q[++t] = (node){0, x, a[x], -1, 0};
q[++t] = (node){0, x, y, 1, 0};//Divide the modification into two operations
//The k in the structure indicates whether this is deleted or added
a[x] = y;//A very important line, I always forget
}
}//All operations must be stored in the array in chronological order
solve(-1e9, 1e9, 1, t);
for (int i = 1; i <= cnt; ++i)
printf("%d\n", ans[i]);
return 0;
}
Compared with nested trees, the theoretical complexity of overall dichotomy has changed from \ (O((n+m)\log^2n) \) to \ (O((n+m)\log n\log SIZE) \), but look at the actual effect:
| algorithm | Segment tree set balance tree | Overall dichotomy |
|---|---|---|
| time | \(23.23s\) | \(2.06s\) |
| space | \(88.13MB\) | \(21.09MB\) |
| Code length | \(2.77KB\) | \(1.90KB\) |
It can be found that the overall dichotomy has hanged the tree from any aspect. I haven't written the chairman tree of the tree array, but judging from the submission records of others, it should not be able to run the whole two points.
Several exercises:
Next is the comprehensive application of overall dichotomy, which can not only do interval Kth problems.
This problem It's beginning to deform
We can still make an overall dichotomy to see whether enough meteorites have been collected in the (i \) country after the \ ([l,mid] \) meteorite rain, so as to determine the relationship between the answer and the size of \ (mid \).
This problem also needs to be judged to have no solution. We don't need to spend more energy on special judgment. We can artificially add the \ (k+1 \) meteorite rain. In this way, the unsolved query will recurs to the right in two minutes, and the answer will become \ (k+1 \), which is easy to judge.
#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
int n, m, k;
vector<int> o[300005];
struct option {int l, r, k;} a[300005];
struct node {int p, k;} q[300005], lq[300005], rq[300005];
int sum[300005], ans[300005];
int lowbit(int x) {return x & -x;}
void update(int x, int val) {
for (; x <= m; x += lowbit(x))
sum[x] += val;
}
int query(int x) {
int res = 0;
for (; x; x -= lowbit(x)) res += sum[x];
return res;
}
void solve(int l, int r, int st, int ed) {
if (st > ed) return;
if (l == r) {
for (int i = st; i <= ed; i++)
ans[q[i].p] = l;
return;
}
int mid = l + r >> 1, cnt1 = 0, cnt2 = 0;
for (int i = l; i <= mid; i++)
if (a[i].l <= a[i].r) update(a[i].l, a[i].k), update(a[i].r + 1, -a[i].k);
else update(a[i].l, a[i].k), update(1, a[i].k), update(a[i].r + 1, -a[i].k);
for (int i = st; i <= ed; i++) {
int s = 0;
for (int j = 0; j < o[q[i].p].size(); j++)
s += query(o[q[i].p][j]);
if (q[i].k <= s) lq[++cnt1] = q[i];
else q[i].k -= s, rq[++cnt2] = q[i];
}
for (int i = l; i <= mid; i++)
if (a[i].l <= a[i].r) update(a[i].l, -a[i].k), update(a[i].r + 1, a[i].k);
else update(a[i].l, -a[i].k), update(1, -a[i].k), update(a[i].r + 1, a[i].k);
for (int i = 1; i <= cnt1; i++) q[st + i - 1] = lq[i];
for (int i = 1; i <= cnt2; i++) q[st + cnt1 + i - 1] = rq[i];
solve(l, mid, st, st + cnt1 - 1); solve(mid + 1, r, st + cnt1, ed);
}
signed main() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int x; cin >> x;
o[x].push_back(i);
}
for (int i = 1; i <= n; i++)
cin >> q[i].k, q[i].p = i;
cin >> k;
for (int i = 1; i <= k; i++)
cin >> a[i].l >> a[i].r >> a[i].k;
a[k + 1] = (option){1, m, 0};//In order to judge that there is no solution, add the k+1 meteorite rain
solve(1, k + 1, 1, n);
for (int i = 1; i <= n; i++)
if (ans[i] == k + 1) cout << "NIE" << endl;
else cout << ans[i] << endl;
return 0;
}
Several exercises:
- P7424 [thupc217] shooting every day
- P4602 [CTSC2018] mixed juice
- P3242 [HNOI2015] connected to fruit
Finally, apply Xu Haoran's paper.
Problems that can be solved by overall dichotomy need to meet the following properties:
- The answer to the question is dichotomous
- The contribution of modification to the judgment answer is independent of each other, and the modification does not affect the effect of each other
- If the modification contributes to the decision answer, the contribution is a determined value independent of the decision criteria
- Contribution satisfies commutative law, associative law, additive
- Offline algorithms are allowed
period