Luogu P5280 [ZJOI2019]线段树

送我退役的神题，但不得不说是ZJOIDay1最可做的一题了

先说一下考场的ZZ想法以及出来后YY的优化版吧

首先发现每次操作其实就是统计出增加的节点个数（原来的不会消失）

所以我们只要统计出线段树上每个节点在进行了\(t\)次操作（有\(2^t\)棵树）是某个点为\(1\)的总个数，令这个值为\(f_x\)

然后考场上用了一种记录该节点+左儿子+右儿子状态的方法，这样可以把答案的贡献全部算到这个点上

但是这样细节巨多且容易算重（漏），所以考场上码了\(200+\)行最后没调出大样例

后来想了一种记录该节点+父亲状态的方法，但是这样贡献就要算重，可能可以利用矩阵来做

接下来我们考虑正解，我们发现细分每一个点的性质其实就只有\(4\)种：

直接在该点进行赋值操作，那么此时显然多出的\(2^{t-1}\)棵树的这个节点都是可行的，直接\(f_x+=2^{t-1}\)
直接在该点进行pushdown，那么此时显然多出的树上这个点没有增加（\(1\to 0\)了，\(0\)还是\(0\)），\(f_x\)不变
该点不在修改区间内，那么状态直接被复制一遍，\(f_x*=2\)
最麻烦的一种，该点（包括这个点）到根的路径上至少有一个点的tag为\(1\)，我们令这个方案数为\(g_x\)，那么就有\(f_x+=g_x\)

然后开始考虑怎么维护\(g_x\)，那么类似地分成\(3\)类讨论：

直接在该点进行pushdown，那么新增的树的这个节点到根的路径上都不会tag等于\(1\)的情况，\(g_x\)不变
直接再该点打标记，多出的\(2^{t-1}\)棵树中它的子树内的点显然都有\(g_x+=2^{t-1}\)
该点被访问但不在区间内，和上面一样，直接\(g_x*=2\)

那么我们显然还是可以用线段树来维护\(f,g\)，具体考虑到修改\(g\)的时候要集体\(*2\)不好维护（其实开一个乘法标记和两个加法标记即可），我们直接在最外面乘上\(2^t\)，然后把访问过的节点都\(\div2\)即可

然后\(g\)的标记怎么下传呢，我们发现可以再开一个懒标记\(tag\)表示这个点有多少次直接修改，然后下传的时候用这个来改\(g\)

具体地就是先把该除的\(2\)除了，然后加上\(\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\dots+\frac{1}{2^{tag}}=1-\frac{1}{2^{tag}}\)即可

附上超级简短的CODE

#include<cstdio>

#include<cctype>

#define RI register int

#define CI const int&

#define Tp template <typename T>

using namespace std;

const int N=100005,mod=998244353,inv2=499122177;

int n,m,opt,x,y,ipw[N],ret,prod;

class FileInputOutput

{

	private:

		static const int S=1<<21;

		#define tc() (A==B&&(B=(A=Fin)+fread(Fin,1,S,stdin),A==B)?EOF:*A++)

		#define pc(ch) (Ftop<S?Fout[Ftop++]=ch:(fwrite(Fout,1,S,stdout),Fout[(Ftop=0)++]=ch))

		char Fin[S],Fout[S],*A,*B; int Ftop,pt[15];

	public:

		Tp inline void read(T& x)

		{

			x=0; char ch; while (!isdigit(ch=tc()));

			while (x=(x<<3)+(x<<1)+(ch&15),isdigit(ch=tc()));

		}

		Tp inline void write(T x)

		{

			if (!x) return (void)(pc('0'),pc('\n')); RI ptop=0;

			while (x) pt[++ptop]=x%10,x/=10; while (ptop) pc(pt[ptop--]+48); pc('\n');

		}

		inline void Fend(void)

		{

			fwrite(Fout,1,Ftop,stdout);

		}

		#undef tc

		#undef pc

}F;

inline void inc(int& x,CI y)

{

	if ((x+=y)>=mod) x-=mod;

}

inline void dec(int& x,CI y)

{

	if ((x-=y)<0) x+=mod;

}

inline int sum(CI x,CI y)

{

	int t=x+y; return t>=mod?t-mod:t;

}

inline int sub(CI x,CI y)

{

	int t=x-y; return t<0?t+mod:t;

}

class Segment_Tree

{

	private:

		struct segment

		{

			int f,g,tag;

		}node[N<<2];

		#define F(x) node[x].f

		#define G(x) node[x].g

		#define T(x) node[x].tag

		inline void pushdown(CI now)

		{

			if (!T(now)) return; int& add=T(now); T(now<<1)+=add; T(now<<1|1)+=add;

			G(now<<1)=sum(1LL*G(now<<1)*ipw[add]%mod,sub(1,ipw[add]));

			G(now<<1|1)=sum(1LL*G(now<<1|1)*ipw[add]%mod,sub(1,ipw[add])); add=0;

		}

	public:

		inline void modify(CI beg,CI end,CI now=1,CI l=1,CI r=n)

		{

			dec(ret,F(now)); F(now)=1LL*F(now)*inv2%mod; G(now)=1LL*G(now)*inv2%mod;

			if (beg<=l&&r<=end) inc(F(now),inv2),inc(G(now),inv2);

			if (l>end||r<beg) inc(F(now),G(now)),inc(G(now),G(now)); inc(ret,F(now));

			if (l>end||r<beg) return; if (beg<=l&&r<=end) return (void)(++T(now));

			pushdown(now); int mid=l+r>>1; modify(beg,end,now<<1,l,mid); modify(beg,end,now<<1|1,mid+1,r);

		}

		#undef F

		#undef G

		#undef T

}SEG;

int main()

{

	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);

	RI i; for (F.read(n),F.read(m),ipw[0]=i=1;i<=m;++i)

	ipw[i]=1LL*ipw[i-1]*inv2%mod; for (i=prod=1;i<=m;++i)

	{

		F.read(opt); if (opt^1) F.write(1LL*ret*prod%mod);

		else inc(prod,prod),F.read(x),F.read(y),SEG.modify(x,y);

	}

	return F.Fend(),0;

}

巴特西

Luogu P5280 [ZJOI2019]线段树

最新文章

热门文章