整体二分

把所有询问离线一起二分回答。

跟CDQ分治比较：

CDQ分治是按照中序遍历来解决，整体二分是从上往下。

推荐一个博客。

例题洛谷P2617 Dynamic Rankings

  1 #include <cstdio>
  2 #include <algorithm>
  3 #include <cstring>
  4 
  5 const int N = 100010;
  6 
  7 struct Node {
  8     int f, x, y, k, id;
  9     // f = 0  ask  [x, y]  k
 10     // f = 1  change  pos = x  val = y  sum += k
 11     Node(int F = 0, int X = 0, int Y = 0, int K = 0, int ID = 0) {
 12         f = F;
 13         x = X;
 14         y = Y;
 15         k = K;
 16         id = ID;
 17     }
 18 }node[N * 3], t1[N * 3], t2[N * 3];
 19 
 20 int ans[N], ta[N], a[N], n;
 21 char str[3];
 22 
 23 inline void add(int x, int v) {
 24     for(int i = x; i <= n; i += i & (-i)) {
 25         ta[i] += v;
 26     }
 27     return;
 28 }
 29 
 30 inline int getSum(int x) {
 31     int ans = 0;
 32     for(int i = x; i >= 1; i -= i & (-i)) {
 33         ans += ta[i];
 34     }
 35     return ans;
 36 }
 37 
 38 inline void div(int L, int R, int l, int r) {
 39     //printf("[%d %d]  [%d %d] 
", L, R, l, r);
 40     if(L > R || l > r) {
 41         return;
 42     }
 43     if(l == r) {
 44         for(int i = L; i <= R; i++) {
 45             if(node[i].f == 0) {
 46                 ans[node[i].id] = r;
 47             }
 48         }
 49         return;
 50     }
 51     int mid = (l + r) >> 1;
 52     int top1 = 0, top2 = 0;
 53     for(int i = L; i <= R; i++) {
 54         if(node[i].f == 0) { // ask
 55             int t = getSum(node[i].y) - getSum(node[i].x - 1);
 56             if(node[i].k <= t) {
 57                 t1[++top1] = node[i];
 58             }
 59             else {
 60                 node[i].k -= t;
 61                 t2[++top2] = node[i];
 62             }
 63         }
 64         else { // change
 65             if(node[i].y <= mid) {
 66                 add(node[i].x, node[i].k);
 67                 t1[++top1] = node[i];
 68             }
 69             else {
 70                 t2[++top2] = node[i];
 71             }
 72         }
 73     }
 74     for(int i = 1; i <= top1; i++) {
 75         if(t1[i].f) {
 76             add(t1[i].x, -t1[i].k);
 77         }
 78     }
 79     memcpy(node + L, t1 + 1, top1 * sizeof(Node));
 80     memcpy(node + L + top1, t2 + 1, top2 * sizeof(Node));
 81     div(L, L + top1 - 1, l, mid);
 82     div(L + top1, R, mid + 1, r);
 83     return;
 84 }
 85 
 86 int main() {
 87     int m, tot = 0;
 88     scanf("%d%d", &n, &m);
 89     memset(ans, 0x3f, sizeof(ans));
 90     int small = ans[0], large = -ans[0];
 91     for(int i = 1; i <= n; i++) {
 92         scanf("%d", &a[i]);
 93         node[++tot] = Node(1, i, a[i], 1, 0);
 94         small = std::min(small, a[i]);
 95         large = std::max(large, a[i]);
 96     }
 97     for(int i = 1, x, y, k; i <= m; i++) {
 98         scanf("%s", str);
 99         if(str[0] == 'Q') {
100             scanf("%d%d%d", &x, &y, &k);
101             node[++tot] = Node(0, x, y, k, i);
102         }
103         else {
104             scanf("%d%d", &x, &y);
105             node[++tot] = Node(1, x, a[x], -1, 0);
106             node[++tot] = Node(1, x, y, 1, i);
107             a[x] = y;
108             small = std::min(small, y);
109             large = std::max(large, y);
110         }
111     }
112     div(1, tot, small, large);
113     for(int i = 1; i <= m; i++) {
114         if(ans[i] != ans[0]) {
115             printf("%d
", ans[i]);
116         }
117     }
118     return 0;
119 }

AC代码

注意这里对原来的数视作一个插入。对修改视作删除 + 插入，跟CDQ一样。用完树状数组之后要还原也跟CDQ一样。

不用合并区间所以不用归并。注意操作数不是m。

[ZJOI2013]K大数查询

当单点修改变成区间放入一个数的时候，树套树T飞......整体二分就是把树状数组的操作变成区间加，区间求和。线段树即可。

区间覆盖标记的线段树写起来繁琐至极...要注意下传tag如果把覆盖标记覆盖了，那么还要把子节点的覆盖标记传到孙子上。

50000²爆int了...

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 
  5 typedef long long LL;
  6 const int N = 50010;
  7 
  8 struct Node {
  9     int f, x, y, id; // 0 ask 1 change
 10     LL v;
 11 }node[N], t1[N], t2[N];
 12 
 13 LL X[N];
 14 int ans[N], xx, n;
 15 int tag[N * 4], zero[N * 4];
 16 LL sum[N * 4];
 17 
 18 inline void pushdown(int l, int r, int o) {
 19     if(zero[o]) {
 20         zero[o << 1] = zero[o << 1 | 1] = 1;
 21         sum[o << 1] = sum[o << 1 | 1] = 0;
 22         tag[o << 1] = tag[o << 1 | 1] = 0;
 23         zero[o] = 0;
 24     }
 25     if(tag[o]) {
 26         int mid = (l + r) >> 1;
 27         //zero[o << 1] = zero[o << 1 | 1] = 0;
 28         int ls = o << 1, rs = o << 1 | 1;
 29         if(zero[ls]) {
 30             zero[ls] = 0;
 31             if(l < mid) {
 32                 zero[ls << 1] = zero[ls << 1 | 1] = 1;
 33                 sum[ls << 1] = sum[ls << 1 | 1] = 0;
 34                 tag[ls << 1] = tag[ls << 1 | 1] = 0;
 35             }
 36         }
 37         if(zero[rs]) {
 38             zero[rs] = 0;
 39             if(mid + 1 < r) {
 40                 zero[rs << 1] = zero[rs << 1 | 1] = 1;
 41                 sum[rs << 1] = sum[rs << 1 | 1] = 0;
 42                 tag[rs << 1] = tag[rs << 1 | 1] = 0;
 43             }
 44         }
 45         tag[o << 1] += tag[o];
 46         tag[o << 1 | 1] += tag[o];
 47         sum[o << 1] += 1ll * (mid - l + 1) * tag[o];
 48         sum[o << 1 | 1] += 1ll * (r - mid) * tag[o];
 49         tag[o] = 0;
 50     }
 51     return;
 52 }
 53 
 54 void add(int L, int R, int l, int r, int o) {
 55     //printf("add %d %d %d %d 
", L, R, l, r);
 56     if(L <= l && r <= R) {
 57         if(zero[o]) {
 58             zero[o] = 0;
 59             if(l < r) {
 60                 zero[o << 1] = zero[o << 1 | 1] = 1;
 61                 sum[o << 1] = sum[o << 1 | 1] = 0;
 62                 tag[o << 1] = tag[o << 1 | 1] = 0;
 63             }
 64         }
 65         tag[o]++;
 66         sum[o] += (r - l + 1);
 67         //printf("sum %d += %d = %d 
", o, (r - l + 1), sum[o]);
 68         return;
 69     }
 70     pushdown(l, r, o);
 71     int mid = (l + r) >> 1;
 72     if(L <= mid) {
 73         add(L, R, l, mid, o << 1);
 74     }
 75     if(mid < R) {
 76         add(L, R, mid + 1, r, o << 1 | 1);
 77     }
 78     sum[o] = sum[o << 1] + sum[o << 1 | 1];
 79     return;
 80 }
 81 
 82 LL ask(int L, int R, int l, int r, int o) {
 83     //printf("ASK : %d %d %d %d 
", L, R, l, r);
 84     if(L <= l && r <= R) {
 85         //printf("return sum %d = %d 
", o, sum[o]);
 86         return sum[o];
 87     }
 88     pushdown(l, r, o);
 89     int mid = (l + r) >> 1;
 90     LL ans = 0;
 91     if(L <= mid) {
 92         ans += ask(L, R, l, mid, o << 1);
 93     }
 94     if(mid < R) {
 95         ans += ask(L, R, mid + 1, r, o << 1 | 1);
 96     }
 97     return ans;
 98 }
 99 
100 inline void solve(int L, int R, int l, int r) {
101     //printf("solve : %d %d  %d %d
", L, R, l, r);
102     if(L > R) {
103         return;
104     }
105     if(l == r) {
106         for(int i = L; i <= R; i++) {
107             if(node[i].f == 2) {
108                 ans[node[i].id] = r;
109             }
110         }
111         return;
112     }
113     int mid = (l + r) >> 1, top1 = 0, top2 = 0;
114     for(int i = L; i <= R; i++) {
115         if(node[i].f == 2) { // ask
116             LL t = ask(node[i].x, node[i].y, 1, n, 1);
117             //printf("id = %d  t = %d 
", node[i].id, t);
118             if(node[i].v <= t) {
119                 t2[++top2] = node[i];
120             }
121             else {
122                 node[i].v -= t;
123                 t1[++top1] = node[i];
124             }
125         }
126         else {
127             if(node[i].v > mid) {
128                 add(node[i].x, node[i].y, 1, n, 1);
129                 t2[++top2] = node[i];
130             }
131             else {
132                 t1[++top1] = node[i];
133             }
134         }
135     }
136     zero[1] = 1; sum[1] = tag[1] = 0;
137     memcpy(node + L, t1 + 1, top1 * sizeof(Node));
138     memcpy(node + L + top1, t2 + 1, top2 * sizeof(Node));
139     solve(L, L + top1 - 1, l, mid);
140     solve(L + top1, R, mid + 1, r);
141     return;
142 }
143 
144 int main() {
145 
146     int m;
147     scanf("%d%d", &n, &m);
148     memset(ans, -1, sizeof(ans));
149     for(int i = 1; i <= m; i++) {
150         scanf("%d%d%d%lld", &node[i].f, &node[i].x, &node[i].y, &node[i].v);
151         node[i].id = i;
152         if(node[i].f == 1) {
153             X[++xx] = node[i].v;
154         }
155     }
156     std::sort(X + 1, X + xx + 1);
157     xx = std::unique(X + 1, X + xx + 1) - X - 1;
158     for(int i = 1; i <= m; i++) {
159         if(node[i].f == 1) {
160             node[i].v = std::lower_bound(X + 1, X + xx + 1, node[i].v) - X;
161         }
162     }
163     solve(1, m, 1, xx);
164     for(int i = 1; i <= m; i++) {
165         if(ans[i] != ans[0]) {
166             printf("%lld
", X[ans[i]]);
167         }
168     }
169     return 0;
170 }

AC代码

洛谷P1527 矩阵乘法

二维平面的时候用二维树状数组即可。

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 
  5 const int N = 510, M = 60010;
  6 
  7 struct Node {
  8     int f, x, y, xx, yy, k, id; /// 0 ask 1 change
  9     Node(int F = 0, int X = 0, int Y = 0, int XX = 0, int YY = 0, int K = 0, int ID = 0) {
 10         f = F;
 11         x = X;
 12         y = Y;
 13         k = K;
 14         xx = XX;
 15         yy = YY;
 16         id = ID;
 17     }
 18 }node[N * N + M], t1[N * N + M], t2[N * N + M]; int tot;
 19 
 20 int X[N * N], xx, a[N][N], n;
 21 int ta[N][N], ans[M];
 22 
 23 inline void add(int x, int y, int v) {
 24     for(int i = x; i <= n; i += i & (-i)) {
 25         for(int j = y; j <= n; j += j & (-j)) {
 26             ta[i][j] += v;
 27         }
 28     }
 29     return;
 30 }
 31 
 32 inline int ask(int x, int y) {
 33     int ans = 0;
 34     for(int i = x; i >= 1; i -= i & (-i)) {
 35         for(int j = y; j >= 1; j -= j & (-j)) {
 36             ans += ta[i][j];
 37         }
 38     }
 39     return ans;
 40 }
 41 
 42 void solve(int L, int R, int l, int r) {
 43     if(L > R) {
 44         return;
 45     }
 46     if(l == r) {
 47         for(int i = L; i <= R; i++) {
 48             if(node[i].f == 0) {
 49                 ans[node[i].id] = r;
 50             }
 51         }
 52         return;
 53     }
 54     int mid = (l + r) >> 1, top1 = 0, top2 = 0;
 55     for(int i = L; i <= R; i++) {
 56         if(node[i].f == 0) { // ask
 57             int x = node[i].x, y = node[i].y;
 58             int xx = node[i].xx, yy = node[i].yy;
 59             int t = ask(xx, yy) - ask(xx, y - 1) - ask(x - 1, yy) + ask(x - 1, y - 1);
 60             if(node[i].k <= t) {
 61                 t1[++top1] = node[i];
 62             }
 63             else {
 64                 node[i].k -= t;
 65                 t2[++top2] = node[i];
 66             }
 67         }
 68         else { // change
 69             if(node[i].k <= mid) {
 70                 add(node[i].x, node[i].y, 1);
 71                 t1[++top1] = node[i];
 72             }
 73             else {
 74                 t2[++top2] = node[i];
 75             }
 76         }
 77     }
 78     for(int i = 1; i <= top1; i++) {
 79         if(t1[i].f) {
 80             add(t1[i].x, t1[i].y, -1);
 81         }
 82     }
 83     memcpy(node + L, t1 + 1, top1 * sizeof(Node));
 84     memcpy(node + L + top1, t2 + 1, top2 * sizeof(Node));
 85     solve(L, L + top1 - 1, l, mid);
 86     solve(L + top1, R, mid + 1, r);
 87     return;
 88 }
 89 
 90 int main() {
 91     int q;
 92     scanf("%d%d", &n, &q);
 93     memset(ans, 0x7f, sizeof(ans));
 94     for(int i = 1; i <= n; i++) {
 95         for(int j = 1; j <= n; j++) {
 96             scanf("%d", &a[i][j]);
 97             node[++tot] = Node(1, i, j, 0, 0, a[i][j], 0);
 98             X[tot] = a[i][j];
 99         }
100     }
101     std::sort(X + 1, X + tot + 1);
102     int xx = std::unique(X + 1, X + tot + 1) - X - 1;
103     for(int i = 1; i <= tot; i++) {
104         node[i].k = std::lower_bound(X + 1, X + xx + 1, node[i].k) - X;
105     }
106     for(int i = 1; i <= q; i++) {
107         ++tot;
108         scanf("%d%d%d%d%d", &node[tot].x, &node[tot].y, &node[tot].xx, &node[tot].yy, &node[tot].k);
109         node[tot].id = i;
110     }
111     solve(1, tot, 1, xx);
112     for(int i = 1; i <= q; i++) {
113         if(ans[i] != ans[0]) {
114             printf("%d
", X[ans[i]]);
115         }
116     }
117     return 0;
118 }

AC代码