BZOJ 2683: 简单题

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 
  4 template <typename tn> void read (tn & a) {
  5     tn x = 0, f = 1; char c = getchar(); while (c < ‘0‘ || c > ‘9‘){ if (c == ‘-‘) f = -1; c = getchar(); }
  6     while (c >= ‘0‘ && c <= ‘9‘){ x = x * 10 + c - ‘0‘; c = getchar(); } a = (f == 1) ? x : -x;
  7 }
  8 
  9 const int MAXN = 510000;
 10 int t[MAXN];
 11 int n;
 12 struct xy {
 13     int x, y, a, id, op, t;
 14 }q[MAXN * 4], put[MAXN * 4];
 15 int qx, tx;
 16 int p[MAXN * 4], px, ans[MAXN * 4];
 17 bool cmp (const xy i, const xy j) { return (i.x == j.x) ? (i.t < j.t) : (i.x < j.x); }
 18 void add (int x, int d) { while (x <= n) { t[x] += d; x += x & (-x); } }
 19 int sum (int x) { int s = 0; while (x > 0) { s += t[x]; x -= x & (-x); } return s; }
 20 void solve (int left, int right) {
 21     if (left + 1 >= right) return;
 22     int mid = (left + right) / 2;
 23     int tx = 0;
 24     for (int i = left; i < right; ++i) {
 25         if (q[i].t < mid && q[i].op == 1) {
 26             add(q[i].y, q[i].a);
 27         }
 28         if (q[i].t >= mid && q[i].op == 2) {
 29             ans[q[i].id] += sum(q[i].y);
 30         }
 31     }
 32     for (int i = left; i < right; ++i) {
 33         if (q[i].t < mid && q[i].op == 1) add(q[i].y, -q[i].a);
 34     }
 35     int l1 = left - 1, l2 = mid - 1;
 36     for (int i = left; i < right; ++i) {
 37         if (q[i].t < mid) {
 38             put[++l1] = q[i];
 39         }
 40         else {
 41             put[++l2] = q[i];
 42         }
 43     }
 44     for (int i = left; i < right; ++i) q[i] = put[i];
 45     solve(left, mid);
 46     solve(mid, right);
 47 }
 48 
 49 int main() {
 50     read(n);
 51     ++n; 
 52     int id;
 53     read(id);
 54     while (id != 3) {
 55         if (id == 1) {
 56             int x, y, a;
 57             read(x); read(y); read(a);
 58             q[++qx].x = x + 1; q[qx].y = y + 1; q[qx].a = a;
 59             q[qx].op = 1; q[qx].id = qx; q[qx].t = ++tx;
 60         }
 61         else {
 62             int x_1, y_1, x_2, y_2;
 63             read(x_1);
 64             read(y_1);
 65             read(x_2);
 66             read(y_2);
 67             p[++px] = qx;
 68             q[++qx].x = x_1;
 69             q[qx].y = y_1;
 70             q[qx].id = qx;
 71             q[qx].op = 2;
 72             q[qx].t = ++tx;
 73             
 74             q[++qx].x = x_2 + 1;
 75             q[qx].y = y_1;
 76             q[qx].id = qx;
 77             q[qx].op = 2;
 78             q[qx].t = ++tx;
 79             
 80             q[++qx].x = x_1;
 81             q[qx].y = y_2 + 1;
 82             q[qx].id = qx;
 83             q[qx].op = 2;
 84             q[qx].t = ++tx;
 85             
 86             q[++qx].x = x_2 + 1;
 87             q[qx].y = y_2 + 1;
 88             q[qx].id = qx;
 89             q[qx].op = 2;            
 90             q[qx].t = ++tx;
 91             
 92         }
 93         read(id);
 94     }
 95     sort(q + 1, q + 1 + qx, cmp);
 96     solve(1, qx + 1);
 97     for (int i = 1; i <= px; ++i) {
 98         printf("%d\n", ans[p[i] + 1] - ans[p[i] + 2] - ans[p[i] + 3] + ans[p[i] + 4]);
 99     }
100     return 0;
101 }