bzoj 1176: [Balkan2007]Mokia&&2683: 简单题 -- cdq分治

2683: 简单题

Time Limit: 50 Sec Memory Limit: 128 MB

Description

你有一个N*N的棋盘，每个格子内有一个整数，初始时的时候全部为0，现在需要维护两种操作：

命令	参数限制	内容
1 x y A	1<=x,y<=N，A是正整数	将格子x,y里的数字加上A
2 x₁ y₁ x₂ y₂	1<=x₁<= x₂<=N 1<=y₁<= y₂<=N	输出x₁ y₁ x₂ y₂这个矩形内的数字和
3	无	终止程序

Input

输入文件第一行一个正整数N。

接下来每行一个操作。

Output

对于每个2操作，输出一个对应的答案。

Sample Input

4
1 2 3 3
2 1 1 3 3
1 2 2 2
2 2 2 3 4
3

Sample Output

3
5

HINT

1<=N<=500000,操作数不超过200000个，内存限制20M。

对于100%的数据，操作1中的A不超过2000。

Source

拆点，cdq分治，第一维排序，第二维树状数组维护

#include<map>

#include<cmath>

#include<queue>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

#define inf 1000000007

#define ll long long

#define N 2000010

inline int rd()

{

    int x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

struct qaz{int op,x,y,v,dd;}q[N];

bool cmp(qaz a,qaz b){return a.x==b.x?a.y<b.y:a.x<b.x;}

int n,ans[N],m,ji[N],mm;

int c[N];

void add(int x,int v){for(int i=x;i<=n;i+=i&(-i)) c[i]+=v;}

int fd(int x){int sum=;for(int i=x;i;i-=i&(-i)) sum+=c[i];return sum;}

void cdq(int l,int r)

{

    if(l==r) return;

    int mid=l+r>>;

    cdq(l,mid);cdq(mid+,r);

    sort(q+l,q+mid+,cmp);

    sort(q+mid+,q+r+,cmp);

    int i=l,j=mid+,lst=;

    while(j<=r)

    {

        while(q[i].op==&&i<=mid) i++;

        while(q[j].op==&&j<=r) j++;

        if(i<=mid&&q[i].x<=q[j].x) add(q[i].y,q[i].v),lst=i++;

        else if(j<=r) ans[q[j].dd]+=fd(q[j].y),j++;

    }

    for(i=l;i<=lst;i++) if(q[i].op==) add(q[i].y,-q[i].v);

}

int main()

{

    n=rd();

    int op,x,y,A,x2,y2;

    while()

    {

        op=rd();

        if(op==)

        {

            x=rd();y=rd();A=rd();

            q[++m]=(qaz){,x,y,A,m};

        }

        else if(op==)

        {

            x=rd();y=rd();x2=rd();y2=rd();

            ji[++mm]=m;

            q[++m]=(qaz){,x2,y2,,m};

            q[++m]=(qaz){,x-,y-,,m};

            q[++m]=(qaz){,x2,y-,,m};

            q[++m]=(qaz){,x-,y2,,m};

        }

        else break;

    }

    cdq(,m);

    for(int i=,p=ji[i];i<=mm;i++,p=ji[i])

        printf("%d\n",ans[p+]+ans[p+]-ans[p+]-ans[p+]);

    return ;

}

巴特西