题解 P3460 【[POI2007]TET-Tetris Attack】

· · 题解

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

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

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;
}