POI2011 MET-Meteors
题解：
第一道整体二分。
如果只有一个询问，我们可以二分答案，然后O(n)验证;
对于多种询问而且不强制在线，我们就可以使用整体二分。
整体二分的精髓是，先想一个二分暴力，然后把所有二分过程放在一起。
还有，整体二分中，分的是值域。
对于本题直接二分值域，然后将前$mid$个操作扔到树状数组/线段树中。
然后按能/不能完成二分。
到达底层，值域为$[l,l]$，我们就可以直接赋值了。
代码：
#include<vector> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define N 300050 #define ll long long const int inf = 0x3f3f3f3f; inline int rd() { int f = 1,c = 0;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){c=10*c+ch-'0';ch=getchar();} return f*c; } int n,m,k; int ans[N],o[N]; vector<int>ve[N]; struct node { int id; ll lim; }p[N],tmpl[N],tmpr[N]; int tim; struct BIT { ll f[N]; void up(int x,ll d) { if(!x)return ; while(x<N)f[x]+=d,x+=(x&-x); } ll down(int x) { if(!x)return 0; ll ret = 0; while(x)ret+=f[x],x-=(x&-x); return ret; } }tr; struct Stars { int l,r,d; }s[N]; void update(int l,int r,int d) { if(l<=r) { tr.up(l,d); tr.up(r+1,-d); }else { tr.up(1,d),tr.up(r+1,-d); tr.up(l,d),tr.up(m+1,-d); } } void divi(int l,int r,int beg,int ens) { if(beg>ens)return ; if(l==r) { for(int i=beg;i<=ens;i++) ans[p[i].id] = l; return ; } int mid = (l+r)>>1; while(tim<mid)tim++,update(s[tim].l,s[tim].r,s[tim].d); while(tim>mid)update(s[tim].l,s[tim].r,-s[tim].d),tim--; int lt=0,rt=0; for(int i=beg;i<=ens;i++) { ll sum = 0; for(int j=0;j<ve[p[i].id].size();j++) { sum+=tr.down(ve[p[i].id][j]); if(sum>=p[i].lim)break; } if(sum>=p[i].lim)tmpl[++lt]=p[i]; else tmpr[++rt]=p[i]; } for(int i=beg;i<=beg+lt-1;i++)p[i]=tmpl[i-beg+1]; for(int i=beg+lt;i<=ens;i++)p[i]=tmpr[i-beg-lt+1]; divi(l,mid,beg,beg+lt-1); divi(mid+1,r,beg+lt,ens); } int main() { n = rd(),m = rd(); for(int i=1;i<=m;i++) { o[i] = rd(); ve[o[i]].push_back(i); } for(int i=1;i<=n;i++) { p[i].id = i; p[i].lim = rd(); } k = rd(); for(int i=1;i<=k;i++) s[i].l = rd(),s[i].r = rd(),s[i].d = rd(); divi(1,k+1,1,n); for(int i=1;i<=n;i++) { if(ans[i]==k+1)puts("NIE"); else printf("%d ",ans[i]); } return 0; }