标签：整体二分，树状数组
题目
Description
Byteotian Interstellar Union有N个成员国。现在它发现了一颗新的星球，这颗星球的轨道被分为M份（第M份和第1份相邻），第i份上有第Ai个国家的太空站。
这个星球经常会下陨石雨。BIU已经预测了接下来K场陨石雨的情况。
BIU的第i个成员国希望能够收集Pi单位的陨石样本。你的任务是判断对于每个国家，它需要在第几次陨石雨之后，才能收集足够的陨石。
输入
第一行是两个数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单位的陨石样本。
输出
N行。第i行的数Wi表示第i个国家在第Wi波陨石雨之后能够收集到足够的陨石样本。
如果到第K波结束后仍然收集不到，输出NIE。
数据范围
1<=n,m,k<=3 * 10^5 1<=Pi<=10^9 1<=Ai<10^9
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
题意
给定一个环，每个节点有一个所属国家，k次事件，每次对[l,r]区间上的每个点点权加上一个值，求每个国家最早多少次操作之后所有点的点权和能达到一个值
分析
整体二分的基础练手题
离线操作，对于每个国家来说，答案是可二分的
把所有国家整体二分，用树状数组维护修改操作
然后把已经满足条件的答案放在l->mid，还没满足的放在mid+1->r
之后继续向下分治
code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
#define inf 1e9
using namespace std;
inline ll read()
{
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=3e5+6;
int n,m,K,T,l[maxn],r[maxn],val[maxn];
int p[maxn],id[maxn],tmp[maxn],ans[maxn];
vector<int> a[maxn];ll t[maxn];
bool mark[maxn];
ll query(int x){ll re=0;for(int i=x;i;i-=i&-i)re+=t[i];return re;}
void modify(int x,int val){if(x>m)return;for(int i=x;i<=m;i+=i&-i)t[i]+=val;}
void opera(int k,int f){
if(l[k]<=r[k])modify(l[k],f*val[k]),modify(r[k]+1,f*(-val[k]));
else modify(1,f*val[k]),modify(r[k]+1,f*(-val[k])),modify(l[k],f*val[k]);
}
void solve(int l,int r,int L,int R){
if(l>r)return;
if(L==R){
rep(i,l,r)ans[id[i]]=L;
return;
}
int mid=(L+R)>>1;
while(T<=mid)T++,opera(T,1);
while(T>mid)opera(T,-1),T--;
int cnt=0,now;ll tot;
rep(i,l,r){
tot=0;now=id[i];
for(int j=0;j<a[now].size();j++){
tot+=query(a[now][j]);
if(tot>=p[now])break;
}
if(tot>=p[now])mark[now]=1,cnt++;else mark[now]=0;
}
int l1=l,l2=l+cnt;
rep(i,l,r)
if(mark[id[i]])tmp[l1++]=id[i];else tmp[l2++]=id[i];
rep(i,l,r)id[i]=tmp[i];
solve(l,l1-1,L,mid);solve(l1,l2-1,mid+1,R);
}
int main()
{
n=read(),m=read();
rep(i,1,m){int x=read();a[x].push_back(i);}
rep(i,1,n)p[i]=read();
K=read();
rep(i,1,K)l[i]=read(),r[i]=read(),val[i]=read();
K++;l[K]=1;r[K]=m;val[K]=inf;
rep(i,1,n)id[i]=i;
solve(1,n,1,K);
rep(i,1,n)
if(ans[i]!=K)printf("%d\n",ans[i]);else puts("NIE");
return 0;
}
