Description

维护一个W*W的矩阵，初始值均为S.每次操作可以增加某格子的权值,或询问某子矩阵的总权值.修改操作数M<=160000,询问数Q<=10000,W<=2000000.
Input

第一行两个整数,S,W;其中S为矩阵初始值;W为矩阵大小

接下来每行为一下三种输入之一(不包含引号):

“1 x y a”

“2 x1 y1 x2 y2”

“3”

输入1:你需要把(x,y)(第x行第y列)的格子权值增加a

输入2:你需要求出以左下角为(x1,y1),右上角为(x2,y2)的矩阵内所有格子的权值和,并输出

输入3:表示输入结束
Output

对于每个输入2,输出一行,即输入2的答案
Sample Input
0 4

1 2 3 3

2 1 1 3 3

1 2 2 2

2 2 2 3 4

3
Sample Output
3

5

解题方法： 给个别人的链接
初学CDQ花了快1天理解这个原理，再推荐一位大牛写的关于CDQ分治的总结: 见这里 初级CDQ大概理解了，不过CDQ套CDQ，以及高维偏序还不理解，强撸题吧！注意这个题数组开小不是RE,是WA，神坑。

//bzoj 1176
//1维排序，二维分治，3维BIT
#include <bits/stdc++.h>
using namespace std;
const int maxq = 200010;
const int maxn = 500010;
int S, W, ans[maxq];
inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while(!(ch>='0'&&ch<='9')){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+(ch-'0');ch=getchar();}
    return x*f;
}
namespace BIT{
    int tree[2000010];
    inline int lowbit(int x) {return x & -x;}
    inline void update(int x, int y) {for(int i = x; i <= W; i+=lowbit(i)) tree[i] += y;}
    inline int query(int x) {int res = 0; for(int i = x; i; i -= lowbit(i)) res += tree[i]; return res;}
}
using namespace BIT;
struct Q{
    int id, x, y, opt, del, ID;
    Q(){}
    Q(int id, int x, int y, int opt, int del, int ID) : id(id), x(x), y(y), opt(opt), del(del), ID(ID) {}
    bool operator < (const Q &rhs) const{
        return (x == rhs.x && y == rhs.y) ? opt < rhs.opt : ((x == rhs.x) ? y < rhs.y : x < rhs.x);
    }
}q[maxq*4], tmp[maxq*4];
void CDQ(int l, int r){
    if(l == r) return ;
    int mid = (l+r)>>1, z1 = l, z2 = mid + 1;
    for(int i = l; i <= r; i++){
        if(q[i].opt == 1 && q[i].id <= mid) update(q[i].y, q[i].del);
        if(q[i].opt == 2 && q[i].id > mid) ans[q[i].ID] += query(q[i].y) * q[i].del;
    }
    for(int i = l; i <= r; i++) if(q[i].opt == 1 && q[i].id <= mid) update(q[i].y, -q[i].del);
    for(int i = l; i <= r; i++) if(q[i].id <= mid) tmp[z1++] = q[i]; else tmp[z2++] = q[i];
    for(int i = l; i <= r; i++) q[i] = tmp[i];
    CDQ(l, mid);
    CDQ(mid + 1, r);
}
int t, z;
void presolve(int x1, int y1, int x2, int y2){ //操作拆分 sum(x2,y2)+sum(x1-1,y1-1)+sum(x1-1,y2)-sum(x2,y1-1)
    z++;
    t++; q[t].id = t; q[t].ID = z; q[t].x = x1 - 1; q[t].y = y1 - 1; q[t].del = 1; q[t].opt = 2;
    t++; q[t].id = t; q[t].ID = z; q[t].x = x2; q[t].y = y2; q[t].del = 1; q[t].opt = 2;
    t++; q[t].id = t; q[t].ID = z; q[t].x = x1 - 1; q[t].y = y2; q[t].del = -1; q[t].opt = 2;
    t++; q[t].id = t; q[t].ID = z; q[t].x = x2; q[t].y = y1 - 1; q[t].del = -1; q[t].opt = 2;
}
int main(){
    //scanf("%d%d", &S, &W);
    S = read(); W = read();
    t = z = 0;
    while(1){
        int cmd;
        //scanf("%d", &cmd);
        cmd = read();
        if(cmd == 3) break;
        if(cmd == 1){t++; //scanf("%d%d%d", &q[t].x, &q[t].y, &q[t].del);
        q[t].x = read(), q[t].y = read(), q[t].del = read();
        q[t].id = t; q[t].opt = 1; }
        if(cmd == 2){
            int x1, x2, y1, y2;
            //scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
            x1 = read(), y1 = read(), x2 = read(), y2 = read();
            presolve(x1, y1, x2, y2);
        }
    }
    sort(q + 1, q + t + 1);
    CDQ(1, t);
    for(int i = 1; i <= z; i++) printf("%d\n", ans[i]);
    return 0;
}