【BZOJ2850】巧克力王国 [KD-tree]

  1 #include<iostream>    
  2 #include<string>    
  3 #include<algorithm>    
  4 #include<cstdio>    
  5 #include<cstring>    
  6 #include<cstdlib>    
  7 #include<cmath>    
  8 #include<map>  
  9 using namespace std;  
 10 
 11 typedef long long s64;
 12 
 13 const int ONE=1000001;
 14 const int INF=2147483640;
 15 
 16 int n,m;
 17 int x,y,A,B;
 18 s64 C,h;
 19 int root;
 20 s64 Ans;
 21 int Ran;
 22 
 23 struct power
 24 {
 25         int x,y,l,r;
 26         int maxx,maxy; 
 27         int minx,miny;
 28         s64 val,sum;
 29 }a[ONE];
 30 
 31 int get()
 32 {    
 33         int res=1,Q=1;char c;    
 34         while( (c=getchar())<48 || c>57 ) 
 35         if(c==‘-‘)Q=-1; 
 36         res=c-48;     
 37         while( (c=getchar())>=48 && c<=57 )    
 38         res=res*10+c-48;    
 39         return res*Q;    
 40 }
 41 
 42 namespace KD
 43 {
 44         void Update(int i)
 45         {
 46             a[i].sum=a[i].val;
 47             if(a[i].l)
 48             {
 49                 a[i].sum+=a[a[i].l].sum;
 50                 a[i].minx=min(a[i].minx,a[a[i].l].minx);    a[i].miny=min(a[i].miny,a[a[i].l].miny);
 51                 a[i].maxx=max(a[i].maxx,a[a[i].l].maxx);    a[i].maxy=max(a[i].maxy,a[a[i].l].maxy); 
 52             }
 53             if(a[i].r)
 54             {
 55                 a[i].sum+=a[a[i].r].sum;
 56                 a[i].minx=min(a[i].minx,a[a[i].r].minx);    a[i].miny=min(a[i].miny,a[a[i].r].miny);
 57                 a[i].maxx=max(a[i].maxx,a[a[i].r].maxx);    a[i].maxy=max(a[i].maxy,a[a[i].r].maxy);
 58             }
 59         }
 60         
 61         int cmp(const power &a,const power &b)
 62         {
 63             if(Ran) return a.x<b.x; return a.y<b.y;
 64         }
 65         
 66         int Build(int l,int r,int T)
 67         {
 68             int mid=(l+r)/2;
 69             Ran=T;
 70             nth_element(a+l,a+mid,a+r+1,cmp);
 71             if(l<mid) a[mid].l = Build(l,mid-1,T^1);
 72             if(mid<r) a[mid].r = Build(mid+1,r,T^1);
 73             Update(mid);
 74             return mid;
 75         }
 76 }
 77 
 78 int PD(int x,int y)
 79 {
 80         return (s64)A*x+(s64)B*y < C ;
 81 }
 82 
 83 int Check(int i)
 84 {
 85         int res=0;
 86         res+= PD(a[i].minx,a[i].miny);
 87         res+= PD(a[i].minx,a[i].maxy);
 88         res+= PD(a[i].maxx,a[i].miny);
 89         res+= PD(a[i].maxx,a[i].maxy);
 90         return res;
 91 }
 92 
 93 void Query(int i)
 94 {
 95         if(PD(a[i].x,a[i].y)) Ans+=a[i].val;
 96         if(a[i].l)
 97         {
 98             int Record=Check(a[i].l);
 99             if(Record==4) Ans+=a[a[i].l].sum;
100             else if(Record) Query(a[i].l);
101         }
102         if(a[i].r)
103         {
104             int Record=Check(a[i].r);
105             if(Record==4) Ans+=a[a[i].r].sum;
106             else if(Record) Query(a[i].r);
107         }
108 }
109 
110 
111 int main() 
112 {
113         n=get();    m=get();
114         for(int i=1;i<=n;i++) a[i].minx=a[i].miny=INF;
115         for(int i=1;i<=n;i++)
116         {
117             x=get();    y=get();    scanf("%lld",&h);
118             a[i].val=h;
119             a[i].x=a[i].minx=a[i].maxx=x;
120             a[i].y=a[i].miny=a[i].maxy=y;
121         }
122         root=KD::Build(1,n,1);
123         
124         while(m--)
125         {
126             A=get();    B=get();    scanf("%lld",&C);
127             Ans=0;
128             Query(root);
129             printf("%lld\n",Ans);
130         }
131         
132 }