Bzoj4066 简单题-白红宇

Bzoj4066 简单题

阅读量：6584 次

发布时间：2019-06-24

本文共 2042 字，大约阅读时间需要 6 分钟。

Time Limit: 50 Sec Memory Limit: 20 MB

Submit: 2185 Solved: 581

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。

接下来每行一个操作。每条命令除第一个数字之外，

均要异或上一次输出的答案last_ans，初始时last_ans=0。

Output

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

Sample Input

1 2 3 3

2 1 1 3 3

1 1 1 1

2 1 1 0 7

Sample Output

HINT

数据规模和约定

1<=N<=500000,操作数不超过200000个，内存限制20M，保证答案在int范围内并且解码之后数据仍合法。

样例解释见OJ2683

新加数据一组，但未重测----2015.05.24

Source

同Bzoj2683。

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

由于强制在线，所以不能像2683那样各种方法乱搞，只能老实写K-Dtree（好像还有块链之类的解法）

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

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

1 /*by SilverN*/  2 #include
     
        3 #include
      
         4 #include
       
          5 #include
        
           6 #include
         
            7 #include
          
            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]
           
            t[k].max[0] || x2
            
             t[k].max[1] || y2
             
              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]