首页 > 代码库 > 简单题(bzoj 1683)

简单题(bzoj 1683)

Description

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

 

命令

参数限制

内容

1 x y A

1<=x,y<=N,A是正整数

将格子x,y里的数字加上A

2 x1 y1 x2 y2

1<=x1<= x2<=N

1<=y1<= y2<=N

输出x1 y1 x2 y2这个矩形内的数字和

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。
/*
  第一次写cdq分治,先看了2013年集训队作业中许昊然的论文,有了一点初步理解,然后又做这个题,
  感觉对cdq分治的大概思路有了一定认识。
  
  cdq分治要求可离线,并且各个修改操作之间互不影响,且对查询操作的贡献独立。
  我们考虑将操作分治,那么后一般操作中的修改是独立的,查询至于前一半的所有修改和后一般在它时间之前的修改有关,
  对于前一半修改可以预处理,对于后一半在它之前的,可以递归处理。 
  
  这个题目的数据范围二维数据结构是不好过的,所以可以考虑将某一维排序,然后用一位数据结构维护。 
  我们用前缀和的思想,将求和操作理解为四个单点查询操作,然后对于每个查询操作x,y,对他有贡献的修改操作
  一定是时间在它之前的并且x比它小的,所以我们可以按照x坐标排序,然后用树状数组维护y坐标的值。 
*/
#include<cstdio>
#include<iostream>
#include<algorithm>
#define N 800010
using namespace std;
int n,tot,T,ans[N],tree[N];
struct node{
    int op,x,y,A,no,belong;
};node Q[N],tq[N];
bool cmp(const node&s1,const node&s2){
    if(s1.x==s2.x&&s1.y==s2.y) return s1.op<s2.op;
    if(s1.x==s2.x) return s1.y<s2.y;
    return s1.x<s2.x;
}
void modify(int x,int v){
    while(x<=n){
        tree[x]+=v;
        x+=x&(-x);
    }
}
int query(int x){
    int sum=0;
    while(x){
        sum+=tree[x];
        x-=x&(-x);
    }
    return sum;
}
void solve(int l,int r){
    if(l==r)return;
    int mid=l+r>>1;
    for(int i=l;i<=r;i++)
        if(Q[i].no<=mid&&Q[i].op==1) modify(Q[i].y,Q[i].A);
        else if(Q[i].no>mid&&Q[i].op==2){
            if(Q[i].A) ans[Q[i].belong]+=query(Q[i].y);
            else ans[Q[i].belong]-=query(Q[i].y);
        }
    for(int i=l;i<=r;i++)
        if(Q[i].no<=mid&&Q[i].op==1) modify(Q[i].y,-Q[i].A);
    int l1=l,l2=mid+1;
    for(int i=l;i<=r;i++)
        if(Q[i].no<=mid)tq[l1++]=Q[i];
        else tq[l2++]=Q[i];
    for(int i=l;i<=r;i++)
        Q[i]=tq[i];
    solve(l,mid);solve(mid+1,r);
}
int main(){
    scanf("%d",&n);
    int opt,x,y,v,x1,y1;
    while(1){
        scanf("%d",&opt);
        if(opt==1){
            scanf("%d%d%d",&x,&y,&v);
            Q[++tot].op=1;Q[tot].x=x;Q[tot].y=y;Q[tot].A=v;Q[tot].no=tot;
        }
        else if(opt==2){
            scanf("%d%d%d%d",&x,&y,&x1,&y1);
            Q[++tot].op=2;Q[tot].x=x-1;Q[tot].y=y-1;Q[tot].A=1;Q[tot].no=tot;Q[tot].belong=++T;
            Q[++tot].op=2;Q[tot].x=x-1;Q[tot].y=y1;Q[tot].A=0;Q[tot].no=tot;Q[tot].belong=T;
            Q[++tot].op=2;Q[tot].x=x1;Q[tot].y=y-1;Q[tot].A=0;Q[tot].no=tot;Q[tot].belong=T;
            Q[++tot].op=2;Q[tot].x=x1;Q[tot].y=y1;Q[tot].A=1;Q[tot].no=tot;Q[tot].belong=T;
        }
        else break;
    }
    sort(Q+1,Q+tot+1,cmp);
    solve(1,tot);
    for(int i=1;i<=T;i++)
        printf("%d\n",ans[i]);
    return 0;
}
    

 

简单题(bzoj 1683)