AtCoder Regular Contest 088 E - Papple Sort（树状数组+结论） - JavaScript

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

结论：每次把字符丢到最外面最优，用树状数组统计答案，把字符放到最外边后可以当成消失了，直接在树状数组上删掉就好。

感性理解是把字符丢到中间会增加其他字符的移动次数，但是丢到外面不会，所以是正确的。

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#define ll long long

using namespace std;

const int maxn=;

int n, x, num;

int cnt[maxn], tree[maxn], pos[][maxn];

ll ans;

char s[maxn];

bool v[maxn];

inline void add(int x, int delta){for(;x<=n;x+=x&-x) tree[x]+=delta;}

inline int query(int x){int sum=; for(;x;x-=x&-x) sum+=tree[x]; return sum;}

int main()

{

    scanf("%s", s+); n=strlen(s+);

    for(int i=;i<=n;i++) cnt[x=s[i]-'a']++, pos[x][++pos[x][]]=i, tree[i]=i&-i;

    for(int i=;i<;i++) if(cnt[i]&) num++;

    if(num>) return puts("-1"), ;

    for(int i=;i<=n;i++)

    if(!v[i])

    {

        int x=s[i]-'a', nxt=pos[x][pos[x][]--];

        if(i==nxt) ans+=(query(n)-query(i))>>;

        else ans+=query(n)-query(nxt);

        add(i, -); add(nxt, -); v[i]=v[nxt]=;

    }

    printf("%lld\n", ans);

}