codeforces-Ed94-E

codeforces-Ed94-E

十月 30, 2020

E. String Reversal

  • 题意

给出一个长度为2e5的字符串s

要求只能通过交换相邻字母的操作将它变换成它的镜像字符

如aaaza ->azaaa

问最少要几次操作

  • 题解

首先从s变换成它的镜像t

例如abac ->caba

对于t串的第一个a 它一定从s串的第一个a移动得到

对于第t串的第二个a它一定从s串的第二个a移动得到

因为加入t串中第一个a用s串中第二个a ，第二个a用s串中第一个a

必定会导致在交换获得第二个a时会与前一个a交换位置 但这并不改变串的形态

所以这一步显然多余 为了避免这种情况发生 t串某个字母第几次出现 它就一定是

s串中第几次(从左到右遍历而言)出现的相同字母移动而来

实际上若不避免相同字母相邻互换操作产生的次数

任意一种s->t所需的交换次数是相同的

无论是规定s中第几个a变为t中第几个a，还是先让某个位置的a先移动到达目标位置

找完t中每个字母从s中哪一位字母移动得到后

我们可以得到一个位置下标的映射数组

如abac为[1,2,3,4] -> caba为[4,1,2,3]

那么这个问题就变成了将某个1到n的乱序排列 sort还原成1,2,3,4,5…n的排列

而最小交换相邻元素的次数实际上就是求逆序对个数

求逆序对科技很多 比如用权值线段树 并归排序 甚至字典树处理二进制位

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
#define P pair<ll,ll>
const int Max=2e5+5;
const int Mod=1e9+7;
const int inf=0x3f3f3f3f;


class SegTree{
public:
    #define mid ((L+R)>>1)
    #define Leftson now<<1
    #define Rightson now<<1|1
    struct segtree{int L,R;ll sum;};
    segtree tree[Max<<2];
    void push_up(int now){
        tree[now].sum=tree[Leftson].sum+tree[Rightson].sum;
        return;
    }
    void build(int L,int R,int now=1){
        tree[now]={L,R,0};
        //cout<<L<<" "<<R<<endl;
        if(L==R)return;
        //int mid=(L+R)>>1;
        build(L,mid,Leftson);
        build(mid+1,R,Rightson);
        push_up(now);
        return;
    }
    void updata(int pos,ll val,int now=1){
        if(tree[now].L==tree[now].R){
            tree[now].sum=tree[now].sum+val;
            return;
        }
        if(pos<=tree[Leftson].R)updata(pos,val,Leftson);
        if(pos>=tree[Rightson].L)updata(pos,val,Rightson);
        push_up(now);return;
    }
    ll query(int qL,int qR,int now=1){
        if(qL>qR)return 0;
        if(tree[now].R<=qR&&tree[now].L>=qL)return tree[now].sum;
        ll sum=0;
        if(tree[Leftson].R>=qL)sum+=query(qL,qR,Leftson);
        if(tree[Rightson].L<=qR)sum+=query(qL,qR,Rightson);
        return sum;
    }
}GetInv;

int to[Max];
int main(){
    Turnoff;
    ll n,ans=0;cin>>n;
    string s,t;cin>>s;
    GetInv.build(1,n);
    t=s;reverse(t.begin(),t.end());
    //cout<<t<<endl;
    for(char x='a';x<='z';x++){
        int pos=0;
        for(int i=0;i<n;i++){
            if(t[i]!=x)continue;
            while(pos<n&&s[pos]!=x)pos++;
            if(pos==n)continue;
            to[i]=pos+1;pos++;
        }
    }
    /*
    for(int i=0;i<n;i++)cout<<to[i]<<" ";
    cout<<endl;
    */
    for(int i=0;i<n;i++){
        //cout<<GetInv.query(to[i]+1,n)<<" ";
        ans+=GetInv.query(to[i]+1,n);
        GetInv.updata(to[i],1);
    }
    cout<<ans<<endl;
}