YbtOJ 774「分块算法」奇妙的树
YbtOJ 774「分块算法」奇妙的树
题目链接：YbtOJ #774
小 A 有一棵 n 个点的有根树，以 1 号点为根。i 号点的点权为 a_i。
假设 i 号点的父节点为 f_i（方便起见认为 f_1=0），小 A 发现这棵树非常奇妙，它满足一个特殊的性质：对于任意整数 i\in[2,n]，满足 f_{i-1}\le f_i < i
小 A 将会进行 q 次询问，第 i 次询问给出一个区间 [l_i,r_i]，求：
强制在线。
1\le n,q\le2.5\times10^5，0\le a_i < 9982443531\le l_i\le r_i\le n。保证对于任意整数 i\in[2,n]，满足 f_{i-1}\le f_i < i
Solution
容易通过归纳证明如下几个性质：
- 性质一：x 的祖先标号必然小于 x。
- 性质二：dep_i 随着 i 的增大不降。
- 性质三：设 g_i 为 满足 f_j < ij，则 i 和 g_i 的深度至多相差 1。
- 性质四：标号在 [l,r] 范围内的点构成以 [l,\min{r,g_l}] 中的点为根的若干无交连通子树。
则，对于一个询问 [l,r]，如果我们只保留 [l,r] 范围内的点，根据性质四，它将构成以 [l,\min{r,g_l}] 中的点为根的若干无交连通子树。
显然，当且仅当选择的点对 (x,y) 位于同一棵子树中，\operatorname{LCA}(x,y) 会在 [l,r] 范围内。
中选择两个点，它们的乘积和为：
即 T 中所有点权和的平方。
综上，我们要求出的就是仅保留 [l,r] 中的点时， 这些子树点权和的平方和。
据性质一，[1,l) 中的点不可能出现在 [l,r] 中的点的子树里，因此我们实际上可以不用只保留 [l,r] 中的点，而是保留 [1,r] 中的所有点。
于是假设可以离线，把询问按照右端点排序，然后就能把节点一个个加入来扩展右端点了。加入的过程需要更新所有祖先的子树点权和的平方，询问时就是对 [l,\min{r,g_i}] 区间求和。
但这样时间复杂度未免过于浪费，考虑把这个过程分块一下，即每加入 S 个点就重构一次（遍历整棵树统计所有点的子树点权和，并对其平方做前缀和方便区间查询），不满 S 个点根据具体询问，直接求出这个点在谁的子树中更新对应子树点权和并更新答案即可。
至于如何判断一个点 x 在谁的子树中，根据性质三，[l,\min{r,g_i}] 最多只有两种不同的深度，我们求出 x 深度为 dep_l+1 的祖先 t（可以使用 O(n\log n) 预处理+O(1) 查询的长链剖分求 k 级祖先算法），如果 t\le g_i 说明 x 在 t 的子树中，否则说明 x 在 f_t 的子树中。
然后发现我们实际上没有必要离线，可以事先预处理出这些信息存下来在线做。
即对于所有 i=1\sim\lceil\frac nS\rceil，记录下仅保留标号在 1\sim (i-1)\times S 范围内的点时，所有点的子树点权和 w_{i,x}，及其平方的前缀和 s_{i,x}。
假设询问的是 [l,r]，按照先前的方式，我们在加入 1\sim (\lceil\frac rS\rceil-1)\times S 中的所有点的基础上，枚举 (\lceil\frac rS\rceil-1)\times S+1\sim r 中的点，求出它在谁的子树中更新对应子树点权和并更新答案。
PS: 卡常。本人长链被卡，重链剖分与倍增择选复杂度优的跑然后调了调块长才过。
Code
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
using namespace std;
namespace FastIO{
#define FS 100000
#define tc() (FA==FB&&(FB=(FA=FI)+fread(FI,1,FS,stdin),FA==FB)?EOF:*FA++)
#define pc(c) (FC==FE&&(clear(),0),*FC++=c)
int OT;char oc,FI[FS],FO[FS],OS[FS],*FA=FI,*FB=FI,*FC=FO,*FE=FO+FS;
I void clear() {fwrite(FO,1,FC-FO,stdout),FC=FO;}
Tp I void read(Ty& x) {x=0;W(!isdigit(oc=tc()));W(x=(x<<3)+(x<<1)+(oc&15),isdigit(oc=tc()));}
Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}
Tp I void writeln(Ty x) {W(OS[++OT]=x%10+48,x/=10);W(OT) pc(OS[OT--]);pc('\n');}
}using namespace FastIO;
Cn int N=250002,M=510+2,p=998244353;
int n,q,sz,a[N],f[N],S[M][N],SS[M][N],fa[N],dep[N],g[N],bl[N],mx[N],dfn[N],bk[N],cnt,top[N],st[N][20],wei[N],lg[N];
int fir[N],nxt[N],son[N],tot;
I void Add(CI x,CI y){nxt[++tot]=fir[x],fir[x]=tot,son[tot]=y;}
I void addup(int& x,CI y){(x+=y)>=p&&(x-=p);}
I int add(CI x,CI y){return (x+y)-(x+y>=p?p:0);}
I void DFS1(CI x){bl[x]=1;for(RI i=fir[x];i;i=nxt[i]) dep[son[i]]=dep[x]+1,DFS1(son[i]),bl[x]+=bl[son[i]],bl[mx[x]]<bl[son[i]]&&(mx[x]=son[i]);}
I void DFS2(CI x){if(bk[dfn[x]=++cnt]=x,mx[x]) top[mx[x]]=top[x],wei[mx[x]]=wei[x],DFS2(mx[x]);for(RI i=fir[x];i;i=nxt[i]) son[i]^mx[x]&&(top[son[i]]=son[i],wei[son[i]]=wei[x]+1,DFS2(son[i]),0);}
I int Jump1(RI x,RI k){W(k>=dfn[x]-dfn[top[x]]+1&&x!=1) k-=(dfn[x]-dfn[top[x]]+1),x=f[top[x]];return bk[dfn[x]-k];}
I int Jump2(RI x,CI k){for(RI i=lg[k];~i;i--) k>>i&1&&(x=st[x][i]);return x;}
I int Jump(CI x,CI k){return wei[x]<lg[k]?Jump1(x,k):Jump2(x,k);}
I int Q(CI l,CI r){
RI i,t,X=add(SS[bl[r]][g[l]],p-SS[bl[r]][l-1]);
for(i=max(l,(bl[r]-1)*sz+1);i<=r;i++) t=Jump(i,max(0,dep[i]-dep[l]-1)),t>g[l]&&(t=f[t]),fa[i]=t,addup(X,p-1LL*S[bl[r]][t]*S[bl[r]][t]%p),addup(S[bl[r]][t],a[i]),addup(X,1LL*S[bl[r]][t]*S[bl[r]][t]%p);
for(i=max(l,(bl[r]-1)*sz+1);i<=r;i++) addup(S[bl[r]][fa[i]],p-a[i]);return X;
}
int main(){
freopen("slight.in","r",stdin),freopen("slight.out","w",stdout);
RI i,j,lst=0,l,r;for(read(n,q),lg[0]=-1,i=1;i<=n;i++) read(a[i]),lg[i]=lg[i/2]+1;
for(dep[1]=j=1,i=2;i<=n;i++){read(f[i]),Add(f[i],i),dep[i]=dep[st[i][0]=f[i]]+1;W(j<=f[i]) g[j++]=i-1;}W(j<=n) g[j++]=n;
for(j=1;j<=lg[n];j++) for(i=1;i<=n;i++) st[i][j]=st[st[i][j-1]][j-1];
for(DFS1(1),DFS2(wei[1]=1),sz=n/M+2,i=1;i<=n;i++) bl[i]=(i-1)/sz+1;for(i=1;i<=bl[n];i++){
for(j=1;j<=(i-1)*sz;j++) S[i][j]=a[j];for(j=n;j;j--) addup(S[i][f[j]],S[i][j]);for(j=1;j<=n;j++) SS[i][j]=add(SS[i][j-1],1LL*S[i][j]*S[i][j]%p);
}W(q--) read(l,r),writeln(lst=Q(l^lst,r^lst));return clear(),0;
}腾讯云开发者
