bzoj 4066: 简单题-白红宇

bzoj 4066: 简单题

阅读量：5984 次

发布时间：2019-06-20

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

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #define M 200009  6 #define inf 100000000  7 #define ll long long  8 using namespace std;  9 struct A 10 { 11     int l,r,mn[2],mx[2],d[2],v; 12     ll sum; 13 }a[M],b,p[M]; 14 int n,m,root,N,tot; 15 ll lans; 16 void updata(int k) 17 { 18     A l1=a[a[k].l],r1=a[a[k].r]; 19     for(int i=0;i<2;i++) 20       { 21         a[k].mn[i]=a[k].mx[i]=a[k].d[i]; 22         if(a[k].l) 23           a[k].mn[i]=min(a[k].mn[i],l1.mn[i]),a[k].mx[i]=max(a[k].mx[i],l1.mx[i]); 24         if(a[k].r) 25           a[k].mn[i]=min(a[k].mn[i],r1.mn[i]),a[k].mx[i]=max(a[k].mx[i],r1.mx[i]); 26       } 27     a[k].sum=l1.sum+r1.sum+(ll)a[k].v; 28     return; 29 } 30 bool cmp(A a1,A a2) 31 { 32     return a1.d[N]
         
          >1; 38     nth_element(p+l1,p+mid,p+r1+1,cmp); 39     a[mid]=p[mid]; 40     if(l1
          
           mid) 45 a[mid].r=rebuild(mid+1,r1,now^1); 46 else 47 a[mid].r=0; 48 updata(mid); 49 return mid; 50 } 51 void cha(int &k,A b,int now) 52 { 53 if(!k) 54 { 55 k=++m; 56 for(int i=0;i<2;i++) 57 a[k].mn[i]=a[k].mx[i]=a[k].d[i]=b.d[i]; 58 a[k].l=a[k].r=0; 59 } 60 if(a[k].d[0]==b.d[0]&&a[k].d[1]==b.d[1]) 61 { 62 a[k].v+=b.v; 63 a[k].sum+=b.v; 64 return; 65 } 66 if(a[k].d[now]>b.d[now]) 67 cha(a[k].l,b,now^1); 68 else 69 cha(a[k].r,b,now^1); 70 updata(k); 71 } 72 ll zhao(int k,int x1,int y1,int x2,int y2) 73 { 74 if(a[k].mn[0]>=x1&&a[k].mn[1]>=y1&&a[k].mx[0]<=x2&&a[k].mx[1]<=y2) 75 return a[k].sum; 76 if(a[k].mn[0]>x2||a[k].mn[1]>y2||a[k].mx[0]
           
            
             =x1&&a[k].d[1]>=y1&&a[k].d[0]<=x2&&a[k].d[1]<=y2) 80 tmp+=a[k].v; 81 return tmp+zhao(a[k].l,x1,y1,x2,y2)+zhao(a[k].r,x1,y1,x2,y2); 82 } 83 84 ll read() 85 { 86 ll x=0,f=1;char ch=getchar(); 87 while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar();} 88 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 89 return x*f; 90 } 91 int main() 92 { 93 n=read(); 94 tot=10000; 95 for(;;) 96 { 97 int a1,a2,a3,a4; 98 a1=read(); 99 if(a1==3)100 return 0;101 a2=read()^lans;102 a3=read()^lans;103 a4=read()^lans;104 if(a1==1)105 {106 b.d[0]=a2;107 b.d[1]=a3;108 b.v=a4;109 cha(root,b,0);110 if(m==tot)111 {112 for(int i=1;i<=m;i++)113 p[i]=a[i];114 root=rebuild(1,m,0);115 tot+=10000;116 }117 }118 else119 {120 int a5;121 a5=read()^lans;122 printf("%lld\n",lans=zhao(root,a2,a3,a4,a5));123 }124 }125 return 0;126 }