BZOJ4066: 简单题-白红宇

BZOJ4066: 简单题

阅读量：4311 次

发布时间：2019-06-06

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

题解:KDtree模板题 (犯了逻辑错误调了2个小时

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #define mp make_pair#define pb push_back#define pii pair
               
                #define inc(i,l,r) for(int i=l;i<=r;i++)#define dec(i,r,l) for(int i=r;i>=l;i--)const int MAXN=4e5+10;const double eps=1e-8;#define ll long longusing namespace std;ll read(){ ll x=0,f=1;char ch=getchar(); while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();} while(isdigit(ch))x=x*10+ch-'0',ch=getchar(); return x*f;}int rt,d,n;typedef struct node{ int p[2],c[2],maxx[2],minn[2],sum,key; friend bool operator<(node aa,node bb){ if(aa.p[d]!=bb.p[d])return aa.p[d]
                
                 >1; d=now;nth_element(a+l,a+mid,a+r+1); for(int i=0;i<=1;i++)a[mid].minn[i]=a[mid].maxx[i]=a[mid].p[i]; a[mid].sum=a[mid].key;a[mid].c[0]=a[mid].c[1]=0; if(l
                 
                  mid)a[mid].c[1]=built(mid+1,r,now^1),up(mid,a[mid].c[1]); return mid;}inline void insert(int x){ int *t=&rt; d=0; while(*t)up(*t,x),t=&a[*t].c[a[x].p[d]>a[*t].p[d]],d=d^1; *t=x;}int ans;inline void querty(int x,int x1,int y1,int x2,int y2){ if(!x)return ; int t=x; if(a[t].minn[0]>=x1&&a[t].maxx[0]<=x2&&a[t].minn[1]>=y1&&a[t].maxx[1]<=y2){ans+=a[t].sum;return ;} if(a[t].minn[0]>x2||a[t].maxx[0]
                  
                   y2||a[t].maxx[1]
                   
                    =x1&&a[x].p[0]<=x2&&a[x].p[1]>=y1&&a[x].p[1]<=y2)ans+=a[x].key; querty(a[x].c[0],x1,y1,x2,y2); querty(a[x].c[1],x1,y1,x2,y2);}int main(){ n=read();int op,x,y,x1,y1,t; int tot=0;int res=0; while(op=read()){ if(op==3)break; if(op==1){ x=read()^res;y=read()^res;t=read()^res; tot++; a[tot].c[0]=a[tot].c[1]=0;a[tot].key=a[tot].sum=t; a[tot].p[0]=a[tot].maxx[0]=a[tot].minn[0]=x; a[tot].p[1]=a[tot].maxx[1]=a[tot].minn[1]=y; insert(tot); if(tot%10000==0)rt=built(1,tot,0); } else{ x=read()^res;y=read()^res;x1=read()^res;y1=read()^res; ans=0;querty(rt,x,y,x1,y1); res=ans;printf("%d\n",res); } }}

4066: 简单题

Time Limit: 50 Sec Memory Limit: 20 MB

Submit: 5024 Solved: 1414

[ ][ ][ ]

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	无	终止程序