题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2527
题意：
有n个国家和m个空间站，每个空间站都属于一个国家，一个国家可以有多个空间站，所有空间站按照顺序形成一个环，也就是说，m号空间站和1号空间站相邻。
现在，将会有k场流星雨降临，每一场流星雨都会给区间[li,ri]内的每个空间站带来ai单位的陨石，每个国家都有一个收集陨石的目标pi，即第i个国家需要收集pi单位的陨石。
询问：每个国家最早完成陨石收集目标是在第几场流星雨过后。
1<=n,m,k<=300000
题解：
整体二分。
将所有的国家一起二分。
对于当前的答案区间[l,r]，先模拟下前mid场的流星雨，用树状数组维护。
再将已经超出目标pi的国家放到左边；把没达到目标的放在右边，并将这些国家的需求减去已经收集到的数量。
然后恢复刚才的流星雨，带上相应的国家，分别左右递归。
当访问到叶子节点的时候（即l==r），当前存的国家的答案即为l。
AC Code:
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#define MAX_N 300005
#define INF 100000000 using namespace std; int n,m,t;
int ct[MAX_N];
int nd[MAX_N];
int L[MAX_N];
int R[MAX_N];
int a[MAX_N];
int ans[MAX_N];
long long sum[MAX_N];
long long dat[MAX_N];
vector<int> sp[MAX_N]; void update(int k,int x)
{
while(k>)
{
dat[k]+=x;
k-=k&-k;
}
} long long query(int k)
{
long long sum=;
while(k<=m)
{
sum+=dat[k];
k+=k&-k;
}
return sum;
} void section(int l,int r,int x)
{
update(r,x);
update(l-,-x);
} void meteor(int x,int f)
{
if(L[x]<=R[x]) section(L[x],R[x],a[x]*f);
else section(L[x],m,a[x]*f),section(,R[x],a[x]*f);
} void read()
{
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)
{
scanf("%d",&ct[i]);
sp[ct[i]].push_back(i);
}
for(int i=;i<=n;i++)
{
scanf("%d",&nd[i]);
}
scanf("%d",&t);
for(int i=;i<=t;i++)
{
scanf("%d%d%d",&L[i],&R[i],&a[i]);
}
t++;
L[t]=; R[t]=t; a[t]=INF;
} void dfs(vector<int> v,int l,int r)
{
if(l==r)
{
for(int i=;i<v.size();i++)
{
ans[v[i]]=l;
}
return;
}
vector<int> vl,vr;
int mid=(l+r)>>;
for(int i=l;i<=mid;i++)
{
meteor(i,);
}
for(int i=;i<v.size();i++)
{
sum[v[i]]=;
}
for(int i=;i<v.size();i++)
{
for(int j=;j<sp[v[i]].size() && sum[v[i]]<nd[v[i]];j++)
{
int temp=sp[v[i]][j];
sum[v[i]]+=query(temp);
}
}
for(int i=;i<v.size();i++)
{
if(sum[v[i]]>=nd[v[i]]) vl.push_back(v[i]);
else nd[v[i]]-=sum[v[i]],vr.push_back(v[i]);
}
for(int i=l;i<=mid;i++)
{
meteor(i,-);
}
dfs(vl,l,mid);
dfs(vr,mid+,r);
} void solve()
{
memset(dat,,sizeof(dat));
vector<int> v;
for(int i=;i<=n;i++) v.push_back(i);
dfs(v,,t);
} void print()
{
for(int i=;i<=n;i++)
{
if(ans[i]==t) printf("NIE\n");
else printf("%d\n",ans[i]);
}
} int main()
{
read();
solve();
print();
}