維護一個 W*W 的矩陣，每次操作可以增加某格子的權值，或詢問某子矩陣的總權值。 修改操作數 M<=160000，詢問數 Q<=10000，W<=2000000。
。。。 cdq 分治 + 掃描線。
。強行離線。將二維樹狀數組降成一維。。。
http://www.lydsy.com/JudgeOnline/problem.php?id=1176
https://gist.github.com/lychees/d677c384dbe09fea8e02

//}/* .................................................................................................................................. */ const int N = int(2e5) + 9; int n; namespace BIT{ const int N = 2000009; typedef LL intt; intt C[N], n; void Add(int x, int d){ for (;x<=n;x+=low_bit(x)) C[x] += d; } intt Sum(int x){ intt res = 0; for (;x;x^=low_bit(x)) res += C[x]; return res; } intt Sum(int l, int r){ return Sum(r) - Sum(l-1); } } //using namespace BIT; struct Op{ int x1, y1, x2, y2, ty; LL d; void in(int _ty){ ty = _ty; if (ty == 1){ RD(x1, y1, d); } else if (ty == 2){ RD(x1, y1, x2, y2); d = 0; } } }; vector<Op> op; void cdq(int l, int r){ if (l + 1 == r){ } else{ int m = l + r >> 1; static PII Q[N]; int qn = 0; FOR(i, l, m) if (op[i].ty == 1) Q[qn++] = MP(op[i].x1, i); FOR(i, m, r) if (op[i].ty == 2){ Q[qn++] = MP(op[i].x1-1, i); Q[qn++] = MP(op[i].x2, i); } sort(Q, Q+qn); REP(i, qn){ int id = Q[i].se; if (op[id].ty == 2){ // Query if (Q[i].fi + 1 == op[id].x1){ // Left op[id].d -= BIT::Sum(op[id].y1, op[id].y2); } else{ // Right op[id].d += BIT::Sum(op[id].y1, op[id].y2); } } else{ BIT::Add(op[id].y1, op[id].d); } } REP(i, qn){ int id = Q[i].se; if (op[id].ty == 2){ // Query } else{ BIT::Add(op[id].y1, -op[id].d); } } cdq(l, m); cdq(m, r); } } int main(){ #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); #endif int init_value; RD(init_value, BIT::n); assert(init_value == 0); do{ int ty; RD(ty); if (ty == 3) break; Op t; t.in(ty); op.PB(t); } while (1); cdq(0, SZ(op)); ECH(it, op) if (it->ty == 2){ OT(it->d); } }