【题意】n*n的矩阵，初始值为0（题面有误），m次操作，增加一个格子的权值，或查询子矩阵和。n<=2*10^6。（m应该较题面所述偏大）。

【算法】CDQ分治（算法知识见）

【题解】三维偏序，一维排序扫描线（x坐标），一维树状数组前缀和（y坐标），一维CDQ分治（操作时间）。

每个矩阵查询差分成四个单点查询。

CDQ分治的过程：①左边影响右边，②消除影响，③分成左右两部分，最后递归进行。

#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;int read(){    char c;int s=0,t=1;    while(!isdigit(c=getchar()))if(c=='-')t=-1;    do{s=s*10+c-'0';}while(isdigit(c=getchar()));    return s*t;}const int maxn=2000010,maxq=600010;struct cyc{
    int kind,id,ID,x,y,z;}a[maxq],b[maxq];int tot,n,c[maxn],ans[10010];#define lowbit(x) (x&-x)void modify(int x,int k){
    for(int i=x;i<=n;i+=lowbit(i))c[i]+=k;}int query(int x){
    int as=0;for(int i=x;i>=1;i-=lowbit(i))as+=c[i];return as;}bool cmp(cyc a,cyc b){
    return a.x
          
           
            
             >1; for(int i=l;i<=r;i++) if(a[i].kind==1&&a[i].id<=mid)modify(a[i].y,a[i].z); else if(a[i].kind==2&&a[i].id>mid)ans[a[i].ID]+=a[i].z*query(a[i].y); for(int i=l;i<=r;i++)if(a[i].kind==1&&a[i].id<=mid)modify(a[i].y,-a[i].z); int x1=l-1,x2=mid; for(int i=l;i<=r;i++) if(a[i].id<=mid)b[++x1]=a[i]; else b[++x2]=a[i]; for(int i=l;i<=r;i++)a[i]=b[i]; CDQ(l,mid);CDQ(mid+1,r);}int main(){ int S=read();n=read(); int kind=read(),ID=0;tot=0; while(kind!=3){ if(kind==1){ int x=read(),y=read(),z=read(); a[++tot]=(cyc){ 1,tot,0,x,y,z}; } else{ int x1=read(),y1=read(),x2=read(),y2=read();ID++; a[++tot]=(cyc){ 2,tot,ID,x2,y2,1}; a[++tot]=(cyc){ 2,tot,ID,x2,y1-1,-1}; a[++tot]=(cyc){ 2,tot,ID,x1-1,y2,-1}; a[++tot]=(cyc){ 2,tot,ID,x1-1,y1-1,1}; } kind=read(); } sort(a+1,a+tot+1,cmp); CDQ(1,tot); for(int i=1;i<=ID;i++)printf("%d\n",ans[i]); return 0;}