本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-09-15 07:51:05

思路

发现由于移动时不能让两人在同一位置，所以所有人的相对顺序不会改变，同时移动时若旁边已经有人，还可能需要带上别的人一起动。

考虑把相邻的人看成一个整块一起移动，初始每个人各为一个块，移动时暴力向目标方向走，接上下一个块就合成一个整块接着走，直到到达终点。

具体维护时可以在 set 中维护 $(p_i,x_i)$ 表示一个从 $p_i$ 开始的整块，此时 $p_i$ 的位置为 $x_i$。每个块的右端点和长度可以结合下一个块的左端点来计算，具体操作还是看代码实现吧。

时间复杂度上由于每次操作只可能从一个整块中分出一个含 $T_i$ 的小块，总块数不超过 $S=N+Q$，合并的次数不超过总块数，所以时间复杂度是 $O(S\log S)$ 的。

代码

#include<iostream>
#include<set>
#define int long long
#define pii pair<int,int>
using namespace std; 
const int N=4e5+10;
const int inf=1e18;
int n,Q,res;
set <pii> s;
signed main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1,x;i<=n;i++) cin>>x,s.insert({i,x});
	s.insert({0,-inf}),s.insert({n+1,inf}),cin>>Q; \/\/ 处理边界 
	while(Q--)
	{
		int p,to; cin>>p>>to;
		pii te=*--s.upper_bound({p,inf}); s.erase(te); \/\/ p 所在的整块 
		int lp=te.first,lx=te.second,nowx=lx+(p-lp),nlp=(*s.upper_bound(te)).first; \/\/ lp 为左端点人的编号，lx 为位置 
		if(to<nowx) \/\/ 向左走 
		{
			if(p+1!=nlp) s.insert({p+1,nowx+1}),nlp=p+1; \/\/ 拆块 
			to-=(p-lp); \/\/转化为左端点移动到的位置 
			while(lx!=to)
			{
				pii tt=*(--s.upper_bound({lp,lx})); \/\/ 左边的块 
				int tp=tt.first,tx=tt.second,lim=tx+(lp-tp),tto=max(to,lim);
				res+=(nlp-lp)*(lx-tto),lx=tto;  
				if(lx==lim) s.erase(tt),to-=(lp-tp),lp=tp,lx=tx; \/\/ 合并 
			}
		}
		else \/\/向右走 
		{
			if(p!=lp) s.insert({lp,lx}),lp=p,lx=nowx; \/\/ 拆块 
			while(lx!=to)
			{
				pii tt=*(s.upper_bound({lp,lx})); \/\/ 右边的块 
				int np=tt.first,nx=tt.second,lim=nx-(np-lp),tto=min(to,lim);
				res+=(np-lp)*(tto-lx),lx=tto;
				if(lx==lim) s.erase(tt); \/\/ 合并 
			}
		}
		s.insert({lp,lx}); \/\/把目前的块重新加入集合 
	}
	cout<<res;
	return 0;
}