整体二分模板题
不会的这里
首先横跨m的陨石降落可以拆分为不跨过m的两段
我们考虑第L~R场陨石降落，设\(mid=\frac{L+R}{2}\)。
把mid及以前可以完成任务的国家，丢到左边继续二分，不能完成任务的丢到右边继续二分。
当L=R时，此时国家的询问的答案是L。
修改&求和 用树状数组维护就OK；
建议配合代码食用
下面代码去掉了快读
#include<iostream>
#include<cstdio>
#include<vector>
#define LL long long
using namespace std;
int n,m,k;
const int N=600010;
int xu[N],ans[N];
LL tr[N];
vector<int>g[N];
int lowbit(int x){return x&(-x);}
void add(int pos,LL val){for(;pos<=m;pos+=lowbit(pos))tr[pos]+=val;}
LL ask(int pos){LL res=0;for(;pos;pos-=lowbit(pos))res+=tr[pos];return res;}
struct ask
{
int l,r,opt,id;
LL val;
}q[N],q1[N],q2[N];
void work(int s,int t,int l,int r)//s~t询问区间 l~r答案区间
{
if(s>t)return;
if(l==r)
{
for(int i=s;i<=t;++i)
if(q[i].opt==1)ans[q[i].id]=l;
return;
}
int mid=(l+r)>>1,now1=0,now2=0;
for(int i=s;i<=t;++i)
{
if(q[i].opt==1)
{
LL tmp=0,siz=g[q[i].id].size();
for(int j=0;j<siz;++j)
{
tmp+=ask(g[q[i].id][j]);
if(tmp>=q[i].val)break;
}
if(tmp>=q[i].val)q1[++now1]=q[i];
else q[i].val-=tmp,q2[++now2]=q[i];
}
else
{
if(q[i].id<=mid)
{
if(q[i].opt==2)add(q[i].l,q[i].val),add(q[i].r+1,-q[i].val);
else add(1,q[i].val),add(q[i].r+1,-q[i].val),add(q[i].l,q[i].val);
q1[++now1]=q[i];
}
else q2[++now2]=q[i];
}
}
for(int i=s;i<=t;++i)
if(q[i].id<=mid&&q[i].opt!=1)
{
if(q[i].opt==2)
add(q[i].l,-q[i].val),add(q[i].r+1,q[i].val);
else add(1,-q[i].val),add(q[i].r+1,q[i].val),add(q[i].l,-q[i].val);
}
int flag1=0,flag2=0;
for(int i=1;i<=now1;++i)q[s+i-1]=q1[i],flag1=1;
for(int i=1;i<=now2;++i)q[s+now1+i-1]=q2[i],flag2=1；
if(flag1)work(s,s+now1-1,l,mid);
if(flag2)work(s+now1,t,mid+1,r);
}
int main()
{
cin>>n>>m;
for(int i=1;i<=m;++i)g[read()].push_back(i);
for(int i=1;i<=n;++i)xu[i]=read();
cin>>k;
for(int i=1;i<=k;++i)
{
q[i].l=read();q[i].r=read();q[i].val=read();
if(q[i].l<=q[i].r)q[i].opt=2;
else q[i].opt=3;
q[i].id=i;
}
for(int i=1;i<=n;++i){q[i+k].val=xu[i];q[i+k].opt=1;q[i+k].id=i;}//把两种操作混在一起
work(1,k+n,1,k+1);
for(int i=1;i<=n;++i)ans[i]==k+1?printf("NIE\n"):printf("%d\n",ans[i]);
return 0;
}