Census
昨天看完刘汝佳的，用二维线段树写了。。。
然后刚学过整体二分，就拿来练一下，结果调了一晚上加一早上bug。。。
先是二维树状数组写崩了
emmm一直没发现他们两个是不等价的，，好菜啊=_=
改了之后还是一直RE，要是一直RE我大概也能猜到很可能是数组的问题，关键中间还莫名返回了几个WA，一头雾水...
最后发现还是数组开太小了=_=
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define LL long long 4 const int maxn = 520; 5 const int maxq = 350010; //数组开小了WA到死。。。。 500 × 500 + 40000 × 2 6 const int inf = 1<<30; 7 struct Qry{ 8 int x1, y1, x2, y2, v; 9 int id, type; 10 }q[maxq], q1[maxq], q2[maxq]; 11 12 struct BIT{ 13 int n; 14 int b[maxn][maxn]; 15 void init(int _n){ 16 n = _n; 17 memset(b, 0, sizeof(b)); 18 } 19 void add(int x, int y, int v){ 20 for(int i = x; i <= n; i += i & -i){ 21 for(int j = y; j <= n; j += j & -j){ 22 b[i][j] += v; 23 } 24 } 25 } 26 int sum(int x, int y){ 27 int res = 0; 28 for(int i = x; i; i -= i & -i){ 29 for(int j = y; j; j -= j & -j){ 30 res += b[i][j]; 31 } 32 } 33 return res; 34 } 35 int sum(int x1, int y1, int x2, int y2){ 36 return sum(x2, y2) - sum(x1 - 1, y2) - sum(x2, y1 - 1) + sum(x1 - 1, y1 - 1); 37 } 38 }bit; 39 int a[maxn][maxn], ans[maxq]; 40 void solve(int L, int R, LL l, LL r){ 41 if(L > R) return ; 42 if(l == r){ 43 for(int i = L; i <= R; i++){ 44 if(q[i].type == 2) ans[q[i].id] = l; 45 } 46 return ; 47 } 48 LL m = (l + r) >> 1; 49 int f = 0, g = 0; 50 for(int i = L; i <= R; i++){ 51 if(q[i].type == 1){ 52 if(q[i].v <= m) { 53 bit.add(q[i].x1, q[i].y1, q[i].id); 54 q1[f++] = q[i]; 55 }else q2[g++] = q[i]; 56 }else{ 57 int temp = bit.sum(q[i].x1, q[i].y1, q[i].x2, q[i].y2); 58 if(temp >= q[i].v) q1[f++] = q[i]; 59 else { 60 q[i].v -= temp; 61 q2[g++] = q[i]; 62 } 63 } 64 } 65 for(int i = 0; i < f; i++) if(q1[i].type == 1) bit.add(q1[i].x1, q1[i].y1, -q1[i].id); 66 memcpy(q + L, q1, f * sizeof(Qry)); 67 memcpy(q + L + f, q2, g * sizeof(Qry)); 68 solve(L, L + f - 1, l, m); 69 solve(L + f, R, m + 1, r); 70 } 71 72 int main(){ 73 int n; 74 //freopen("in.txt", "r", stdin); 75 //freopen("out1.txt", "w", stdout); 76 while(scanf("%d", &n) != EOF){ 77 bit.init(n); 78 int idx = 0, cnt = 0; 79 for(int i = 1; i <= n; i++){ 80 for(int j = 1; j <= n; j++){ 81 scanf("%d", &a[i][j]); 82 q[++idx] = Qry{i, j, 0, 0, a[i][j], 1, 1}; 83 } 84 } 85 int m; 86 scanf("%d",&m); 87 for(int i = 1; i <= m; i++){ 88 int x1, y1, x2, y2, v; 89 char op[4]; 90 scanf("%s", op); 91 if(op[0] == 'q'){ 92 scanf("%d %d %d %d", &x1, &y1, &x2, &y2); 93 q[++idx] = Qry{x1, y1, x2, y2, 1, ++cnt, 2}; 94 int temp = (x2 - x1 + 1) * (y2 - y1 + 1); 95 q[++idx] = Qry{x1, y1, x2, y2, temp, ++cnt, 2}; 96 }else{ 97 scanf("%d %d %d", &x1, &y1, &v); 98 q[++idx] = Qry{x1, y1, 0, 0, a[x1][y1], -1, 1}; 99 a[x1][y1] = v; 100 q[++idx] = Qry{x1, y1, 0, 0, v, 1, 1}; 101 } 102 } 103 solve(1, idx, 0, inf); 104 for(int i = 1; i <= cnt; i += 2){ 105 printf("%d %d ", ans[i + 1], ans[i]); 106 } 107 } 108 }
再贴个对拍生成的数据吧orz
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int MAXN = 1313; 4 const int mod = 1<<30; 5 int main(){ 6 freopen("in.txt", "w", stdout); 7 for(int k = 0; k < MAXN; k++){ 8 int n = rand() % 13 + 1; 9 cout<<n<<endl; 10 for(int i = 0; i < n; i++){ 11 for(int j = 0; j < n; j++){ 12 cout<<(rand() % mod) <<" "; 13 } 14 cout<<endl; 15 } 16 int m = 10; 17 cout<<m<<endl; 18 while(m--){ 19 int fg = rand() & 1; 20 if(fg){ 21 cout<<"q "; 22 int x1 = rand() % n + 1; 23 int y1 = rand() % n + 1; 24 int x2 = rand() % n + 1; 25 int y2 = rand() % n + 1; 26 if(x1 > x2) swap(x1, x2); 27 if(y1 > y2) swap(y1, y2); 28 printf("%d %d %d %d ", x1, y1, x2, y2); 29 }else{ 30 cout<<"c "; 31 int x1 = rand() % n + 1; 32 int y1 = rand() % n + 1; 33 int v = rand() % mod; 34 printf("%d %d %d ", x1, y1, v); 35 } 36 } 37 } 38 }