bzoj 4785: [Zjoi2017]树状数组【树套树】

参考：https://www.cnblogs.com/ljh2000-jump/p/6686960.html

由于操作反过来了，所以显然树状数组维护后缀和，所以本来想查询(1,r)-(1,l-1)，现在变成了(r,n)-(l-1,n)；

然后在mod 2意义下进行，每次又是+1，就相当于是异或操作了；

所以现在这样的树状数组和正确的差别就在l-1和r这两个位置上，所以只要维护(x,y)(x<=y)表示xy操作次数在mod 2意义下相同的概率即可。

使用线段树套线段树实现；

#include<iostream>

#include<cstdio>

using namespace std;

const int N=200005,mod=998244353;

int n,m,tot,rt[N<<3],ans;

struct wai

{

	int ls,rs,p;

}t[N*180];

int read()

{

	int r=0,f=1;

	char p=getchar();

	while(p>'9'||p<'0')

	{

		if(p=='-')

			f=-1;

		p=getchar();

	}

	while(p>='0'&&p<='9')

	{

		r=r*10+p-48;

		p=getchar();

	}

	return r*f;

}

int ksm(int a,int b)

{

	int r=1;

	while(b)

	{

		if(b&1)

			r=1ll*r*a%mod;

		a=1ll*a*a%mod;

		b>>=1;

	}

	return r;

}

void build(int ro,int l,int r)

{

	tot=max(tot,ro);

	if(l==r)

		return;

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

	build(ro<<1,l,mid);

	build(ro<<1|1,mid+1,r);

}

int clc(int x,int y)

{

	return (1ll*x*y%mod+1ll*(1-x+mod)*(1-y+mod)%mod)%mod;

}

void nupdate(int &ro,int l,int r,int ql,int qr,int v)

{

	if(!ro)

	{

		ro=++tot;

		t[ro].p=1;

	}

	if(ql<=l&&r<=qr)

	{

		t[ro].p=clc(t[ro].p,v);

		return;

	}

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

	if(ql<=mid)

		nupdate(t[ro].ls,l,mid,ql,qr,v);

	if(qr>mid)

		nupdate(t[ro].rs,mid+1,r,ql,qr,v);

}

void wupdate(int ro,int l,int r,int ql,int qr,int dw,int up,int v)

{

	if(ql<=l&&r<=qr)

	{

		nupdate(rt[ro],0,n+1,dw,up,v);

		return;

	}

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

	if(ql<=mid)

		wupdate(ro<<1,l,mid,ql,qr,dw,up,v);

	if(qr>mid)

		wupdate(ro<<1|1,mid+1,r,ql,qr,dw,up,v);

}

void nques(int &ro,int l,int r,int p)

{

	if(!ro)

		return;

	ans=clc(ans,t[ro].p);

	if(l==r)

		return;

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

	if(p<=mid)

		nques(t[ro].ls,l,mid,p);

	else

		nques(t[ro].rs,mid+1,r,p);

}

void wques(int ro,int l,int r,int px,int py)

{

	if(rt[ro])

		nques(rt[ro],0,n+1,py);

	if(l==r)

		return;

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

	if(px<=mid)

		wques(ro<<1,l,mid,px,py);

	else

		wques(ro<<1|1,mid+1,r,px,py);

}

int main()

{

	n=read(),m=read();

	build(1,0,n);

	for(int i=1;i<=m;i++)

	{

		int o=read(),l=read(),r=read();

		if(o==1)

		{

			int p=ksm(r-l+1,mod-2);

			if(l>1)

			{

				wupdate(1,1,n,1,l-1,l,r,(1-p+mod)%mod);

				nupdate(rt[0],1,n,1,l-1,0);

			}

			if(r<n)

			{

				wupdate(1,1,n,l,r,r+1,n,(1-p+mod)%mod);

				nupdate(rt[0],1,n,r+1,n,0);

			}

			if(l!=r)

				wupdate(1,1,n,l,r,l,r,(1-p*2+mod*2)%mod);

			nupdate(rt[0],1,n,l,r,p);

		}

		else

		{

			ans=1;

			if(l==1)

				nques(rt[0],1,n,r);

			else

				wques(1,1,n,l-1,r);

			printf("%d\n",ans);

		}

	}

	return 0;

}

巴特西

bzoj 4785: [Zjoi2017]树状数组【树套树】

最新文章

热门文章