Luogu

分析

设第 $i$ 个数的两个出现位置为 $a_i,b_i$。可以发现,若 $(a_i,b_i)$ 中有 $x$ 个数还没有消去,那么要把 $i$ 消去的代价为 $x$。

于是我们可以从前往后扫,如果当前的数是第一次出现就在这个位置 $+1$,否则将答案加上 $(a_i,b_i)$ 的区间和并把 $a_i-1$ 。用树状数组维护这个过程即可。

输出方案在扫的过程中顺便搞一下就好了。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int n,a[N],l[N];
vector<int> op;

int c[N];
inline void add(int x,int y) { for (;x<=n<<1;x+=x&-x) c[x]+=y; }
inline int query(int x) { int s=0; for (;x;x-=x&-x) s+=c[x]; return s; }

int main() {
    n=read(); int ans=0;
    for (re int i=1;i<=n<<1;++i) a[i]=read();
    for (re int i=1,s=0;i<=n<<1;++i) {
        if (!l[a[i]]) add(i,1),l[a[i]]=i;
        else {
            int now=query(i-1)-query(l[a[i]]); ans+=now;
            for (re int t=i;now;--now,--t) op.push_back(t-1-s);
            add(l[a[i]],-1),s+=2;
        }
    }
    printf("%d\n",ans);
    for (re int i:op) printf("%d\n",i);
    return 0;
}
最后修改:2019 年 10 月 24 日 09 : 28 PM