维护一个 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);
}
}
