题目
有个排列
p
p
p。
对于两个位置
i
i
i和
j
j
j，如果有边从
i
i
i连向
j
j
j，当且仅当
p
i
>
p
j
p_i>p_j
pi>pj且对于任意
k
∈
(
min
(
i
,
j
)
,
max
(
i
,
j
)
)
k\in (\min(i,j),\max(i,j))
k∈(min(i,j),max(i,j))，
p
k
<
p
j
p_k<p_j
pk<pj。
你要选择一些点，选择某个点之后这个点以及其连向的点会被覆盖。
求要覆盖所有点最少需要的点。
支持交换相邻两个位置的操作。
n
≤
1
0
5
n\le 10^5
n≤105
q
≤
2
∗
1
0
4
q\le 2*10^4
q≤2∗104
数据随机。
转化一下题意：连边的方式相当于，对序列建一棵笛卡尔树，一个点连向的它左子树的右链和右子树的左链。
先不考虑修改，先考虑一个询问改怎么求：
DP：设
f
i
,
0
/
1
,
0
/
1
,
0
/
1
f_{i,0/1,0/1,0/1}
fi,0/1,0/1,0/1表示
i
i
i的子树中，
i
i
i自己是否被覆盖，
i
i
i的左链是否被覆盖，
i
i
i的右链是否被覆盖，此时的最小代价。
接下来要支持修改，那么可以维护这棵笛卡尔树。由于数据随机，所以树高为
O
(
lg
n
)
O(\lg n)
O(lgn)级别。
题解是根据交换相邻两个位置的特殊性来考虑，我是直接改节点的权值然后旋转（这样可以稍微扩展一下题目，变成交换任意两个）。
于是总时间复杂度为
O
(
8
q
lg
n
)
O(8q\lg n)
O(8qlgn)
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("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\n",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]);
printf("%d\n",rt
->ans());
}
return 0;
}
