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分治你就会做了？
将一个询问操作拆成四个加加减减
三维偏序:操作顺序 横坐标 纵坐标

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n;
struct your
{
    int x,y,c;
    int flag,color;
    int id;
}a[1000000];
int ans[200010];
int f[2000010];
void update(int x,int c)
{
    for(;x<=n;x+=x&-x) f[x]+=c;
}
int ask(int x)
{
    int sum=0;
    for(;x;x-=x&-x) sum+=f[x];
    return sum;
}
int cmp(your j,your k)
{
    if(j.x==k.x) return j.id<k.id;
    return j.x<k.x;
}
void clean(int x)
{
    for(;x<=n;x+=x&-x) f[x]=0;
}
void cdq(int l,int r)
{
    if(l==r) return ;
    int mid=(l+r)>>1;
    cdq(l,mid),cdq(mid+1,r);
    sort(a+l,a+mid+1,cmp),sort(a+mid+1,a+r+1,cmp);
    int tmp=l,nmp=mid+1;
    for(;nmp<=r;nmp++)
    {
        while(tmp<=mid&&a[tmp].x<=a[nmp].x)
        {   
            if(!a[tmp].flag) update(a[tmp].y,a[tmp].c);
            tmp++;
        }
        if(a[nmp].flag) 
        {
            if(a[nmp].color) ans[a[nmp].id]+=ask(a[nmp].y);
            else ans[a[nmp].id]-=ask(a[nmp].y);
        }
    }   
    for(int i=l;i<=mid;i++)
        if(!a[i].flag) clean(a[i].y); 
}
int number[1000100];
int kkk;
int main()
{
    scanf("%d",&kkk);
    scanf("%d",&n);
    int tmp;
    scanf("%d",&tmp);
    int tot=0,cnt=0;
    while(tmp!=3)
    {
        tot++;
        int x,y,c;
        int dx,dy,kx,ky;
        if(tmp==1)
        {
            scanf("%d%d%d",&x,&y,&c);
            cnt++;
            a[cnt].x=x,a[cnt].y=y,a[cnt].c=c,a[cnt].flag=0,a[cnt].id=tot;
        }
        else
        {
            scanf("%d%d%d%d",&dx,&dy,&kx,&ky);
            cnt++,a[cnt].x=kx,a[cnt].y=ky,a[cnt].flag=1,a[cnt].id=tot,a[cnt].color=1;
            cnt++,a[cnt].x=kx,a[cnt].y=dy-1,a[cnt].flag=1,a[cnt].id=tot,a[cnt].color=0;
            cnt++,a[cnt].x=dx-1,a[cnt].y=ky,a[cnt].flag=1,a[cnt].id=tot,a[cnt].color=0;
            cnt++,a[cnt].x=dx-1,a[cnt].y=dy-1,a[cnt].flag=1,a[cnt].id=tot,a[cnt].color=1;
            number[++number[0]]=tot;
        }
        scanf("%d",&tmp);
    }   
    cdq(1,cnt);
    for(int i=1;i<=number[0];i++) printf("%d\n",ans[number[i]]+kkk);
    return 0;
}