题目
https://gmoj.net/senior/#main/show/6816
题解
发现如果对原序列建一棵笛卡尔树，一个节点x在原图中连向的点其实就是它在笛卡尔树上的左子树的右链+右子树的左链，如下图。 有了这个性质就很好弄了，这样子一棵子树的可能被祖先覆盖的部分就是它自己 以及左子树的左链 和右子树的右链。
因此设
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 、左子树的左链、右子树的右链 是/否被覆盖，其它节点都已经被覆盖的最少关键点数量，转移不难。
至于交换操作，不妨设
p
x
<
p
x
+
1
p_x<p_{x+1}
px<px+1，那么x必定在以x+1为根的子树的左子树右链的尽头上。用x的左儿子代替x（没有就直接删去x），然后把x插入以x+1为根的子树的右子树的左链某个位置上，接着把这个位置上的点变成自己的右儿子就好了。这时只用修改x原来的位置和现在的位置到根的两条路径上的 f 值就好了。因为数据是随机的，笛卡尔树深度是log的，因此能过。
CODE
#include<cstdio>
using namespace std
;
#define N 100005
int a
[N
],lson
[N
],rson
[N
],fa
[N
],f
[N
][2][2][2];
inline void read(int &x
)
{
char ch
;
while(ch
=getchar(),ch
<'0'||ch
>'9');x
=ch
-48;
while(ch
=getchar(),ch
>='0'&&ch
<='9') x
=x
*10+ch
-48;
}
inline void calc(int k
)
{
f
[k
][0][0][0]=f
[lson
[k
]][0][0][1]+f
[rson
[k
]][0][1][0];
f
[k
][0][1][0]=f
[lson
[k
]][1][1][1]+f
[rson
[k
]][0][1][0];
f
[k
][0][0][1]=f
[lson
[k
]][0][0][1]+f
[rson
[k
]][1][1][1];
f
[k
][0][1][1]=f
[lson
[k
]][1][1][1]+f
[rson
[k
]][1][1][1];
f
[k
][1][0][0]=f
[lson
[k
]][0][0][0]+f
[rson
[k
]][0][0][0]+1;
f
[k
][1][1][0]=f
[lson
[k
]][0][1][0]+f
[rson
[k
]][0][0][0]+1;
f
[k
][1][0][1]=f
[lson
[k
]][0][0][0]+f
[rson
[k
]][0][0][1]+1;
f
[k
][1][1][1]=f
[lson
[k
]][0][1][0]+f
[rson
[k
]][0][0][1]+1;
for(int x
=1;x
>=0;--x
)
for(int y
=1;y
>=0;--y
)
for(int z
=1;z
>=0;--z
)
{
if(x
==1&&f
[k
][0][y
][z
]>f
[k
][1][y
][z
]) f
[k
][0][y
][z
]=f
[k
][1][y
][z
];
if(y
==1&&f
[k
][x
][0][z
]>f
[k
][x
][1][z
]) f
[k
][x
][0][z
]=f
[k
][x
][1][z
];
if(z
==1&&f
[k
][x
][y
][0]>f
[k
][x
][y
][1]) f
[k
][x
][y
][0]=f
[k
][x
][y
][1];
}
}
void dfs(int k
)
{
if(lson
[k
]) dfs(lson
[k
]);
if(rson
[k
]) dfs(rson
[k
]);
calc(k
);
}
inline void swap(int &x
,int &y
){int z
=x
;x
=y
,y
=z
;}
int main()
{
freopen("permutation.in","r",stdin);
freopen("permutation.out","w",stdout);
int n
,q
,i
,j
,x
,root
;
read(n
),read(q
);
for(i
=1;i
<=n
;++i
) read(a
[i
]);
root
=a
[1];
for(i
=2;i
<=n
;++i
)
{
if(a
[i
]>root
) lson
[a
[i
]]=root
,fa
[root
]=a
[i
],root
=a
[i
];
else
{
for(j
=root
;a
[i
]<rson
[j
];j
=rson
[j
]);
if(rson
[j
]) lson
[a
[i
]]=rson
[j
],fa
[rson
[j
]]=a
[i
];
rson
[j
]=a
[i
],fa
[a
[i
]]=j
;
}
}
dfs(root
),printf("%d\n",f
[root
][1][1][1]);
while(q
--)
{
scanf("%d",&x
);
if(a
[x
]<a
[x
+1])
{
if(a
[x
]==lson
[a
[x
+1]])
{
fa
[a
[x
]]=lson
[a
[x
+1]]=0;
if(lson
[a
[x
]])
{
j
=lson
[a
[x
]],lson
[a
[x
]]=0;
fa
[j
]=a
[x
+1],lson
[a
[x
+1]]=j
;
}
}
else
{
j
=fa
[a
[x
]],fa
[a
[x
]]=0;
if(lson
[a
[x
]]) rson
[j
]=lson
[a
[x
]],fa
[rson
[j
]]=j
,lson
[a
[x
]]=0;
else rson
[j
]=0;
for(i
=j
;i
!=a
[x
+1];i
=fa
[i
]) calc(i
);
}
if(!rson
[a
[x
+1]]) rson
[a
[x
+1]]=a
[x
],fa
[a
[x
]]=a
[x
+1];
else if(a
[x
]>rson
[a
[x
+1]])
{
j
=rson
[a
[x
+1]];
rson
[a
[x
]]=j
,fa
[j
]=a
[x
];
rson
[a
[x
+1]]=a
[x
],fa
[a
[x
]]=a
[x
+1];
}
else
{
for(i
=rson
[a
[x
+1]];a
[x
]<lson
[i
];i
=lson
[i
]);
if(lson
[i
]) j
=lson
[i
],rson
[a
[x
]]=j
,fa
[j
]=a
[x
];
fa
[a
[x
]]=i
,lson
[i
]=a
[x
];
}
for(i
=a
[x
];i
;i
=fa
[i
]) calc(i
);
}
else
{
if(a
[x
+1]==rson
[a
[x
]])
{
fa
[a
[x
+1]]=rson
[a
[x
]]=0;
if(rson
[a
[x
+1]])
{
j
=rson
[a
[x
+1]],rson
[a
[x
+1]]=0;
fa
[j
]=a
[x
],rson
[a
[x
]]=j
;
}
}
else
{
j
=fa
[a
[x
+1]],fa
[a
[x
+1]]=0;
if(rson
[a
[x
+1]]) lson
[j
]=rson
[a
[x
+1]],fa
[lson
[j
]]=j
,rson
[a
[x
+1]]=0;
else lson
[j
]=0;
for(i
=j
;i
!=a
[x
];i
=fa
[i
]) calc(i
);
}
if(!lson
[a
[x
]]) lson
[a
[x
]]=a
[x
+1],fa
[a
[x
+1]]=a
[x
];
else if(a
[x
+1]>lson
[a
[x
]])
{
j
=lson
[a
[x
]];
lson
[a
[x
+1]]=j
,fa
[j
]=a
[x
+1];
lson
[a
[x
]]=a
[x
+1],fa
[a
[x
+1]]=a
[x
];
}
else
{
for(i
=lson
[a
[x
]];a
[x
+1]<rson
[i
];i
=rson
[i
]);
if(rson
[i
]) j
=rson
[i
],lson
[a
[x
+1]]=j
,fa
[j
]=a
[x
+1];
fa
[a
[x
+1]]=i
,rson
[i
]=a
[x
+1];
}
for(i
=a
[x
+1];i
;i
=fa
[i
]) calc(i
);
}
swap(a
[x
],a
[x
+1]);
printf("%d\n",f
[root
][1][1][1]);
}
return 0;
}
