自动搬运

查看原文

来自洛谷，原作者为

	gxy001 ......

搬运于2025-08-24 22:22:24，当前版本为作者最后更新于2021-07-06 21:52:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意首先可以转化为求笛卡尔树上大小为 $4$ 的连通块个数（对应六元环的六个点为这四个点和最上面节点代表区间的右端点 $+1$，左端点 $-1$），但不能包含根节点（六元环不包含 $0$，$n+1$），用一个简单的 dp 求解就行了。

修改操作体现在笛卡尔树上其实就是上旋，容易发现，对于一条方向相同的链，一个点上旋到链顶只会产生 $O(1)$ 的父子关系改变，也只会产生 $O(1)$ 的 dp 数组的改变。

所以直接用 LCT 去维护就行了。

核心代码：

inline void upd(int x,int val){
	int l=ch[x][0],r=ch[x][1];
	cut(x,l),cut(x,r);
	v[x]+=val;
	while(fa[x]&&cmp(x,fa[x])){
		splay(x);
		if(s[x][0]){
			int fat=findnxt(x),h=fa[x];
			cut(h,x);
			if(d[x])link(h,l),l=fat;
			else link(h,r),r=fat;
			if(fa[fat]){
				int g=fa[fat];
				cut(g,fat),link(g,x);
			}
		}else{
			int fat=fa[x];
			cut(fat,x);
			if(d[x])link(fat,l),l=fat;
			else link(fat,r),r=fat;
			if(fa[fat]){
				int g=fa[fat];
				cut(g,fat),link(g,x);
			}
		}
	}
	link(x,l),link(x,r);
	if(!fa[x]) rt=x;
}