JZOJ 6816.随机的排列

观察这个连边方式,容易想到笛卡尔树。
则一个点的出边即为其左子树的右链和右子树的左链。

考虑在笛卡尔树上 DP。
\(f_{i,0/1,0/1,0/1}\) 表示点 \(i\) 是否被选,左链是否被覆盖,右链是否被覆盖的最小点数。
修改时暴力更新即可。

代码:

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
117
118
119
120
121
122
123
124
125
126
127
128
129
#pragma GCC optimize("Ofast")
#pragma GCC target("sse3","sse2","sse")
#pragma GCC diagnostic error "-std=c++14"
#pragma GCC diagnostic error "-fwhole-program"
#pragma GCC diagnostic error "-fcse-skip-blocks"
#pragma GCC diagnostic error "-funsafe-loop-optimizations"
#pragma GCC optimize("fast-math","unroll-loops","no-stack-protector","inline")
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5;
int n,q;
struct node
{
int val;
int f[2][2][2];
int ls,rs,fa;
} a[N + 5];
int rt;
inline void trans(int &x,int v)
{
x = min(x,v);
}
inline void push(int p)
{
a[p].ls && (a[a[p].ls].fa = p),
a[p].rs && (a[a[p].rs].fa = p);
}
inline void calc(int p)
{
memset(a[p].f,0x3f,sizeof a[p].f);
for(register int i1 = 0;i1 < 2;++i1)
for(register int j1 = 0;j1 < 2;++j1)
for(register int k1 = 0;k1 < 2;++k1)
for(register int i2 = 0;i2 < 2;++i2)
for(register int j2 = 0;j2 < 2;++j2)
for(register int k2 = 0;k2 < 2;++k2)
{
int val = a[a[p].ls].f[i1][j1][k1] + a[a[p].rs].f[i2][j2][k2];
if(j1 && i2)
trans(a[p].f[0][0][0],val);
trans(a[p].f[0][0][1],val + 1);
if(i1)
{
if(j1 && i2 && k1)
trans(a[p].f[1][0][0],val);
trans(a[p].f[1][0][1],val + 1);
}
if(j2)
{
if(j1 && i2 && k2)
trans(a[p].f[0][1][0],val);
trans(a[p].f[0][1][1],val + 1);
}
if(i1 && j2)
{
if(j1 && i2 && k1 && k2)
trans(a[p].f[1][1][0],val);
trans(a[p].f[1][1][1],val + 1);
}
}
}
int merge(int x,int y)
{
if(!x || !y)
return x | y;
if(a[x].val > a[y].val)
{
a[x].rs = merge(a[x].rs,y),push(x);
return x;
}
else
{
a[y].ls = merge(x,a[y].ls),push(y);
return y;
}
}
void split(int p,int k,int &x,int &y)
{
if(!p)
{
x = y = 0;
return ;
}
if(p <= k)
x = p,split(a[p].rs,k,a[p].rs,y);
else
y = p,split(a[p].ls,k,x,a[p].ls);
a[x].fa = a[y].fa = 0,push(p);
}
void dfs(int p)
{
if(!p)
return ;
dfs(a[p].ls),dfs(a[p].rs);
calc(p);
}
void up(int p)
{
if(!p)
return ;
for(;p;p = a[p].fa)
calc(p);
}
int main()
{
freopen("permutation.in","r",stdin),freopen("permutation.out","w",stdout);
scanf("%d%d",&n,&q);
for(register int i = 1;i <= n;++i)
scanf("%d",&a[i].val),push(i),rt = merge(rt,i);
dfs(rt),printf("%d\n",a[rt].f[1][1][1]);
for(int x,y,l,r,t;q;--q)
{
scanf("%d",&x);
if(a[x].val < a[x + 1].val)
y = a[x].fa;
else
y = a[x + 1].fa;
split(rt,x - 1,l,t),split(t,x,t,r),split(r,x + 1,t,r),
swap(a[x],a[x + 1]),
rt = merge(merge(l,x),merge(x + 1,r));
if(a[x].val < a[x + 1].val)
up(y),up(x);
else
up(y),up(x + 1);
printf("%d\n",a[rt].f[1][1][1]);
}
}