整体二分模板题

不会的这里

首先横跨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;
}