Description
给你一个长度为
n
n
n且完全随机的排列
p
p
p，
i
i
i（下标）可以被右边或左边第一个大于它的支配。
现在需要选择最少的点，使得每一个点要么被选择，要么被一个选择的点支配。
还需要支持
q
q
q次修改：交换相邻的两个随机位置的值。
对于未修改时和每一次修改后输出最少的选择数。
n
≤
1
e
5
,
q
≤
2
e
4
n\le1e5,q\le2e4
n≤1e5,q≤2e4
Solution
首先建出笛卡尔树，可以发现一个点支配的点是左儿子的所有右儿子链，和右儿子的所有左儿子链。所以可以记一个DP，
f
[
x
]
[
0
/
1
]
[
0
/
1
]
f[x][0/1][0/1]
f[x][0/1][0/1]表示笛卡尔树的
x
x
x的子树下，左儿子链、右儿子链是否被父亲覆盖，
O
(
n
)
O(n)
O(n)处理一次询问。然后相邻的交换可以直接在树上接一接，断一断，因为完全随机，所以期望的树高的
l
o
g
log
log的，由于只会修改两条链上的点，所以暴力改一改就好了。
O
(
n
+
q
l
o
g
n
)
O(n+q\ log\ n)
O(n+q log n)
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define maxn 100005
using namespace std
;
int n
,q
,i
,j
,k
,a
[maxn
],d
[maxn
],L
[maxn
],R
[maxn
];
int fa
[maxn
],tr
[maxn
][2],f
[maxn
][2][2];
void read(int &x
){
x
=0; char ch
=getchar();
for(;ch
<'0'||ch
>'9';ch
=getchar());
for(;ch
>='0'&&ch
<='9';ch
=getchar()) x
=x
*10+ch
-'0';
}
void dp(int x
){
memset(f
[x
],127,sizeof(f
[x
]));
for(int i
=0;i
<2;i
++) for(int j
=0;j
<2;j
++){
if (i
||j
) f
[x
][i
][j
]=f
[tr
[x
][0]][i
][0]+f
[tr
[x
][1]][0][j
];
f
[x
][i
][j
]=min(f
[x
][i
][j
],f
[tr
[x
][0]][i
][1]+f
[tr
[x
][1]][1][j
]+1);
}
}
void change(int v
){
int x
,y
,z
,c
;
if (a
[v
]>a
[v
+1]) x
=a
[v
],y
=a
[v
+1],c
=1;
else x
=a
[v
+1],y
=a
[v
],c
=0;
swap(a
[v
],a
[v
+1]);
if (fa
[y
]==x
) {
z
=x
,tr
[x
][c
]=tr
[y
][c
];
if (tr
[x
][c
]) fa
[tr
[x
][c
]]=x
;
} else {
z
=fa
[y
],tr
[z
][c
^1]=tr
[y
][c
];
if (tr
[z
][c
^1]) fa
[tr
[z
][c
^1]]=z
;
}
while (z
!=x
) dp(z
),z
=fa
[z
];
tr
[y
][0]=tr
[y
][1]=fa
[y
]=0;
if (y
>tr
[x
][c
^1]){
tr
[y
][c
^1]=tr
[x
][c
^1],tr
[x
][c
^1]=y
,fa
[y
]=x
;
if (tr
[y
][c
^1]) fa
[tr
[y
][c
^1]]=y
;
} else {
z
=tr
[x
][c
^1];
while (tr
[z
][c
]>y
) z
=tr
[z
][c
];
tr
[y
][c
^1]=tr
[z
][c
],tr
[z
][c
]=y
,fa
[y
]=z
;
if (tr
[y
][c
^1]) fa
[tr
[y
][c
^1]]=y
;
}
z
=y
;
while (z
) dp(z
),z
=fa
[z
];
}
int main(){
freopen("permutation4.in","r",stdin);
freopen("ceshi.out","w",stdout);
read(n
),read(q
);
for(i
=1;i
<=n
;i
++) read(a
[i
]);
for(d
[0]=0,i
=1;i
<=n
;i
++){
while (d
[0]&&a
[d
[d
[0]]]<a
[i
]) R
[a
[d
[d
[0]]]]=a
[i
],d
[0]--;
d
[++d
[0]]=i
;
}
for(d
[0]=0,i
=n
;i
>=1;i
--){
while (d
[0]&&a
[d
[d
[0]]]<a
[i
]) L
[a
[d
[d
[0]]]]=a
[i
],d
[0]--;
d
[++d
[0]]=i
;
}
for(i
=1;i
<n
;i
++) if (L
[i
]&&L
[i
]<R
[i
]||!R
[i
]) fa
[i
]=L
[i
],tr
[L
[i
]][1]=i
;
else fa
[i
]=R
[i
],tr
[R
[i
]][0]=i
;
for(i
=1;i
<=n
;i
++) dp(i
);
printf("%d\n",f
[n
][0][0]);
int qi
=0;
while (q
--){
int x
; read(x
);
change(x
);
printf("%d\n",f
[n
][0][0]);
}
}
