【模拟赛】乌拉~~（重链剖分）

2023-09-28 18:29:04

背景

大家好，我是一名勇敢的俄罗斯士兵，我昨天正在打 C o d e F o r c e s \tt CodeForces CodeForces 呢，突然被拉去打仗了。我们已经突入基辅，但因为推进过于迅速，后勤补给未能补上，我们现在急需 143 元来购买一些吃的 一个能替代通信员的老兄来解密一下临时截获的乌克兰电报，密钥似乎是一道信息题。等我们打赢了，就分你一个 【 数 据 删 除 】 _{^{【数据删除】}} 【数据删除】​ 作为答谢。不说了又要冲锋了，乌拉！！！

题面

给定一棵以 1 1 1 为根的有根树， i i i 号点有点权 v i v_i vi​。接下来你需要对其进行 q q q 次操作，操作有 3 3 3 种：

  • S u d： v u ← v u + d v_u ← v_u + d vu​←vu​+d;
  • M u d：对于 u u u 子树中的任意一点 x x x（包括 u u u）， v x ← v x + d v_x ← v_x + d vx​←vx​+d；
  • Q u：求 ∑ i = 1 n ∑ j = i + 1 n [ L C A ( i , j ) = u ] v i v j m o d    2 63 ∑^n_{i=1}∑_{j=i+1}^n[LCA(i, j) = u]v_iv_j \mod 2^{63} ∑i=1n​∑j=i+1n​[LCA(i,j)=u]vi​vj​mod263。

2 ≤ n , q ≤ 2 × 1 0 5 , 1 ≤ f i ≤ i , 0 ≤ d , v i ≤ 1 0 9 2 ≤ n, q ≤ 2 × 10^5, 1 ≤ f_i ≤ i, 0 ≤ d, v_i ≤ 10^9 2≤n,q≤2×105,1≤fi​≤i,0≤d,vi​≤109 。

题解

令 a n s ( u ) = ∑ i = 1 n ∑ j = i + 1 n [ L C A ( i , j ) = u ] v i v j m o d    2 63 ans(u)=∑^n_{i=1}∑_{j=i+1}^n[LCA(i, j) = u]v_iv_j \mod 2^{63} ans(u)=∑i=1n​∑j=i+1n​[LCA(i,j)=u]vi​vj​mod263 （其实就是把它简写了一下）， f ( u ) = ∑ i = 1 n ∑ j = 1 n [ L C A ( i , j ) = u ] v i v j m o d    2 64 = 2 a n s ( u ) + v u 2 f(u)=∑^n_{i=1}∑_{j=1}^n[LCA(i, j) = u]v_iv_j \mod 2^{64}=2ans(u)+v_u^2 f(u)=∑i=1n​∑j=1n​[LCA(i,j)=u]vi​vj​mod264=2ans(u)+vu2​，我们很容易想到用重链剖分维护每个点的 f ( u ) f(u) f(u) 。

设 s v ( u ) sv(u) sv(u) 表示 u u u 的子树点权和，那么 f ( u ) = s v ( u ) 2 − ∑ i ∈ s o n u s v ( i ) 2 f(u)=sv(u)^2-\sum_{i\in son_u}sv(i)^2 f(u)=sv(u)2−∑i∈sonu​​sv(i)2（和点分治的容斥是一个原理），我们暴力维护每个点轻儿子的 s v ( i ) 2 sv(i)^2 sv(i)2 和，记为 s m 2 ( u ) sm^2(u) sm2(u)。

但是子树修改权值将十分麻烦，子树中所有的信息都会变化，包括 s m 2 ( u ) sm^2(u) sm2(u) 。所以我们不妨将子树修改的懒标记永久化，子树维护的所有值都排除祖先的懒标记的影响。在求答案的时候再考虑懒标记总和 d d d 会带来什么影响。

由于 ( v i + d ) ( v j + d ) = v i v j + d ( v i + v j ) + d 2 (v_i+d)(v_j+d)=v_iv_j+d(v_i+v_j)+d^2 (vi​+d)(vj​+d)=vi​vj​+d(vi​+vj​)+d2 ，所以我们还要维护 ∑ i = 1 n ∑ j = 1 n [ L C A ( i , j ) = u ] ( v i + v j ) m o d    2 64 ∑^n_{i=1}∑_{j=1}^n[LCA(i, j) = u](v_i+v_j) \mod 2^{64} ∑i=1n​∑j=1n​[LCA(i,j)=u](vi​+vj​)mod264 和 ∑ i = 1 n ∑ j = 1 n [ L C A ( i , j ) = u ] m o d    2 64 ∑^n_{i=1}∑_{j=1}^n[LCA(i, j) = u] \mod 2^{64} ∑i=1n​∑j=1n​[LCA(i,j)=u]mod264 ，两者都能和 f ( u ) f(u) f(u) 相似地维护。

最后算答案的时候细节极多。

时间复杂度 O ( n log ⁡ 2 n ) O(n\log^2 n) O(nlog2n) 。

CODE

#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<random>
#include<bitset>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 200005
#define LL long long
#define ULL unsigned long long
#define ENDL putchar('\n')
#define DB double
#define lowbit(x) (-(x) & (x))
#define FI first
#define SE second
int xchar() {
	static const int maxn = 1000000;
	static char b[maxn];
	static int pos = 0,len = 0;
	if(pos == len) pos = 0,len = fread(b,1,maxn,stdin);
	if(pos == len) return -1;
	return b[pos ++];
}
//#define getchar() xchar()
LL read() {
	LL f = 1,x = 0;int s = getchar();
	while(s < '0' || s > '9') {if(s<0)return -1;if(s=='-')f=-f;s = getchar();}
	while(s >= '0' && s <= '9') {x = (x<<1) + (x<<3) + (s^48);s = getchar();}
	return f*x;
}
void putpos(LL x) {if(!x)return ;putpos(x/10);putchar((x%10)^48);}
void putnum(LL x) {
	if(!x) {putchar('0');return ;}
	if(x<0) putchar('-'),x = -x;
	return putpos(x);
}
void AIput(LL x,int c) {putnum(x);putchar(c);}

int n,m,s,o,k;
int hd[MAXN],nx[MAXN],v[MAXN],cne;
void ins(int x,int y) {
	nx[++ cne] = hd[x]; v[cne] = y; hd[x] = cne;
}
ULL tre[MAXN<<2],lz[MAXN<<2];
int M;
void maketree(int n) {M=1;while(M<n+2)M<<=1;}
void addp(int x,ULL y) {
	for(int s=M+x;s;s>>=1)tre[s]+=y;
}
void addtree(int l,int r,ULL y) {
	if(l > r) return ;
	int le = 1;
	for(int s = M+l-1,t = M+r+1;s || t;s >>= 1,t >>= 1,le <<= 1) {
		if(s<M) tre[s] = tre[s<<1]+tre[s<<1|1]+lz[s]*le;
		if(t<M) tre[t] = tre[t<<1]+tre[t<<1|1]+lz[t]*le;
		if((s>>1) != (t>>1)) {
			if(!(s&1)) tre[s^1] += y*le,lz[s^1] += y;
			if(t & 1) tre[t^1] += y*le,lz[t^1] += y;
		}
	}return ;
}
ULL findplz(int x) {
	int s = M+x;ULL as = 0;
	while(s) as += lz[s],s >>= 1;
	return as;
}
ULL findtree(int l,int r) {
	if(l > r || !l || !r) return 0ull;
	ULL as = 0; int ls = 0,rs = 0,le = 1;
	for(int s = M+l-1,t = M+r+1;s || t;s >>= 1,t >>= 1,le <<= 1) {
		as += lz[s]*ls + lz[t]*rs;
		if((s>>1) != (t>>1)) {
			if(!(s&1)) as += tre[s^1],ls += le;
			if(t & 1) as += tre[t^1],rs += le;
		}
	}return as;
}
ULL dp3[MAXN],sm2[MAXN],sm1[MAXN];
int d[MAXN],fa[MAXN],siz[MAXN],son[MAXN];
int tp[MAXN],dfn[MAXN],rr[MAXN],id[MAXN],tim;
void dfs1(int x,int ff) {
	d[x] = d[fa[x] = ff] + 1;
	siz[x] = 1; son[x] = 0; dp3[x] = 1;
	for(int i = hd[x];i;i = nx[i]) {
		dfs1(v[i],x);
		dp3[x] += siz[x] *2ll* siz[v[i]];
		siz[x] += siz[v[i]];
		if(siz[v[i]] > siz[son[x]]) son[x] = v[i];
	}
	return ;
}
void dfs2(int x,int ff) {
	if(son[ff] == x) tp[x] = tp[ff];
	else tp[x] = x;
	dfn[x] = ++ tim; id[tim] = x;
	if(son[x]) dfs2(son[x],x);
	for(int i = hd[x];i;i = nx[i]) {
		if(v[i] != son[x]) {
			dfs2(v[i],x);
		}
	}
	rr[x] = tim;
	return ;
}
void addt(int x,ULL y) {
	addtree(dfn[x],rr[x],y);
	ULL adn = siz[x]*y;
	x = tp[x];
	while(fa[x]) {
		int p = fa[x];
		ULL ssm = findtree(dfn[x],rr[x]) - findplz(dfn[p])*siz[x] - adn;
		sm2[p] += adn*ssm*2 + adn*adn;
		sm1[p] += adn*siz[x];
		x = tp[p];
	}return ;
}
void addsingle(int x,ULL y) {
	addp(dfn[x],y);
	x = tp[x];
	while(fa[x]) {
		int p = fa[x];
		ULL ssm = findtree(dfn[x],rr[x]) - findplz(dfn[p])*siz[x] - y;
		sm2[p] += y*ssm*2 + y*y;
		sm1[p] += y*siz[x];
		x = tp[p];
	}return ;
}
ULL query(int x) {
	ULL flz = findplz(dfn[x]),me = findtree(dfn[x],dfn[x]);
	ULL smh = findtree(dfn[son[x]],rr[son[x]]) - flz*siz[son[x]],sm = findtree(dfn[x],rr[x]) - flz*siz[x];
	ULL s1 = sm*siz[x] - sm1[x] - smh*siz[son[x]],s2 = sm*sm - sm2[x] - smh*smh;
	return s2 + flz*s1*2 + flz*flz*dp3[x] - me*me;
}
int main() {
	freopen("ancestor.in","r",stdin);
	freopen("ancestor.out","w",stdout);
	n = read();int Q = read();
	for(int i = 2;i <= n;i ++) {
		s = read(); ins(s,i);
	}
	dfs1(1,0); dfs2(1,0);
	maketree(n);
	for(int i = 1;i <= n;i ++) {
		addp(dfn[i],read());
	}
	for(int i = 1;i <= n;i ++) {
		for(int j = hd[i];j;j = nx[j]) {
			if(v[j] != son[i]) {
				ULL fd = findtree(dfn[v[j]],rr[v[j]]);
				sm2[i] += fd*fd; sm1[i] += fd*siz[v[j]];
			}
		}
	}
	while(Q --) {
		char c = getchar();
		while(c == ' ' || c == '\n') c = getchar();
		if(c == 'S') {
			s = read();k = read();
			addsingle(s,k);
		}
		else if(c == 'M') {
			s = read();k = read();
			addt(s,k);
		}
		else {
			AIput(query(read())>>1,'\n');
		}
	}
	return 0;
}
上一篇：dialog.setCancelable(false) 不生效问题分析与解决


下一篇：每日一练（27）：二叉树的深度