「ZJOI2019」线段树

传送门

Description

线段树的核心是懒标记，下面是一个带懒标记的线段树的伪代码，其中 tag 数组为懒标记：

其中函数\(Lson(Node)\)表示\(Node\)的左儿子，\(Rson(Node)\)表示\(Node\)的右儿子。

有一棵 \([1,n]\)上的线段树，编号为\(1\) 。初始时什么标记都没有。

每次修改会把当前所有的线段树复制一份，然后对于这些线段树实行一次区间修改操作。

每次修改后线段树棵数翻倍，第 \(i\)次修改后，线段树共有 \(2^i\) 棵。

每次询问这些线段树中有标记的点的总数。

询问个数\(q\)，\(1\leq n,q \leq 10^5\)

Solution

一道很有特色的题目

考察的是对线段树区间修改的认知

\(f_x\)表示\(x\)号节点有标记的线段树占的比例

\(g_x\)表示\(x\)号节点到根路径上有标记的线段树占的比例

首先，把每次区间修改的点分成\(5\)类

在找到目标节点前经过的节点，它们的标记全部下传，所以\(f_x=\frac{1}{2}f_x,g_x=\frac{1}{2}g_x\)

目标节点，完全被覆盖，递归过程中被全部被打上标记，\(f_x=\frac{1}{2}+\frac{1}{2}f_x,g_x=\frac{1}{2}+\frac{1}{2}g_x\)

\(2\)类节点的子树内的其它节点，递归过程中不变，\(f_x=f_x,g_x=\frac{1}{2}+\frac{1}{2}g_x\)

在\(pushdown\)中被访问到的节点，但完全不被覆盖，\(f_x=\frac{1}{2}f_x+\frac{1}{2}g_x,g_x=g_x\)

\(4\)类节点的子树内的其它节点，递归过程不变，\(f_x=f_x,g_x=g_x\)

同时，我们去要维护子树内的\(f_x\)的和

对于\(g_x\)的修改，我们采用打懒标记的方式，当找到\(2\)类节点时，直接对它打上\(*\frac{1}{2}\)的标记

Code

#include<bits/stdc++.h>

#define max(a,b) ((a)>(b)?(a):(b))

#define min(a,b) ((a)<(b)?(a):(b))

#define ll long long

#define reg register

inline int read()

{

	reg int x=0,f=1;char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}

	return x*f;

}

const int MN=1e5+5,mod=998244353,Inv2=499122177;

int N,M;

int f[MN<<3],g[MN<<3],sf[MN<<3],lz[MN<<3];

#define Add(x,y) (((x)+(y))%mod)

#define Mul(x,y) (1ll*(x)*(y)%mod)

#define ls (x<<1)

#define rs (x<<1|1)

void C(int x,int val){lz[x]=Mul(lz[x],val);g[x]=Add(Mul(g[x],val),1-val+mod);}

void down(int x){if(lz[x]^1)C(ls,lz[x]),C(rs,lz[x]),lz[x]=1;}

void up(int x){sf[x]=Add(f[x],Add(sf[ls],sf[rs]));}

void Build(int x,int l,int r)

{

	lz[x]=1;if(l==r) return;

	reg int mid=(l+r)>>1;

	Build(ls,l,mid);Build(rs,mid+1,r);

}

void Modi(int x,int l,int r,int a,int b)

{

	if(r<a||l>b)

	{

		f[x]=Mul(Inv2,Add(f[x],g[x]));

		up(x);return;

	}

	if(l>=a&&r<=b)

	{

		f[x]=Add(Inv2,Mul(Inv2,f[x]));

		C(x,Inv2);up(x);return;

	}

	down(x);f[x]=Mul(Inv2,f[x]);g[x]=Mul(Inv2,g[x]);

	reg int mid=(l+r)>>1;

	Modi(ls,l,mid,a,b);

	Modi(rs,mid+1,r,a,b);

	up(x);

}

int main()

{

	N=read();M=read();Build(1,1,N);

	reg int opt,l,r,Num=1;

	while(M--)

	{

		opt=read();

		if(opt==2) printf("%d\n",Mul(sf[1],Num));

		else l=read(),r=read(),Modi(1,1,N,l,r),Num=Mul(2ll,Num);

	}

	return 0;

}

Blog来自PaperCloud，未经允许，请勿转载，TKS！

巴特西

「ZJOI2019」线段树

传送门

Description

Solution

Code

最新文章

热门文章