题目
有个排列(p)。
对于两个位置(i)和(j)，如果有边从(i)连向(j)，当且仅当(p_i>p_j)且对于任意(kin (min(i,j),max(i,j)))，(p_k<p_j)。
你要选择一些点，选择某个点之后这个点以及其连向的点会被覆盖。
求要覆盖所有点最少需要的点。
支持交换相邻两个位置的操作。
(nle 10^5)
(qle 2*10^4)
数据随机。
转化一下题意：连边的方式相当于，对序列建一棵笛卡尔树，一个点连向的它左子树的右链和右子树的左链。
先不考虑修改，先考虑一个询问改怎么求：
DP：设(f_{i,0/1,0/1,0/1})表示(i)的子树中，(i)自己是否被覆盖，(i)的左链是否被覆盖，(i)的右链是否被覆盖，此时的最小代价。
接下来要支持修改，那么可以维护这棵笛卡尔树。由于数据随机，所以树高为(O(lg n))级别。
题解是根据交换相邻两个位置的特殊性来考虑，我是直接改节点的权值然后旋转（这样可以稍微扩展一下题目，变成交换任意两个）。
于是总时间复杂度为(O(8qlg n))
using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cassert>
#define N 100010
int n,Q;
int p[N];
struct Node *null,*rt;
struct Node{
Node *fa,*c[2];
int v;
int f[2][2][2];
bool getson(){return fa->c[0]!=this;}
void upd(){
for (int k=0;k<2;++k)
for (int i=0;i<2;++i)
for (int j=0;j<2;++j){
f[k][i][j]=c[0]->f[0][i][0]+c[1]->f[0][0][j]+1;
if (!k)
f[k][i][j]=min(f[k][i][j],c[0]->f[i][i][1]+c[1]->f[j][1][j]);
}
}
int ans(){return f[1][1][1];}
void rotate(){
Node *y=fa,*z=y->fa;
if (z==null)
rt=this;
else
z->c[y->getson()]=this;
int k=getson();
fa=z;
y->c[k]=c[!k],c[!k]->fa=y;
c[!k]=y,y->fa=this;
y->upd(),upd();
}
} d[N];
Node *build(){
null=d;
*null={null,null,null,0};
static int st[N];
int tp=0;
for (int i=1;i<=n;++i){
d[i].v=p[i];
Node *lst=null;
while (tp && p[st[tp]]<p[i]){
lst=&d[st[tp]];
--tp;
}
lst->fa=&d[i];
d[i].c[0]=lst;
d[i].c[1]=null;
d[i].fa=&d[st[tp]];
d[st[tp]].c[1]=&d[i];
st[++tp]=i;
}
return &d[st[1]];
}
void init(Node *t){
if (t==null) return;
init(t->c[0]);
init(t->c[1]);
t->upd();
}
void change(Node *x,int _v){
x->v=_v;
while (x!=rt && x->v>x->fa->v)
x->rotate();
while (x->v<max(x->c[0]->v,x->c[1]->v)){
if (x->c[0]->v>x->c[1]->v)
x->c[0]->rotate();
else
x->c[1]->rotate();
}
for (;x!=null;x=x->fa)
x->upd();
}
int main(){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
freopen("permutation.in","r",stdin);
freopen("permutation.out","w",stdout);
scanf("%d%d",&n,&Q);
for (int i=1;i<=n;++i)
scanf("%d",&p[i]);
rt=build();
init(rt);
printf("%d
",rt->ans());
while (Q--){
int x;
scanf("%d",&x);
change(&d[x],p[x+1]);
change(&d[x+1],p[x]);
swap(p[x],p[x+1]);
// init(rt);
// for (int i=1;i<=n;++i)
// if (d[i].fa!=null)
// assert(d[i].fa->v>d[i].v);
printf("%d
",rt->ans());
}
return 0;
}