【BZOJ】1176: [Balkan2007]Mokia

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

【算法】CDQ分治（算法知识见数据结构）

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

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

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

#include<cstdio>

#include<cstring>

#include<cctype>

#include<algorithm>

using namespace std;

int read(){

    char c;int s=,t=;

    while(!isdigit(c=getchar()))if(c=='-')t=-;

    do{s=s*+c-'';}while(isdigit(c=getchar()));

    return s*t;

}

const int maxn=,maxq=;

struct cyc{int kind,id,ID,x,y,z;}a[maxq],b[maxq];

int tot,n,c[maxn],ans[];

#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=;for(int i=x;i>=;i-=lowbit(i))as+=c[i];return as;}

bool cmp(cyc a,cyc b){return a.x<b.x||(a.x==b.x&&a.y<b.y)||(a.x==b.x&&a.y==b.y&&a.kind<b.kind);}

void CDQ(int l,int r){

    if(l==r)return;

    int mid=(l+r)>>;

    for(int i=l;i<=r;i++)

        if(a[i].kind==&&a[i].id<=mid)modify(a[i].y,a[i].z);

        else if(a[i].kind==&&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==&&a[i].id<=mid)modify(a[i].y,-a[i].z);

    int x1=l-,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+,r);

}

int main(){

    int S=read();n=read();

    int kind=read(),ID=;tot=;

    while(kind!=){

        if(kind==){

            int x=read(),y=read(),z=read();

            a[++tot]=(cyc){,tot,,x,y,z};

        }

        else{

            int x1=read(),y1=read(),x2=read(),y2=read();ID++;

            a[++tot]=(cyc){,tot,ID,x2,y2,};

            a[++tot]=(cyc){,tot,ID,x2,y1-,-};

            a[++tot]=(cyc){,tot,ID,x1-,y2,-};

            a[++tot]=(cyc){,tot,ID,x1-,y1-,};

        }

        kind=read();

    }

    sort(a+,a+tot+,cmp);

    CDQ(,tot);

    for(int i=;i<=ID;i++)printf("%d\n",ans[i]);

    return ;

}