题解 | #割韭菜#

首先讲ai排序(从小到大)后,后缀一定是不减的.

证明:在没有割草之前这个一定是成立的,假设我有割草,割的高度是b,那么前面的一定小于b,后面=b,然后后面还是比前面长的更快.

由此就产生了一个线段树二分的做法.

上一次被割草的时间day+1,区间内草的增加速度之和spd,区间内左端点的速度nmspd,区间之和sum,区间的两个延迟标记b和d,来延迟更新区间信息.最后还要维护一下左端点的信息nm方便二分查询后缀和.

然后就是做线段树的区间修改和区间查询的功能了.

code:

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N=1e5+5;

struct Seg{
	int l,r;
	ll day,sum,spd,nm,nmspd;
	ll b,d;
}Tr[N<<2];

int a[N],n,m;
void add(int u,ll b,ll d)
{
	Tr[u].day=d+1;
	Tr[u].sum=b*(Tr[u].r-Tr[u].l+1);
	Tr[u].nm=b;
	Tr[u].b=b;
	Tr[u].d=d;
}

void pushup(int u)
{
	Tr[u].day=Tr[u<<1|1].day;
	Tr[u].spd=Tr[u<<1].spd+Tr[u<<1|1].spd;
	Tr[u].nmspd=Tr[u<<1].nmspd;
	Tr[u].sum=Tr[u<<1].sum+Tr[u<<1|1].sum +(Tr[u].day - Tr[u<<1].day) * Tr[u<<1].spd+(Tr[u].day - Tr[u<<1|1].day) * Tr[u<<1|1].spd;
	Tr[u].nm=Tr[u<<1].nm+(Tr[u<<1|1].day-Tr[u<<1].day)*Tr[u<<1].nmspd;
}

void pushdown(int u)
{
	if(Tr[u].d)
	{
		add(u<<1,Tr[u].b,Tr[u].d);
		add(u<<1|1,Tr[u].b,Tr[u].d);
		Tr[u].d=Tr[u].b=0;
	}
}

void build(int u,int L,int R)
{
	Tr[u].l=L,Tr[u].r=R,Tr[u].day=1,Tr[u].sum=Tr[u].nm=0,Tr[u].b=Tr[u].d=0;
	if(L==R)
	{
		Tr[u].spd=a[L];
		Tr[u].nmspd=a[L];
		return;
	}
	int mid=(L+R)>>1;
	build(u<<1,L,mid);
	build(u<<1|1,mid+1,R);
	pushup(u);
}

void change(int u,int L,int R,ll b,ll d)
{
	if(Tr[u].l>R||Tr[u].r<L)	return;
	if(L<=Tr[u].l&&Tr[u].r<=R)
	{
		add(u,b,d);
		return;
	}
	pushdown(u);
	change(u<<1,L,R,b,d);
	change(u<<1|1,L,R,b,d);
	pushup(u);
}

ll query(int u,int L,int R,ll b,ll d)
{
	//cout<<u<<' '<<L<<' '<<R<<' '<<endl;
	if(L>Tr[u].r||R<Tr[u].l)	return 0;
	if(Tr[u].l>=L&&Tr[u].r<=R)
	{
		return Tr[u].sum+(d-Tr[u].day+1)*Tr[u].spd-b*(Tr[u].r-Tr[u].l+1);
	}
	pushdown(u);
	return query(u<<1,L,R,b,d)+query(u<<1|1,L,R,b,d);
}

int ask(int u,ll b,ll d)
{
	if(Tr[u].l==Tr[u].r)
	{
		if(Tr[u].nm+(d-Tr[u].day+1)*Tr[u].nmspd>b)	return Tr[u].l;
		else										return Tr[u].l+1;
	}
	pushdown(u);
	if(Tr[u<<1|1].nm+(d-Tr[u<<1|1].day+1)*Tr[u<<1|1].nmspd>b)	return ask(u<<1,b,d);
	else														return ask(u<<1|1,b,d);
}

void run()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)	scanf("%d",&a[i]);
	sort(a+1,a+1+n);
	build(1,1,n); 
	while(m--)
	{
		ll B,D;
		scanf("%lld%lld",&D,&B);
		int st=ask(1,B,D);
		//cout<<st<<endl;
		printf("%lld\n",query(1,st,n,B,D));
		change(1,st,n,B,D);
	}
}

int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		run();
	}
	return 0;
}