【BZOJ2527】【POI2011】Meteors [整体二分]

Meteors

Time Limit: 60 Sec Memory Limit: 128 MB
[Submit][Status][Discuss]

Description

　　这个星球经常会下陨石雨。BIU已经预测了接下来K场陨石雨的情况。
　　BIU的第i个成员国希望能够收集Pi单位的陨石样本。你的任务是判断对于每个国家，它需要在第几次陨石雨之后，才能收集足够的陨石。

Input

　　第一行是两个数N,M。
　　第二行有M个数，第i个数Oi表示第i段轨道上有第Oi个国家的太空站。
　　第三行有N个数，第i个数Pi表示第i个国家希望收集的陨石数量。
　　第四行有一个数K，表示BIU预测了接下来的K场陨石雨。
　　接下来K行，每行有三个数Li,Ri,Ai，表示第K场陨石雨的发生地点在从Li顺时针到Ri的区间中（如果Li<=Ri，就是Li,Li+1,...,Ri，否则就是Ri,Ri+1,...,m-1,m,1,...,Li），向区间中的每个太空站提供Ai单位的陨石样本。

Output

　　输出N行。第i行的数Wi表示第i个国家在第Wi波陨石雨之后能够收集到足够的陨石样本。如果到第K波结束后仍然收集不到，输出NIE。

Sample Input

　　3 5
　　1 3 2 1 3
　　10 5 7
　　3
　　4 2 4
　　1 3 1
　　3 5 2

Sample Output

　　3
　　NIE
　　1

HINT

　　1<=n,m,k<=3*10^5 , 1<=Ai,Pi<=10^9

Main idea

　　每个国家有一个需要价值，一个国家可以控制多个点，定义国家已经获得的价值为每个控制点上的价值和，每次操作可以将一段区间上每个点都加上一个价值，问每个国家在第几个操作时达到了需要价值，若达不到则输出NIE。

Solution

　　我们先从二分层面去考虑，对于一个点来说，可以二分答案来求解，那么我们就可以利用整体二分。

　　整体二分，就是我们将所有的询问一起来做，然后二分操作区间L,R，执行L,MID的部分，

　　然后判断询问是否可行，如果可行，将这个询问放到左边区间，否则加上左边的价值再把这个询问放到右区间。然后继续递归操作区间。

　　对于这道题来说，由于一个国家可以控制多个点，我们用链表来存，然后用Bit来判断是否可行。

　　这样就解决了这道题(≧▽≦)/。

Code

  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=300005;
 14 const int INF=2147483640;
 15   
 16 int n,m,k;
 17 int x;
 18 int next[ONE],first[ONE],go[ONE],tot;
 19 int Ans[ONE];
 20   
 21 struct power
 22 {
 23         int need;
 24         int id;
 25 }a[ONE],qL[ONE],qR[ONE];
 26   
 27 struct opera
 28 {
 29         int l,r;
 30         int val;
 31 }oper[ONE];
 32   
 33 int get()
 34 {    
 35         int res=1,Q=1;char c;    
 36         while( (c=getchar())<48 || c>57 ) 
 37         if(c=='-')Q=-1; 
 38         res=c-48;     
 39         while( (c=getchar())>=48 && c<=57 )    
 40         res=res*10+c-48;    
 41         return res*Q;    
 42 }
 43   
 44 void Add(int u,int v)
 45 {
 46         next[++tot]=first[u];   first[u]=tot;   go[tot]=v;
 47 }
 48   
 49 namespace Bit
 50 {
 51         struct power
 52         {
 53             s64 value;
 54         }Node[ONE];
 55          
 56         int lowbit(int i)
 57         {
 58             return i&-i;
 59         }
 60          
 61         void Update(int R,int x)
 62         {
 63             for(int i=R;i<=m;i+=lowbit(i))
 64             Node[i].value+=x;
 65         }
 66           
 67         s64 Query(int R)
 68         {
 69             s64 res=0;
 70             for(int i=R;i>=1;i-=lowbit(i))
 71             res+=Node[i].value;
 72             return res;
 73         }
 74 }
 75   
 76 void Update(int l,int r,int val)
 77 {
 78         if(l>r)
 79         {
 80             Bit::Update(l,val); Bit::Update(m+1,-val);
 81             Bit::Update(1,val); Bit::Update(r+1,-val);
 82         }
 83         else
 84         {   
 85             Bit::Update(l,val); Bit::Update(r+1,-val);
 86         }
 87 }
 88   
 89 void Solve(int l,int r,int L,int R)//l,r 询问;L,R 操作
 90 {
 91         if(l>r) return;
 92         if(L==R)
 93         {
 94             for(int i=l;i<=r;i++)
 95             Ans[a[i].id] = L;
 96             return;
 97         }
 98           
 99         int M=(L+R)>>1;
100         for(int i=L;i<=M;i++)
101         Update(oper[i].l, oper[i].r, oper[i].val);
102           
103         int l_num=0,r_num=0;
104         for(int i=l;i<=r;i++) //判断询问在哪个区间 
105         {
106             s64 sum=0;
107             for(int e=first[a[i].id];e;e=next[e])
108             {
109                 sum+=Bit::Query(go[e]);
110                 if(sum>=a[i].need) break;
111             }
112              
113             if(sum>=a[i].need)
114             {
115                 qL[++l_num]=a[i];
116             }
117             else
118             {
119                 qR[++r_num]=a[i];
120                 qR[r_num].need-=sum;
121             }
122         }
123         int t=l;
124         for(int i=1;i<=l_num;i++) a[t++]=qL[i];
125         for(int i=1;i<=r_num;i++) a[t++]=qR[i];
126           
127         for(int i=L;i<=M;i++)
128         Update(oper[i].l, oper[i].r, -oper[i].val);
129           
130         Solve(l,l+l_num-1,L,M);
131         Solve(l+l_num,r,M+1,R);
132 }
133   
134 int main() 
135 {
136         n=get();    m=get();
137         for(int i=1;i<=m;i++) {x=get(); Add(x,i);}
138         for(int i=1;i<=n;i++)
139         {
140             a[i].need=get();
141             a[i].id=i;
142         }
143           
144         k=get();
145         for(int i=1;i<=k;i++)
146         {
147             oper[i].l=get();    oper[i].r=get();    oper[i].val=get();
148         }
149           
150         Solve(1,n,1,k+1);
151           
152         for(int i=1;i<=n;i++)
153         {
154             if(Ans[i] > k) printf("NIE");
155             else printf("%d",Ans[i]);
156             printf("
");
157         }
158 }

View Code