题目这么说的：

摩尔瓦多的移动电话公司摩基亚（Mokia）设计出了一种新的用户定位系统。和其他的定位系统一样，它能够迅速回答任何形如“用户C的位置在哪？”的问题，精确到毫米。但其真正高科技之处在于，它能够回答形如“给定区域内有多少名用户？”的问题。

在定位系统中，世界被认为是一个W×W的正方形区域，由1×1的方格组成。每个方格都有一个坐标(x,y)，1<=x,y<=W。坐标的编号从1开始。对于一个4×4的正方形，就有1<=x<=4,1<=y<=4（如图）：

请帮助Mokia公司编写一个程序来计算在某个矩形区域内有多少名用户。

有三种命令，意义如下：

0 W 初始化一个全零矩阵。本命令仅开始时出现一次。

1 x y A 向方格(x,y)中添加A个用户。A是正整数。

2 X1 Y1 X2 Y2 查询X1<=x<=X2，Y1<=y<=Y2所规定的矩形中的用户数量

3 无参数 结束程序。本命令仅结束时出现一次。

 

这篇题解写得挺详细的：。

。。然后感觉这题转化成二维前缀和的差分挺厉害的。

1 #include
     
        2 #include
      
         3 #include
       
          4 using namespace std;  5   6 long long tree[2000000<<2];  7 int N,x,y;  8 void update(int i,int j,int k){  9     if(i==j){ 10         tree[k]+=y; 11         return; 12     } 13     int mid=i+j>>1; 14     if(x<=mid) update(i,mid,k<<1); 15     else update(mid+1,j,k<<1|1); 16     tree[k]=tree[k<<1]+tree[k<<1|1]; 17 } 18 long long query(int i,int j,int k){ 19     if(x>y) return 0; 20     if(x<=i && j<=y){ 21         return tree[k]; 22     } 23     int mid=i+j>>1; 24     long long res=0; 25     if(x<=mid) res+=query(i,mid,k<<1); 26     if(y>mid) res+=query(mid+1,j,k<<1|1); 27     return res; 28 } 29  30 struct Query{ 31     int idx,type,anspos; 32     int x,y,A; 33     bool operator<(const Query &q) const { 34         return x
        
         =r) return; 42     int mid=l+r>>1,i=l,j=mid+1; 43     for(int k=l; k<=r; ++k){ 44         if(que[k].idx<=mid) tmp[i++]=que[k]; 45         else tmp[j++]=que[k]; 46     } 47     for(int k=l; k<=r; ++k){ 48         que[k]=tmp[k]; 49     } 50  51     for(i=mid+1,j=l; i<=r; ++i){ 52         if(que[i].type==1) continue; 53         for( ; j<=mid && que[j].x<=que[i].x; ++j){ 54             if(que[j].type==2) continue; 55             x=que[j].y; y=que[j].A; 56             update(1,N,1); 57         } 58         x=1; y=que[i].y; 59         ans[que[i].anspos]+=query(1,N,1)*que[i].A; 60     } 61  62     for(int i=l; i