Description
给定一个环，每个节点有一个所属国家，k次事件，每次对[l,r]区间上的每个点点权加上一个值，求每个国家最早多少次操作之后所有点的点权和能达到一个值
Solution
整体二分，维护一个区间修改单点查询的树状数组来统计mid次操作后每个国家收集到的陨石
要判定最后也收集不够的国家，可以加一场1-m大小为INF的流星雨，如果ans==k+1输出"NIE"
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<vector> #define INF 0x3f3f3f3f #define MAXN 300005 using namespace std; typedef long long LL; int n,m,k,p[MAXN],id[MAXN],t[MAXN]; int x[MAXN],y[MAXN],A[MAXN],ans[MAXN],T=0; LL c[MAXN]; bool vis[MAXN]; vector<int>a[MAXN]; int read() { int x=0,f=1;char c=getchar(); while(c<'0'||c>'9'){ if(c=='-')f=-1;c=getchar(); } while(c>='0'&&c<='9'){ x=x*10+c-'0';c=getchar(); } return x*f; } int lowbit(int x){return x&-x;} void add(int pos,int x) { while(pos<=m) c[pos]+=x,pos+=lowbit(pos); } LL query(int pos) { LL res=0; while(pos>0) res+=c[pos],pos-=lowbit(pos); return res; } void insert(int pos,int f) { if(x[pos]<=y[pos]) add(x[pos],f*A[pos]),add(y[pos]+1,-f*A[pos]); else add(1,f*A[pos]),add(y[pos]+1,-f*A[pos]),add(x[pos],f*A[pos]); } void solve(int l,int r,int L,int R) { if(L>R)return; if(l==r) { for(int i=L;i<=R;i++)ans[id[i]]=l; return; } int Mid=(l+r)>>1; while(T<Mid)++T,insert(T,1); while(T>Mid)insert(T,-1),--T; int cnt=0,idx; LL res; for(int i=L;i<=R;i++) { res=0,idx=id[i]; for(int j=0;j<a[idx].size();j++) { res+=query(a[idx][j]); if(res>=p[idx])break; } if(res>=p[idx])vis[idx]=1,cnt++; else vis[idx]=0; } int j=L,k=L+cnt; for(int i=L;i<=R;i++) if(vis[id[i]])t[j++]=id[i]; else t[k++]=id[i]; for(int i=L;i<=R;i++)id[i]=t[i]; solve(l,Mid,L,L+cnt-1); solve(Mid+1,r,L+cnt,R); } int main() { n=read(),m=read(); for(int i=1;i<=m;i++) { int o=read(); a[o].push_back(i); } for(int i=1;i<=n;i++)p[i]=read(),id[i]=i; k=read(); for(int i=1;i<=k;i++) x[i]=read(),y[i]=read(),A[i]=read(); x[++k]=1,y[k]=m,A[k]=INF; solve(1,k,1,n); for(int i=1;i<=n;i++) if(ans[i]==k)printf("NIE\n"); else printf("%d\n",ans[i]); return 0; }