题目传送门
这题的整体二分还是挺好想到的，代码也挺好写的。（比BZOJ3110好写多……）
取当期的陨石波数的一半加入树状数组中，判断当前每个国家拥有的陨石数是否达到需求量，若达到则放到左区间中，也就是减小陨石数，反之则放到右区间，增加陨石数。
orzZH大佬，当讲课人在上面放出了这道题时，ZH大佬瞟了一眼，哼了一声：“这题不是水题吗？还需要讲？”
ZH大佬太强啦QWQ，%%%%%，献上我的膝盖骨——跪膜大佬。
附上AC代码：
#include <cstdio> #include <cctype> #define N 300010 #define lowbit(x) ((x)&(-x)) using namespace std; struct side{int to,nt;}s[N]; struct note{long long w,wz;}a[N],q1[N],q2[N]; struct ask{long long l,r,w;}q[N]; long long n,m,x,h[N],num,p,ans[N],t[N]; inline char nc(){ static char ch[100010],*p1=ch,*p2=ch; return p1==p2&&(p2=(p1=ch)+fread(ch,1,100010,stdin),p1==p2)?EOF:*p1++; } inline void read(long long &a){ static char ch=nc();int f=1; for (;!isdigit(ch);ch=nc()) if (ch=='-') f=-1; for (a=0;isdigit(ch);a=a*10+ch-'0',ch=nc()); a*=f;return; } inline void add(int x,int y){s[++num]=(side){y,h[x]},h[x]=num;} inline void updata(int x,long long w){for (int i=x; i<=n; i+=lowbit(i)) t[i]+=w;} inline void change(int now,int ww){ for (int i=now; i<=m; i+=lowbit(i)) t[i]+=ww; } inline void updata(int l,int r,long long w){ if (l>r) change(l,w),change(1,w),change(r+1,-w); else change(l,w),change(r+1,-w); } inline long long query(int now){ long long ret=0; for (int i=now; i; i-=lowbit(i)) ret+=t[i]; return ret; } inline void so(int l,int r,int ql,int qr){ if (l>r) return; if (ql==qr){ for (int i=l; i<=r; ++i) ans[a[i].wz]=ql; return; } int mid=(ql+qr)>>1,ll=0,rr=0,len=l; for (int i=ql; i<=mid; ++i) updata(q[i].l,q[i].r,q[i].w); for (int i=l; i<=r; ++i){ long long sum=0; for (int j=h[a[i].wz]; j; j=s[j].nt){ sum+=query(s[j].to); if (sum>=a[i].w) break; } if (sum>=a[i].w) q1[++ll]=a[i]; else q2[++rr]=a[i],q2[rr].w-=sum; } for (int i=1; i<=ll; ++i) a[len++]=q1[i]; for (int i=1; i<=rr; ++i) a[len++]=q2[i]; for (int i=ql; i<=mid; ++i) updata(q[i].l,q[i].r,-q[i].w); return so(l,l+ll-1,ql,mid),so(l+ll,r,mid+1,qr); } int main(void){ read(n),read(m); for (int i=1; i<=m; ++i) read(x),add(x,i); for (int i=1; i<=n; ++i) read(a[i].w),a[i].wz=i; read(p); for (int i=1; i<=p; ++i) read(q[i].l),read(q[i].r),read(q[i].w); so(1,n,1,p+1); for (int i=1; i<=n; ++i) if (ans[i]>p) puts("NIE"); else printf("%d\n",ans[i]); return 0; }