自动搬运

查看原文

来自洛谷，原作者为

	ran_qwq debug 深入思考 只靠样例与自己！

搬运于2025-08-24 23:04:50，当前版本为作者最后更新于2025-04-17 22:04:20，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

大半年前写的题。

借鉴了一下@yangjinhua 的思路。

一个比较显然的转化是，直接维护 $f$，单点与可以看作子树与，路径查可以看作单点查。

考虑怎么更好地表示能量和超能量。记 $s=\sum f_i$，$t=\sum f_i^2$。显然由因式分解得能量 $A=s^2$，超能量就是把能量的 $u=v$ 去掉再除以 $2$，超能量 $B=\dfrac{s^2-t}2$。所以可以先求出初始的 $s$ 和 $t$ 并动态维护。

不同位之间独立，下面只考虑某一位，假设当前询问 $x$ 的这位是 $0$，即把一个子树这一位推平成 $0$。一个点一位只会被有效推平一次，即如果能做到无效推平是均摊 $O(1)$ 的，复杂度就是对的。有两种解决方案：

一是每位维护一个并查集，能找出下一个 $1$ 的位置（后继），一个一个跳，暴力改成 $0$。大半年前实现的是这个思路，但很遗憾空间被卡了。

二是虑暴力从左往右扫，如果当前位置已经是 $0$ 了，则当前位置的子树都可以跳过。分析下时间复杂度，一个点一位只会在 $1$ 变 $0$ 时被遍历到一次，以及操作它的某个祖先时先遍历到它的父亲，然后展开到当前节点。接着父亲会被推平成 $0$，永远遍历不到。所以一个点一位无效推平只有一次。

然而现在还是会 MLE，把 dfs 换成非递归可以通过。

int n,m,id,idx,sm,tt,fa[N],dfn[N],nm[N],rk[N],sz[N];
ll a[N],b[N];
void QwQ() {
	n=rd(),m=rd();
	for(int i=2;i<=n;i++) fa[i]=rd()+1;
	for(int i=1;i<=n;i++) a[i]=rdll(),sz[i]=1;
	for(int i=2;i<=n;i++) a[i]&=a[fa[i]]; 
	for(int i=n;i;i--) sz[fa[i]]+=sz[i];
	for(int i=1;i<=n;i++) dfn[i]=nm[fa[i]]+1,b[dfn[i]]=a[i],rk[dfn[i]]=i,nm[fa[i]]+=sz[i],nm[i]=dfn[i];
	for(int i=1;i<=n;i++) cadd(sm,b[i]%MOD),cadd(tt,vmul(b[i]%MOD,b[i]%MOD));
	wr(vmul(sm,sm)," "),wr(vmul(vsub(vmul(sm,sm),tt),iv),"\n");
	for(int u;m--;) {
		u=rd()+1; ll x=rdll();
		for(int k=0,j;k<60;k++) if(!(x>>k&1)) for(int i=dfn[u];i<dfn[u]+sz[u];i++) {
			if(!(b[i]>>k&1)) {i+=sz[rk[i]]-1; continue;}
			csub(sm,(1ll<<k)%MOD),csub(tt,vmul((1ll<<k)%MOD,vsub(b[i]*2%MOD,(1ll<<k)%MOD))),b[i]-=1ll<<k;
		}
		wr(vmul(sm,sm)," "),wr(vmul(vsub(vmul(sm,sm),tt),iv),"\n");
	}
}