JZOJ 6816 随机的排列

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

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

代码：

#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]);
    }
}