首页 > 代码库 > Bzoj4066 简单题
Bzoj4066 简单题
Submit: 2185 Solved: 581
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。
接下来每行一个操作。每条命令除第一个数字之外，
均要异或上一次输出的答案last_ans，初始时last_ans=0。
Output
对于每个2操作，输出一个对应的答案。
Sample Input
4
1 2 3 3
2 1 1 3 3
1 1 1 1
2 1 1 0 7
3
1 2 3 3
2 1 1 3 3
1 1 1 1
2 1 1 0 7
3
Sample Output
3
5
5
HINT
数据规模和约定
1<=N<=500000,操作数不超过200000个，内存限制20M，保证答案在int范围内并且解码之后数据仍合法。
样例解释见OJ2683
新加数据一组，但未重测----2015.05.24
Source
By wjy1998
同Bzoj2683。
由于强制在线，所以不能像2683那样各种方法乱搞，只能老实写K-Dtree（好像还有块链之类的解法）
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 // 52 t[mid].l=Build(l,mid-1,D^1); 53 if(t[mid].l)pushup(mid,t[mid].l); 54 t[mid].r=Build(mid+1,r,D^1); 55 if(t[mid].r)pushup(mid,t[mid].r); 56 // 57 t[mid].sum=t[mid].w+t[t[mid].l].sum+t[t[mid].r].sum; 58 return mid; 59 } 60 void insert(int &now,int x,int D){ 61 if(!now){now=x;return;} 62 if(t[x].d[D]==t[now].d[D] && t[x].d[!D]==t[now].d[!D]){ 63 t[now].w+=t[x].w; 64 t[now].sum+=t[x].w; 65 --cnt; 66 return; 67 } 68 if(t[x].d[D]<t[now].d[D]){ 69 insert(t[now].l,x,D^1); 70 pushup(now,t[now].l); 71 } 72 else{ 73 insert(t[now].r,x,D^1); 74 pushup(now,t[now].r); 75 } 76 t[now].sum=t[now].w+t[t[now].l].sum+t[t[now].r].sum; 77 return; 78 } 79 LL query(int rt,int x1,int y1,int x2,int y2){ 80 if(!rt)return 0; 81 LL res=0; 82 if(in(x1,y1,x2,y2,rt)){return t[rt].sum;} 83 if(out(x1,y1,x2,y2,rt)){return 0;} 84 if(x1<=t[rt].d[0] && t[rt].d[0]<=x2 && 85 y1<=t[rt].d[1] && t[rt].d[1]<=y2) res+=t[rt].w; 86 res+=query(t[rt].l,x1,y1,x2,y2)+query(t[rt].r,x1,y1,x2,y2); 87 return res; 88 } 89 int main(){ 90 int i,j,op,x,y,w; 91 n=read();lim=9000; 92 LL lans=0;int X1,X2,Y1,Y2; 93 while(1){ 94 op=read(); 95 if(op==3)break; 96 if(op==1){ 97 t[++cnt].d[0]=read()^lans;t[cnt].d[1]=read()^lans; 98 t[cnt].w=read()^lans;t[cnt].sum=t[cnt].w; 99 t[cnt].max[0]=t[cnt].min[0]=t[cnt].d[0];100 t[cnt].max[1]=t[cnt].min[1]=t[cnt].d[1];101 insert(root,cnt,0);102 if(cnt==lim){103 lim+=9000;104 root=Build(1,cnt,0);105 }106 }107 else{108 109 X1=read()^lans;Y1=read()^lans;X2=read()^lans;Y2=read()^lans;110 lans=query(root,X1,Y1,X2,Y2);111 printf("%lld\n",lans);112 }113 }114 return 0;115 }
Bzoj4066 简单题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。