线段树区间定位

模拟线段树上的若干操作，然后查询相关的计数信息。

学习自 https://www.luogu.com/article/qh85y10k。

区间定位数

定义 $[l, r]$ 的区间定位数，为（广义）线段树上 $[l, r]$ 最少拆为多少个区间的并。

区间 $[l, r]$ 在线段树上的区间定位数等于 $2 \times (r - l + 1) - ∣ S ∣$ ，其中 $S$ 为 $[l, r]$ 完全包含的区间数。

P7143

对于 $[1, n]$ 的标准线段树求所有区间的区间定位数之和。

前半部分拆开 $O (1)$ 算，后半部分 $∣ S ∣ = \sum l \times (n - r + 1) = (n + 1) \times \sum l + \sum l \times r$ ，分治维护 $c n t, \sum l, \sum r, \sum l \times r$ 。

int n;
map<int,int> cnt,sl,sr,slr,res;
void sovle(int n){
	if(cnt[n])return ;
	if(n==1){
		cnt[n]=sl[n]=sr[n]=slr[n]=res[n]=1;
		return ;
	}
	int mid=(n+1)>>1,vmid=mid%mod;
	sovle(mid),sovle(n-mid);
	cnt[n]=(cnt[mid]+cnt[n-mid]+1)%mod;
	sl[n]=(sl[mid]+sl[n-mid]+cnt[n-mid]*vmid+1)%mod;
	sr[n]=(sr[mid]+sr[n-mid]+cnt[n-mid]*vmid+n)%mod;
	slr[n]=(slr[mid]+slr[n-mid]+(sl[n-mid]+sr[n-mid])*vmid+cnt[n-mid]*vmid%mod*vmid+n)%mod;
	res[n]=((n%mod+1)*sl[n]+mod-slr[n])%mod;
}
int sum1(int n){return n*(n+1)/2%mod;}
int sum2(int n){return n*(n+1)%mod*(2*n+1)%mod*ni(6)%mod;}
void work(){
	n=read();sovle(n);
	int ans=2*(sum1(n%mod)*(n%mod+1)+mod-sum2(n%mod))%mod;
	printf("%lld\n",(ans+mod-res[n])%mod);
}

区间定位

（广义）线段树上， $[l, r]$ 的区间定位可以描述为：

取出 $[l - 1, l - 1]$ 和 $[r + 1, r + 1]$ 的 lca $U$ 。 $[l - 1, l - 1]$ 到 $U$ 的左儿子（不含）的链上是左儿子的节点的右兄弟。右边同理。

额外建出 $[0, 0]$ 和 $[n + 1, n + 1]$ 。

P5210

对于 $[1, n]$ 的广义线段树 $q$ 次询问 $u, l, r$ 求 $\sum_{v \in S} d i s (u, v)$ 。

$\sum_{v \in S} d i s (u, v) = ∣ S ∣ \times d e p_{u} + \sum_{v \in S} d e p_{v} - 2 \times \sum_{v \in S} d e p_{l c a (u, v)}$ 。设 $c l_{u}, c r_{u}, s l_{u}, s r_{u}$ 表示 $u$ 的所有祖先的左偏/右偏儿子的右兄弟/左兄弟的数量/深度和，求出 lca 后差分求出。

对于 lca，分类讨论。如果 $u$ 在 $U$ 子树外，lca 为 $U$ 。否则假设在 $U$ 的左子树内，求出 $u$ 和 $[l - 1, l - 1]$ 的 lca $x$ 。对于 $U$ 右子树中的区间 lca 为 $U$ ；左子树 $x$ 一下的 lca 为 $x$ ；左子树 $x$ 以上都是 $u$ 的祖先，lca 为区间的父亲，特判 $u$ 在 $x$ 的右子树中时 $u$ 和 $x$ 的右儿子的 lca 不为 $x$ 而是 $x$ 的右儿子。

int n,idx,rt,q;
int ls[maxn],rs[maxn],fa[maxn],pos[maxn];
int dfs(int l,int r){
	if(l>r)return 0;
	if(l==r)return pos[l]=++idx;
	int id=++idx,p=read();
	ls[id]=dfs(l,p),rs[id]=dfs(p+1,r);
	return id;
}
int st[20][maxn],dfn[maxn],tim,dep[maxn],siz[maxn];
int cl[maxn],cr[maxn],sl[maxn],sr[maxn];
void dfs(int u){
	if(!u)return ;
	dep[u]=dep[fa[u]]+1;siz[u]=1;
	cl[u]=cl[fa[u]]+(u==ls[fa[u]])*(rs[fa[u]]!=0),sl[u]=sl[fa[u]]+(u==ls[fa[u]])*dep[u];
	cr[u]=cr[fa[u]]+(u==rs[fa[u]])*(ls[fa[u]]!=0),sr[u]=sr[fa[u]]+(u==rs[fa[u]])*dep[u];
	st[0][dfn[u]=++tim]=fa[u];
	dfs(ls[u]),dfs(rs[u]);
	siz[u]+=siz[ls[u]]+siz[rs[u]];
}
int mmax(int u,int v){return dfn[u]<dfn[v]?u:v;}
int lca(int u,int v){
	if(u==v)return u;
	u=dfn[u],v=dfn[v];
	if(u>v)swap(u,v);u++;
	int k=__lg(v-u+1);
	return mmax(st[k][u],st[k][v-(1<<k)+1]);
}
bool in(int u,int v){return dfn[u]<=dfn[v]&&dfn[v]<dfn[u]+siz[u];}
void work(){
	n=read();rt=dfs(1,n);
	pos[0]=++idx;ls[++idx]=pos[0];rs[idx]=rt;rt=idx;
	pos[n+1]=++idx;rs[++idx]=pos[n+1];ls[idx]=rt;rt=idx;
	for(int i=1;i<=idx;i++)fa[ls[i]]=fa[rs[i]]=i;fa[0]=0;
	dfs(rt);
	for(int j=1;j<20;j++){
		for(int i=1;i+(1<<j)-1<=idx;i++)st[j][i]=mmax(st[j-1][i],st[j-1][i+(1<<j-1)]);
	}
	q=read();
	while(q--){
		int u=read(),l=read(),r=read(),tp=lca(pos[l-1],pos[r+1]);
		int num=cl[pos[l-1]]-cl[ls[tp]]+cr[pos[r+1]]-cr[rs[tp]];
		int sum=sl[pos[l-1]]-sl[ls[tp]]+sr[pos[r+1]]-sr[rs[tp]];
		int ans=num*dep[u]+sum;
		if(!in(tp,u)||u==tp)ans-=2*dep[lca(u,tp)]*num;
		else if(in(ls[tp],u)){
			int x=lca(pos[l-1],u);
			ans-=2*dep[tp]*(cr[pos[r+1]]-cr[rs[tp]]);
			ans-=2*(sl[x]-sl[ls[tp]]-(cl[x]-cl[ls[tp]]));
			if(in(rs[x],u))ans-=2;
			ans-=2*dep[x]*(cl[pos[l-1]]-cl[x]);
		}
		else{
			int x=lca(pos[r+1],u);
			ans-=2*dep[tp]*(cl[pos[l-1]]-cl[ls[tp]]);
			ans-=2*(sr[x]-sr[rs[tp]]-(cr[x]-cr[rs[tp]]));
			if(in(ls[x],u))ans-=2;
			ans-=2*dep[x]*(cr[pos[r+1]]-cr[x]);
		}
		printf("%lld\n",ans);
	}
}

区间修改的 tag 下放

按对 $[l, r]$ 做区间操作时 tag 的下放对节点的 tag 的不同影响将节点分为 $5$ 类。

1.访问到并继续递归的结点。不管之前什么样，现在肯定没标记。

2.区间定位点。不管之前什么样，现在肯定有标记。

3. $2$ 的真后代。不变。

4. $1$ 的儿子，且不是 $1, 2$ 。如果有祖先或自己有标记则有标记。

5. $4$ 的真后代。不变。

维护 $f_{i}, g_{i}$ 表示节点/节点及祖先有没有标记即可转移。

P5280

$q$ 次操作。有 $\frac{1}{2}$ 的概率对 $[l, r]$ 做区间修改；询问期望有几个节点有 tag。

对于 $1$ 类点， $\frac{f _{i}^{'}}{2} \to f_{i}, \frac{g _{i}^{'}}{2} \to g_{i}$ ；对于 $2$ 类点， $\frac{f _{i}^{'} + 1}{2} \to f_{i}, \frac{g _{i}^{'} + 1}{2} \to g_{i}$ ；对于 $4$ 类点， $\frac{f _{i}^{'} + g _{i}^{'}}{2} \to f_{i}$ 。

线段树维护即可。可以维护 $g g_{i} = 1 - g_{i}$ 然后 $\frac{g g _{i}^{'}}{2} \to g g_{i}$ ，维护除了几次 $2$ 。

int n,q,ans;
int inv[maxn];
#define mid (l+r>>1)
#define ls nd<<1
#define rs nd<<1|1
int f[maxn<<2],g[maxn<<2],tag[maxn<<2];
void build(int nd,int l,int r){
	g[nd]=1;
	if(l==r)return ;
	build(ls,l,mid),build(rs,mid+1,r);
}
void inc(int &u,int v){((u+=v)>=mod)&&(u-=mod);}
void downf(int nd,int w){
	inc(ans,mod-f[nd]),f[nd]=(f[nd]+w)*inv[1]%mod,inc(ans,f[nd]);
}
void downg(int nd,int w){
	g[nd]=g[nd]*inv[w]%mod,tag[nd]+=w;
}
void down(int nd){
	downg(ls,tag[nd]),downg(rs,tag[nd]),tag[nd]=0;
}
void updata(int nd,int l,int r,int ql,int qr){
	if(l>=ql&&r<=qr){downf(nd,1),downg(nd,1);return ;}
	if(tag[nd])down(nd);
	if(ql<=mid)updata(ls,l,mid,ql,qr);
	else downf(ls,mod+1-g[ls]);
	if(qr>mid)updata(rs,mid+1,r,ql,qr);
	else downf(rs,mod+1-g[rs]);
	downf(nd,0);g[nd]=(g[nd]+1)*inv[1]%mod;
}
void work(){
	n=read();q=read();int mul=1;
	build(1,1,n);
	inv[0]=1,inv[1]=(mod+1)/2;for(int i=2;i<=q;i++)inv[i]=inv[i-1]*inv[1]%mod;
	while(q--){
		int op=read();
		if(op==1){
			mul=mul*2%mod;
			int l=read(),r=read();
			updata(1,1,n,l,r);
		}
		else printf("%lld\n",ans*mul%mod);
	}
}

P6630

$k$ 次随机选取 $[l, r]$ 做区间修改，询问最后期望有几个节点有 tag。

对于 $1$ 类点， $f_{i} = g_{i} = 0$ ；对于 $2$ 类点， $f_{i} = g_{i} = 1$ ；对于 $3$ 类点， $f_{i} = f_{i}^{'}, g_{i} = 1$ ；对于 $4$ 类点， $f_{i} = g_{i} = g_{i}^{'}$ ；对于 $5$ 类点， $f_{i} = f_{i}^{'}, g_{i} = g_{i}^{'}$ 。

对于区间 $[l, r]$ ，父亲为 $[f l, f r]$ ，选取 $[ql, q r]$ 使得 $[l, r]$ 成为某类点的方案数分别为。记 $v a l_{i} = \frac{i \times ( i + 1 )}{2}$ 。成为 $1$ 类点， $v a l_{n} - v a l_{l - 1} - v a l_{n - r} - l \times (n - r + 1)$ ；成为 $2$ 类点， $l \times (n - r + 1) - f l \times (n - f r + 1)$ ；成为 $3$ 类点， $f l \times (n - f r + 1)$ ；成为 $4$ 类点， $v a l_{l - 1} + v a l_{n - r} - v a l_{f l - 1} - v a l_{n - f r}$ ；成为 $5$ 类点， $v a l_{f l - 1} + v a l_{n - f r}$ ；

维护 $f, g, 1$ 的 $3 \times 3$ 矩阵。

int n,k,ans,inv;
int val(int n){return n*(n+1)/2%mod;}
void calc(int l,int r,int fl,int fr){
	mat a;
	a.e[2][2]=1;
	int p1=(val(n)-val(l-1)-val(n-r)-l*(n-r+1)%mod+3*mod)*inv%mod;
	int p2=(l*(n-r+1)%mod-fl*(n-fr+1)%mod+mod)*inv%mod;
	int p3=fl*(n-fr+1)%mod*inv%mod;
	int p4=(val(l-1)+val(n-r)-val(fl-1)-val(n-fr)+2*mod)*inv%mod;
	int p5=(val(fl-1)+val(n-fr))*inv%mod;
	// assert((p1+p2+p3+p4+p5)%mod==1);
	(a.e[2][0]+=p2)%=mod;
	(a.e[2][1]+=p2)%=mod;
	(a.e[0][0]+=p3)%=mod;
	(a.e[2][1]+=p3)%=mod;
	(a.e[1][0]+=p4)%=mod;
	(a.e[1][1]+=p4)%=mod;
	(a.e[0][0]+=p5)%=mod;
	(a.e[1][1]+=p5)%=mod;
	a=ksm(a,k);
	(ans+=a.e[2][0])%=mod;
}
void dfs(int l,int r,int fl,int fr){
	if(l>r)return ;
	calc(l,r,fl,fr);
	if(l==r)return ;
	int p=read();
	dfs(l,p,l,r),dfs(p+1,r,l,r);
}
void work(){
	n=read();k=read();inv=ni(val(n));
	dfs(1,n,0,n);
	printf("%lld\n",ans);
}

🪴 Quartz 4.0

Explorer