洛谷题目传送门 BZOJ题目传送门
整体二分第一题
把所有国家一起进行二分，每次做1-mid的修改操作，把达成的放在左边，没有达成的放在右边，然后分治下去。
详见代码：
#include<cctype> #include<cstdio> #include<cstring> #include<algorithm> #define N 300005 #define F inline #define inf 0x7fffffff using namespace std; typedef long long LL; struct edge{ int next,to; }ed[N]; struct que{ int l,r,v; }q[N]; int n,m,k,p,ti,h[N],id[N],a[N],tem[N],ans[N]; LL t[N],i; bool f[N]; F char readc(){ static char buf[100000],*l=buf,*r=buf; if (l==r) r=(l=buf)+fread(buf,1,100000,stdin); if (l==r) return EOF; return *l++; } F int _read(){ int x=0,f=1; char ch=readc(); while (!isdigit(ch)) { if (ch=='-') f=-1; ch=readc(); } while (isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=readc(); return x*f; } F void writec(int x){ if (x>9) writec(x/10); putchar(x+48); } F void _write(int x){ writec(x),putchar('\n'); } //以上为IO优化 #define lbt(x) (x&(-x)) F void nsrt(int x,int p){ for (;x<=m;t[x]+=p,x+=lbt(x)); } F void mdfy(int l,int r,int v){ nsrt(l,v),nsrt(r+1,-v); if (l>r) nsrt(1,v); } F LL srch(int x){ for (i=0;x;i+=t[x],x-=lbt(x)); return i; } //以上为树状数组 F void addedge(int x,int y){ ed[++k]=(edge){h[x],y},h[x]=k; } //建边表示当前结点属于的国家 F void ef(int hd,int tl,int l,int r){//整体二分 //当前处理的国家为[hd,tl]，修改区间为[l,r] if (hd>tl) return; int mid=l+r>>1,num=0,x; LL sum; if (l==r){ for (int i=hd;i<=tl;i++) ans[id[i]]=l; return; } //如果修改区间相等则得到答案 while (ti<=mid) ti++,mdfy(q[ti].l,q[ti].r,q[ti].v); while (ti>mid) mdfy(q[ti].l,q[ti].r,-q[ti].v),ti--; //做1-mid的修改 for (int i=hd;i<=tl;i++){//计算每个国家经过mid个修改后能否达到要求 x=id[i],sum=0; for (int j=h[x];j;j=ed[j].next){ sum+=srch(ed[j].to); if (sum>=a[x]) break;//要及时break，据说会爆long long } if (sum>=a[x]) f[x]=true,num++; else f[x]=false;//满足的放左边，不满足的放右边 } int l1=hd,l2=hd+num; for (int i=hd;i<=tl;i++) if (f[id[i]]) tem[l1++]=id[i]; else tem[l2++]=id[i]; for (int i=hd;i<=tl;i++) id[i]=tem[i]; ef(hd,l1-1,l,mid),ef(l1,l2-1,mid+1,r);//继续分治 } int main(){ n=_read(),m=_read(); for (int i=1;i<=m;i++) addedge(_read(),i); for (int i=1;i<=n;i++) a[i]=_read(),id[i]=i; p=_read(); for (int i=1;i<=p;i++) q[i].l=_read(),q[i].r=_read(),q[i].v=_read(); q[++p]=(que){1,m,inf},ef(1,n,1,p); for (int i=1;i<=n;i++) if (ans[i]!=p) _write(ans[i]); else puts("NIE"); return 0; }