Codeforces 785E Anton and Permutation

发表于 | 分类于 | 25

炒鸡水但是卡我空间……
居然没有一遍过，不爽……
下次这种题应该写树状数组套线段树而非线段树套线段树……

跟「『TJOI2017』不勤劳的图书管理员」一个套路，交换 al,ar 的时候更新 [l,r] 的贡献即可。

具体地说，首先去除 (x,r)(x∈[l,r),ax>ar) 的个数和 (l,x)(x∈(l,r],al>ax) 的个数。
在维护的数据结构中去除 al,ar 的贡献。
然后交换 al,ar。
计算新的贡献，即加上 (x,r)(x∈[l,r),ax>ar) 的个数和 (l,x)(x∈(l,r],al>ax) 的个数（注意此处已交换）。
以及要考虑一下 l,r 本身为逆序对的情况，这样可能被算两次。

现在我们需要维护一个数据结构，资瓷区间查询属于某值域的数的个数。
如果是静态的话，主席树即可解决。
动态的话，其实就是一个三维偏序问题，用任何一种树套树即可解决。

注意判掉一些情况，比如 l=r,l>r……

代码： 

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
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 2e5;
int n,q,a[N + 5];
long long ans;
struct segnode
{
    int sum;
    int ls,rs;
} seg[N * 200 + 10];
struct node
{
    int rt;
    int ls,rs;
} tree[(N << 3) + 10];
int rt;
void insert(int x,int k,int &p,int tl,int tr)
{
    static int tot = 0;
    if(!p)
        p = ++tot;
    seg[p].sum += k;
    if(tl == tr)
        return ;
    int mid = tl + tr >> 1;
    x <= mid ? insert(x,k,seg[p].ls,tl,mid) : insert(x,k,seg[p].rs,mid + 1,tr);
}
int query(int l,int r,int p,int tl,int tr)
{
    if(l > r)
        return 0;
    if(!p || (l <= tl && tr <= r))
        return seg[p].sum;
    int mid = tl + tr >> 1;
    int ret = 0;
    if(l <= mid)
        ret += query(l,r,seg[p].ls,tl,mid);
    if(r > mid)
        ret += query(l,r,seg[p].rs,mid + 1,tr);
    return ret;
}
void insert(int x,int v,int k,int &p,int tl,int tr)
{
    static int tot = 0;
    if(!p)
        p = ++tot;
    insert(x,k,tree[p].rt,1,n);
    if(tl == tr)
        return ;
    int mid = tl + tr >> 1;
    v <= mid ? insert(x,v,k,tree[p].ls,tl,mid) : insert(x,v,k,tree[p].rs,mid + 1,tr);
}
int query(int l,int r,int x,int y,int p,int tl,int tr)
{
    if(l > r || x > y)
        return 0;
    if(!p || (x <= tl && tr <= y))
        return query(l,r,tree[p].rt,1,n);
    int mid = tl + tr >> 1;
    int ret = 0;
    if(x <= mid)
        ret += query(l,r,x,y,tree[p].ls,tl,mid);
    if(y > mid)
        ret += query(l,r,x,y,tree[p].rs,mid + 1,tr);
    return ret;
}
int main()
{
    scanf("%d%d",&n,&q);
    for(register int i = 1;i <= n;++i)
        insert(i,a[i] = i,1,rt,1,n);
    int x,y;
    while(q--)
    {
        scanf("%d%d",&x,&y);
        if(x ^ y)
        {
            if(x > y)
                swap(x,y);
            ans -= query(x + 1,y,1,a[x] - 1,rt,1,n),ans -= query(x,y - 1,a[y] + 1,n,rt,1,n),ans += a[x] > a[y];
            insert(x,a[x],-1,rt,1,n),insert(y,a[y],-1,rt,1,n);
            swap(a[x],a[y]);
            insert(x,a[x],1,rt,1,n),insert(y,a[y],1,rt,1,n);
            ans += query(x + 1,y,1,a[x] - 1,rt,1,n),ans += query(x,y - 1,a[y] + 1,n,rt,1,n),ans -= a[x] > a[y];
        }
        printf("%lld\n",ans);
    }
}

Related Issues not found

Please contact @Alpha1022 to initialize the comment