自动搬运

查看原文

来自洛谷，原作者为

	fletmer **

搬运于2025-08-24 21:49:13，当前版本为作者最后更新于2018-08-07 21:20:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

友情提醒，不要试图看楼上的题解的代码，否则你会弃题而走的，不是很明白为什么他能写这么多

关键思想就是通过使用树状数组来维护数列，达到消除后效性的效果。具体看代码注释，这里说一下对方案的记录：

1.第一次记录很简单，关键在于后面的几次，因为有一个问题就是中间被消掉了很多块，所以某个数字的序号可能会改变。所以定义了一个hsb去记录已消的元素个数。由于 | 已经被消的元素 | 一定是 | 当前计算的元素 | 前的元素，所以直接减去就好了。

2.由于两个相同元素之间可能不止隔了一个元素，所以循环去填方案：

dis相同元素的距离，t为当前计算的元素，hsb为当前元素前已被消除的元素

int t=i,dis=Query(i-1)-Query(v[s[i]]);
while(dis) stp[++cnt]=t-1-hsb,t--,dis--;

3.算了多一句嘴，使用树状数组为啥会使后效被消除？

有几种情况

第一种： 1.....1 2.....2这样先消1和先消2一样

第二种：1212 同上，并且只用消一个

第三种： 1 2 ....2 1 显然先消2更优

其中第三种情况，每次交换为了缩短相同元素的距离，都会把无关的后调，树状数组是直接把相同的元素给消除了，对其它元素的影响就是：

1. 没影响

2. 相同元素距离缩短

自行理解吧，还是好懂的

#include <iostream>
#include <cstdio>
#include <algorithm>
#define SIZE 50010
#define lowbit(x) x&(-x)
#define LL long long
using namespace std;

LL n,ans,cnt,hsb;
LL tr[2*SIZE],v[2*SIZE],s[2*SIZE],stp[1000005];

//树状数组不解释
inline void Add(int x,int y){
	//注意这里是2*n不是n
	for( ;x<=2*n;x+=lowbit(x)) tr[x]+=y;
}
inline LL Query(int x){
	LL sum=0;
	for( ;x;x-=lowbit(x)) sum+=tr[x];
	return sum;
}

int main(){
	cin>>n;
    
    //初始化
	for(int i=1;i<=2*n;i++) cin>>s[i],Add(i,1);
	for(int i=1;i<=2*n;i++){
    	//如果遇的元素为第一次遇到，记录其位置
		if(!v[s[i]]) v[s[i]]=i;
        //如果不是第一次遇到
		else{
        	//统计步数，中间有几个，就要交换几回
			ans+=Query(i)-Query(v[s[i]])-1;
			int t=i,dis=Query(i-1)-Query(v[s[i]]);
			while(dis) stp[++cnt]=t-1-hsb,t--,dis--;
            //消除影响
			Add(v[s[i]],-1); Add(i,-1); 
            hsb+=2; //一次合并消两个元素
		}
	}
    
    //输出方案不解释
	printf("%lld\n",ans);
	for(int i=1;i<=cnt;i++) printf("%lld\n",stp[i]);
	
	return 0;
}