Liveddd's Blog

愛にできることはまだあるかい

P9596 [JOI Open 2018] 冒泡排序 2

发表于 更新于 分类于
本文字数： 3.5k 阅读时长 ≈ 8 分钟

简单数据结构，需要一点转化。

考虑冒泡排序的轮数，设 $f_i$ 为第 $i$ 个数前面中 $> a_i$ 的个数，容易发现答案为 $\max{f_i}$，据说使用书套树可以做到 $\mathcal O(n\log^2 n)$。但是不够并且不好写，考虑继续转化。

我们设 $g_i$ 表示前 $i$ 个数中 $\leq a_i$ 的个数，容易发现 $f_i=i-g_i$。注意到我们可以设设 $g_i$ 表示所有数中 $\leq a_i$ 的个数，你会发现这样对于答案没有影响：因为假设在 $i$ 后面存在 $\leq a_i$ 的数 $a_j$，那么 $j$ 肯定是比 $i$ 更优的（因为我们的答案是 $i-g_i$）。所以我们直接开一棵权值线段树维护即可。

具体实现用 set 维护最大的下标，然后对应地在线段树上修改即可。时间复杂度 $\mathcal O(n\log n)$。代码实现很简单一遍过）。

Code
 
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
116
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
using namespace std;
const int N=5e5+10;
template<class T>
inline void read(T &x)
{
	x=0;int f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();};
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
int n,m;
int a[N];
int tot,c[N<<1];
set<int>p[N<<1];
struct Op
{
    int x,y;
}op[N];
struct Seg
{
    struct Node
    {
        int l,r;
        int v,tag;
    }tr[N<<3];
    void pushup(int x){tr[x].v=max(tr[x<<1].v,tr[x<<1|1].v);}
    void update(int x,int k)
    {
        tr[x].v+=k;
        tr[x].tag+=k;
    }
    void pushdown(int x)
    {
        if(tr[x].tag)
        {
            update(x<<1,tr[x].tag);
            update(x<<1|1,tr[x].tag);
            tr[x].tag=0;
        }
    }
    void build(int x,int l,int r)
    {
        tr[x].l=l,tr[x].r=r;
        tr[x].tag=0,tr[x].v=0;
        if(l==r)return ;
        int mid=l+r>>1;
        build(x<<1,l,mid),build(x<<1|1,mid+1,r);
        pushup(x);
    }
    void add(int x,int l,int r,int k)
    {
        if(l<=tr[x].l&&tr[x].r<=r)return update(x,k);
        pushdown(x);
        int mid=tr[x].l+tr[x].r>>1;
        if(l<=mid)add(x<<1,l,r,k);
        if(r>mid)add(x<<1|1,l,r,k);
        pushup(x);
    }
}seg;
void add(int pos,int val)
{
    if(!p[val].empty())seg.add(1,val,val,-*p[val].rbegin());
    seg.add(1,val,tot,-1);
    p[val].insert(pos);
    seg.add(1,val,val,*p[val].rbegin());
}
void del(int pos,int val)
{
    seg.add(1,val,val,-*p[val].rbegin());
    seg.add(1,val,tot,1);   
    p[val].erase(pos);
    if(!p[val].empty())seg.add(1,val,val,*p[val].rbegin());
}
int main()
{
    read(n,m);
    for(int i=1;i<=n;i++)read(a[i]),c[++tot]=a[i];
    for(int i=1;i<=m;i++)read(op[i].x,op[i].y),c[++tot]=op[i].y,op[i].x++;
    sort(c+1,c+1+tot);
    tot=unique(c+1,c+1+tot)-c-1;
    seg.build(1,1,tot);

    for(int i=1;i<=n;i++)
    {
        a[i]=lower_bound(c+1,c+1+tot,a[i])-c;
        p[a[i]].insert(i);
        seg.add(1,a[i],tot,-1);
    }
    for(int i=1;i<=tot;i++)
    {
        if(p[i].empty())continue;
        int x=*p[i].rbegin();
        seg.add(1,i,i,x);
    }
    //pre
    for(int i=1;i<=m;i++)
    {
        int &now=a[op[i].x];
        op[i].y=lower_bound(c+1,c+1+tot,op[i].y)-c;
        del(op[i].x,now);
        now=op[i].y;
        add(op[i].x,now);
        printf("%d\n",seg.tr[1].v);
    }
    return 0;
}