「ZJOI2019」线段树

传送门

Description

Solution

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！