静态逆序对

「洛谷」P1908

经典做法

考虑给定一个值不变的数组，怎么求出逆序对数量？
经典的做法是归并排序，另一种做法就是利用线段树或者树状数组，每次插入一个数询问其对答案的贡献
元素值太大时注意要离散化或者动态开点
这里先贴一份动态开点的代码

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
#include <bits/stdc++.h>
using namespace std;

const int maxn=1e7+5;
#define ll long long

struct Tree
{
    int cnt,ls[maxn],rs[maxn],sum[maxn];

    int query(int rt,int ql,int qr,int l=1,int r=1e9)
    {
        if(!rt) return 0;
        if(l==ql && r==qr) return sum[rt];
        int mid=(l+r)>>1;
        if(qr<=mid) return query(ls[rt],ql,qr,l,mid);
        if(ql>=mid+1) return query(rs[rt],ql,qr,mid+1,r);
        return query(ls[rt],ql,mid,l,mid)+query(rs[rt],mid+1,qr,mid+1,r);
    }

    void add(int &rt,int pos,int val,int l=1,int r=1e9)
    {
        if(!rt) rt=++cnt;
        if(l==r){sum[rt]+=val;return;}
        int mid=(l+r)>>1;
        if(pos<=mid) add(ls[rt],pos,val,l,mid);
        else add(rs[rt],pos,val,mid+1,r);
        sum[rt]=sum[ls[rt]]+sum[rs[rt]];
    }
}T;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    int n;cin>>n;
    ll ans=0;
    int rt=0;
    for(int i=1;i<=n;i++)
    {
        int x;cin>>x;
        ans+=T.query(rt,x+1,1e9);
        T.add(rt,x,1);
    }
    cout<<ans;
    return 0;
}

字典树

那能否用字典树来求逆序对？答案是显然的
我们设 $val$ 为元素大小，$pos$ 为元素位置
我们把所有数插入一棵字典树中，那么对于一个节点，他的左儿子中的 $val$ 一定小于右儿子的 $val$，所以我们只需要统计左儿子中的 $pos$ 大于右儿子中的 $pos$ 的元素个数，累加即可
注意这样求出的逆序对的两个元素分别位于两棵子树，那位于同一棵子树中的逆序对数怎么求解？
按照 $CDQ$ 分治的思想，递归解决即可
注意这种写法如果题目给的空间很小，很容易 $MLE$

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
#include <bits/stdc++.h>
using namespace std;

const int maxn=5e5+5;
const int maxd=35;
#define ll long long

ll Ans;

struct Trie
{
    int cnt=0;
    int ch[maxn*maxd][2];
    vector<int>vec[maxn*maxd];

    void insert(ll x,int pos)
    {   
        int rt=0;
        for(int i=30;i>=0;i--)
        {
            int v=(x>>i)&1;
            int &now=ch[rt][v];
            if(!now) now=++cnt;
            vec[now].push_back(pos);
            rt=now;
        }
    }

    void dfs(int pos,int rt)
    {
        int ls=ch[rt][0],rs=ch[rt][1];
        if(ls) dfs(pos-1,ls);
        if(rs) dfs(pos-1,rs);

        int r=0;
        int lsize=vec[ls].size();
        int rsize=vec[rs].size();
        for(int l=0;l<lsize;l++)
        {
            while(r<rsize && vec[ls][l]>vec[rs][r]) r++;
            Ans+=r;
        }
    }
}T;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    int n;cin>>n;
    for(int x,i=1;i<=n;i++) cin>>x,T.insert(x,i);
    T.dfs(30,0);
    cout<<Ans;
    return 0;
}

动态逆序对

「洛谷」P3157

CDQ分治

现在这个数组变成动态的了，最初的逆序对数很容易求出，但难点就在于删除元素
删除一个元素很简单，只需要统计前面比它大和后面比它小的元素个数即可，但删除多个呢
一种很经典的解法是 $CDQ$ 分治
我们用一个三元组 $(time,val,pos)$ 来表示一个元素，$time$ 表示元素被删除的时间，$val$ 表示元素的值，$pos$ 表示元素的位置
那么能和元素j组成逆序对的元素i必须满足
$time_i < time_j$，$pos_i < pos_j$，$val_i > val_j$
或者 $time_i < time_j$，$pos_i > pos_j$，$val_i < val_j$
这就变成了经典的三维偏序问题

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;

const int maxn=2e5+5;
#define ll long long

int n,m;
struct BIT
{
    ll sum[maxn];
    #define lowbit(x) (x&-x)

    void add(int x,int val)
    {
        while(x<=n) sum[x]+=val,x+=lowbit(x);
    }

    ll query(int x)
    {
        int res=0;
        while(x) res+=sum[x],x-=lowbit(x);
        return res;
    }
}T;

struct Node
{
    int op,v,p,id,t;
    bool operator < (Node &B){return p<B.p;}
}A[maxn];
int cnt,val[maxn],pos[maxn];
ll ans[maxn];

void deal(int l,int r)
{
    if(l==r) return;
    int mid=(l+r)>>1;
    deal(l,mid);deal(mid+1,r);
    sort(A+l,A+mid+1);
    sort(A+mid+1,A+r+1);

    int j=l;
    for(int i=mid+1;i<=r;i++)
    {
        while(j<=mid && A[j].p<=A[i].p) T.add(A[j].v,A[j].op),j++;
        ans[A[i].id]+=(T.query(n)-T.query(A[i].v))*A[i].op;
    }
    for(int i=l;i<j;i++) T.add(A[i].v,-A[i].op);
    j=mid;
    for(int i=r;i>=mid+1;i--)
    {
        while(j>=l && A[j].p>=A[i].p) T.add(A[j].v,A[j].op),j--;
        ans[A[i].id]+=T.query(A[i].v-1)*A[i].op;
    }
    for(int i=mid;i>j;i--) T.add(A[i].v,-A[i].op);
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>val[i];
        pos[val[i]]=i;
        A[++cnt]=(Node){1,val[i],i,0,cnt};
    }
    for(int i=1;i<=m;i++)
    {
        int x;cin>>x;
        A[++cnt]=(Node){-1,x,pos[x],i,cnt};
    }
    deal(1,cnt);
    for(int i=1;i<=m;i++) ans[i]+=ans[i-1];
    for(int i=0;i<m;i++) cout<<ans[i]<<'\n';
    return 0;
}

带修主席树

很显然，$CDQ$ 分治只能离线处理，如果要求强制在线呢？
回顾删除一个元素的过程，删除一个元素，只需要统计前面比它大和后面比它小的元素个数即可
很明显的区间查询问题，主席树可做
那么要修改呢，当然是带修主席树，也就是树状数组套线段树

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <bits/stdc++.h>
using namespace std;

const int maxn=1e5+5;
const int maxm=1e3+5;
#define ll long long

struct Tree
{
    int RT[maxn],Ncnt,Top;
    int L[maxn],R[maxn],Lcnt,Rcnt;
    int ls[maxn<<7],rs[maxn<<7],sum[maxn<<7];
    vector<int>TL[maxm],TR[maxm];

    int limit;
    inline int lowbit(int x){return x&(-x);}

    void update(int &rt,int l,int r,int x,int v)
    {
        if(!rt) rt=++Ncnt;
        sum[rt]+=v;
        if(l==r) return;
        int mid=(l+r)>>1;
        if(x<=mid) update(ls[rt],l,mid,x,v);
        else update(rs[rt],mid+1,r,x,v);
    }

    inline void add(int pos,int x,int v)
    {
        for(int i=pos;i<=limit;i+=lowbit(i)) update(RT[i],1,limit,x,v);
    }

    int query(int ql,int qr,int l,int r)
    {
        int res=0,mid=(l+r)>>1;
        for(int i=1;i<=Lcnt;i++) res-=sum[L[i]];
        for(int i=1;i<=Rcnt;i++) res+=sum[R[i]];
        if(ql==l && qr==r) return res;

        if(qr<=mid)
        {
            for(int i=1;i<=Lcnt;i++) L[i]=ls[L[i]];
            for(int i=1;i<=Rcnt;i++) R[i]=ls[R[i]];
            return query(ql,qr,l,mid);
        }
        else if(ql>=mid+1)
        {
            for(int i=1;i<=Lcnt;i++) L[i]=rs[L[i]];
            for(int i=1;i<=Rcnt;i++) R[i]=rs[R[i]];
            return query(ql,qr,mid+1,r);
        }
        else
        {
            res=0;
            int now=Top++;
            TL[now].clear();TR[now].clear();
            for(int i=1;i<=Lcnt;i++) TL[now].push_back(L[i]);
            for(int i=1;i<=Rcnt;i++) TR[now].push_back(R[i]);

            for(int i=1;i<=Lcnt;i++) L[i]=ls[TL[now][i-1]];
            for(int i=1;i<=Rcnt;i++) R[i]=ls[TR[now][i-1]];
            res+=query(ql,mid,l,mid);

            for(int i=1;i<=Lcnt;i++) L[i]=rs[TL[now][i-1]];
            for(int i=1;i<=Rcnt;i++) R[i]=rs[TR[now][i-1]];
            res+=query(mid+1,qr,mid+1,r);
            return res;
        }
    }

    int ask(int l,int r,int ql,int qr)
    {
        if(ql>qr || l>r) return 0;
        Lcnt=Rcnt=Top=0;
        for(int i=l-1;i;i-=lowbit(i)) L[++Lcnt]=RT[i];
        for(int i=r;i;i-=lowbit(i)) R[++Rcnt]=RT[i];
        return query(ql,qr,1,limit);
    }
}T;

int pos[maxn];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    int n,m;
    cin>>n>>m;
    ll ans=0;
    T.limit=n;
    for(int i=1;i<=n;i++)
    {
        int x;cin>>x;
        pos[x]=i;
        ans+=T.ask(1,i-1,x+1,n);
        T.add(i,x,1);
    }
    for(int i=1;i<=m;i++)
    {
        int x;cin>>x;
        cout<<ans<<'\n';
        ans-=T.ask(1,pos[x]-1,x+1,n);
        ans-=T.ask(pos[x]+1,n,1,x-1);
        T.add(pos[x],x,-1);
    }
    return 0;
}

字典树套树状数组

再回顾一下前面被卡空间的字典树做法，这道题给的空间相对来说大了很多
于是我们可以对字典树上的每一个节点开一个树状数组，同时进行离散化
也就是字典树套树状数组
显然，这种做法也不能强制在线，因为要分配空间，所以说，主席树大法好

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <bits/stdc++.h>
using namespace std;

const int maxn=1e5+5;
const int maxm=1e7+5;
const int maxd=35;
#define ll long long

ll Ans;
int Pos[maxn],result[maxm];
int *POS;

struct BIT
{
    int *sum,lim;
    #define lowbit(x) (x&-x)

    void add(int x,int val)
    {
        while(x<=lim) sum[x]+=val,x+=lowbit(x);
    }

    int query(int x)
    {
        int res=0;
        while(x) res+=sum[x],x-=lowbit(x);
        return res;
    }
}N[maxn*maxd];

struct Trie
{
    int cnt=0;
    int ch[maxn*maxd][2];
    vector<int>vec[maxn*maxd];

    void insert(ll x,int pos)
    {
        int rt=0;
        for(int i=30;i>=0;i--)
        {
            int v=(x>>i)&1;
            int &now=ch[rt][v];
            if(!now) now=++cnt;
            vec[now].push_back(pos);
            rt=now;
        }
    }

    void build(int pos,int rt)
    {
        int ls=ch[rt][0],rs=ch[rt][1];
        if(ls) build(pos-1,ls);
        if(rs) build(pos-1,rs);

        int len=vec[rt].size();
        int lsize=vec[ls].size();
        int rsize=vec[rs].size();
        int r=0;
        for(int l=0;l<lsize;l++)
        {
            while(r<rsize && vec[ls][l]>vec[rs][r]) r++;
            Ans+=r;
        }
        N[rt].lim=len;
        N[rt].sum=POS;
        POS+=len+1;
        for(int i=1;i<=len;i++) N[rt].add(i,1);
    }

    int find(int rt,int pos)
    {
        return lower_bound(vec[rt].begin(),vec[rt].end(),pos)-vec[rt].begin()+1;
    }

    void cut(ll x,int pos)
    {
        int rt=0;
        for(int i=30;i>=0;i--)
        {
            int v=(x>>i)&1;
            int now=ch[rt][v];
            int ls=ch[rt][0],rs=ch[rt][1];
            int p=find(now,pos);
            N[now].add(p,-1);
            if(v==0 && rs) p=find(rs,pos)-1,Ans-=N[rs].query(p);
            if(v==1 && ls) p=find(ls,pos)-1,Ans-=N[ls].query(N[ls].lim)-N[ls].query(p);
            rt=now;
        }
    }
}T;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        ll x;cin>>x;
        Pos[x]=i;
        T.insert(x,i);
    }
    POS=result;
    T.build(30,0);
    for(int i=1;i<=m;i++)
    {
        ll x;cin>>x;
        cout<<Ans<<'\n';
        T.cut(x,Pos[x]);
    }
    return 0;
}