C++ 解法, 执行用时: 324ms, 内存消耗: 62216K, 提交时间: 2021-07-10 15:08:57

#include<bits/stdc++.h>
using namespace std;
const int M=1e5+5,P=1e9+7,qwq=10;
int n,m;
int base[M],A[M];
int root[M],tot;
int sum[M*40],Ls[M*40],Rs[M*40],val[M*40];
int ans[M];
void build(int &rt,int L,int R){
	rt=++tot;
	if(L==R){
		sum[rt]=1ll*A[L]*base[L-1]%P;
		val[rt]=A[L];
		return;
	}
	int mid=L+R>>1;
	build(Ls[rt],L,mid);
	build(Rs[rt],mid+1,R);
	sum[rt]=(sum[Ls[rt]]+sum[Rs[rt]])%P;
}
void update(int &rt,int pt,int x,int a,int b,int L,int R){
	rt=++tot;
	sum[rt]=(sum[pt]+a)%P;
	Ls[rt]=Ls[pt],Rs[rt]=Rs[pt];
	if(L==R){
		val[rt]=val[pt]+b;
		return;
	}
	int mid=L+R>>1;
	if(x<=mid)update(Ls[rt],Ls[pt],x,a,b,L,mid);
	else update(Rs[rt],Rs[pt],x,a,b,mid+1,R);
}
bool cmp(int a,int b){
	if(sum[root[a]]==sum[root[b]])return a<b;
	int L=1,R=n;
	int ra=root[a],rb=root[b];
	while(L!=R){
		int mid=L+R>>1;
		if(sum[Ls[ra]]==sum[Ls[rb]]){
			L=mid+1;
			ra=Rs[ra],rb=Rs[rb];
		}else {
			R=mid;
			ra=Ls[ra],rb=Ls[rb];
		}
	}
	return val[ra]<val[rb];
}
int main(){
	scanf("%d %d",&n,&m);
	base[0]=1;
	for(int i=1;i<=n;i++){
		base[i]=1ll*base[i-1]*qwq%P;
		scanf("%d",&A[i]);
	}
	build(root[0],1,n);
	ans[0]=0;
	for(int i=1;i<m;i++){
		int x,y;
		scanf("%d %d",&x,&y);
		update(root[i],root[i-1],x,(1ll*(A[y]-A[x])*base[x-1]%P+P)%P,A[y]-A[x],1,n);	
		update(root[i],root[i],y,(1ll*(A[x]-A[y])*base[y-1]%P+P)%P,A[x]-A[y],1,n);
		swap(A[x],A[y]);
		ans[i]=i;
	}
	sort(ans,ans+m,cmp);
	for(int i=0;i<m;i++)printf("%d ",ans[i]);
	return 0;
}