首页 > 代码库 > Bzoj2683 简单题

Bzoj2683 简单题

2024-08-29 00:20:48   220人阅读

Time Limit: 50 Sec  Memory Limit: 128 MB
Submit: 1071  Solved: 428

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。

 

Source

 

嘛，真是简单题啊，才调了两天就过了。

K-Dtree定期重构，强行维护数据。常数写不好的话会T飞。

之前把47行的左右边界取错了，时间复杂度直接突破天际。

  1 /*by SilverN*/  2 #include<algorithm>  3 #include<iostream>  4 #include<cstring>  5 #include<cstdio>  6 #include<cmath>  7 #include<vector>  8 #define LL long long  9 using namespace std; 10 const int mxn=250010; 11 LL read(){ 12     LL x=0,f=1;char ch=getchar(); 13     while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 14     while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} 15     return x*f; 16 } 17 struct node{ 18     int l,r; 19     int min[2],max[2]; 20     int d[2]; 21     int w; 22     LL sum; 23 }t[mxn]; 24 int root=0,nowD; 25 int cmp(const node a,const node b){ 26     return a.d[nowD]<b.d[nowD]; 27 } 28 int n,cnt; 29 int lim=0; 30 inline void pushup(int rt,int x){ 31     t[rt].max[0]=max(t[rt].max[0],t[x].max[0]); 32     t[rt].max[1]=max(t[rt].max[1],t[x].max[1]); 33     t[rt].min[0]=min(t[rt].min[0],t[x].min[0]); 34     t[rt].min[1]=min(t[rt].min[1],t[x].min[1]); 35     return; 36 } 37 inline bool in(int x1,int y1,int x2,int y2,int k){ 38     return (x1<=t[k].min[0] && t[k].max[0]<=x2 && 39         y1<=t[k].min[1] && t[k].max[1]<=y2); 40 } 41 inline bool out(int x1,int y1,int x2,int y2,int k){ 42     return (x1>t[k].max[0] || x2<t[k].min[0] || y1>t[k].max[1] || y2<t[k].min[1]); 43 } 44 int Build(int l,int r,int D){ 45     if(l>r)return 0; 46     nowD=D;int mid=(l+r)>>1; 47     nth_element(t+l,t+mid,t+r+1,cmp);/// 48     t[mid].max[0]=t[mid].min[0]=t[mid].d[0]; 49     t[mid].max[1]=t[mid].min[1]=t[mid].d[1]; 50     t[mid].sum=t[mid].w; 51     t[mid].l=Build(l,mid-1,D^1); 52     if(t[mid].l)pushup(mid,t[mid].l); 53     t[mid].r=Build(mid+1,r,D^1); 54     if(t[mid].r)pushup(mid,t[mid].r); 55     t[mid].sum=t[mid].w+t[t[mid].l].sum+t[t[mid].r].sum; 56     return mid; 57 } 58 void insert(int &now,int x,int D){ 59     if(!now){now=x;return;} 60     if(t[x].d[D]==t[now].d[D] && t[x].d[!D]==t[now].d[!D]){ 61         t[now].w+=t[x].w; 62         t[now].sum+=t[x].w; 63         --cnt; 64         return; 65     } 66     if(t[x].d[D]<t[now].d[D]){ 67         insert(t[now].l,x,D^1); 68         pushup(now,t[now].l); 69     } 70     else{ 71         insert(t[now].r,x,D^1); 72         pushup(now,t[now].r); 73     } 74     t[now].sum=t[now].w+t[t[now].l].sum+t[t[now].r].sum; 75     return; 76 } 77 LL query(int rt,int x1,int y1,int x2,int y2){ 78     if(!rt)return 0; 79     LL res=0; 80     if(in(x1,y1,x2,y2,rt)){return t[rt].sum;} 81     if(out(x1,y1,x2,y2,rt)){return 0;} 82     if(x1<=t[rt].d[0] && t[rt].d[0]<=x2 &&  83         y1<=t[rt].d[1] && t[rt].d[1]<=y2) res+=t[rt].w; 84     res+=query(t[rt].l,x1,y1,x2,y2)+query(t[rt].r,x1,y1,x2,y2); 85     return res; 86 } 87 int main(){ 88     int i,j,op,x,y,w; 89     n=read();lim=10000; 90     int X1,X2,Y1,Y2; 91     while(1){ 92         op=read(); 93         if(op==3)break; 94         if(op==1){ 95             t[++cnt].d[0]=read();t[cnt].d[1]=read(); 96             t[cnt].w=read();t[cnt].sum=t[cnt].w; 97             t[cnt].max[0]=t[cnt].min[0]=t[cnt].d[0]; 98             t[cnt].max[1]=t[cnt].min[1]=t[cnt].d[1]; 99             insert(root,cnt,0);100             if(cnt==lim){101                 lim+=10000;102                 root=Build(1,cnt,0);103             }104         }105         else{106  107             X1=read();Y1=read();X2=read();Y2=read();108             printf("%lld\n",query(root,X1,Y1,X2,Y2));109         }110     }111     return 0;112 }

 

Bzoj2683 简单题


联系
我们