原文链接www.cnblogs.com/zhouzhendong/p/ZJOI2019Day1T2.html
前言
在LOJ交了一下我的代码,发现它比选手机快将近 4 倍。
题解
对于线段树上每一个节点,维护以下信息:
1. 这个点为 1 的概率。
2. 这个点为 0 ,且它有祖先是 1 的概率。
其中,第一种东西在维护了 2. 的情况下十分好求。
第二种东西,只有两类:
1. 一次线段树操作涉及到所有的节点,显然只要乘 0.5 。
2. 某些节点打了标记之后,它的所有子孙都被他影响了。于是我们加个区间修改就好了。
时间复杂度 $O(n\log n)$ 。跑的很快。
好像有一种矩阵乘法的做法,但是它可能会被卡常数。
代码
#include <bits/stdc++.h> #define clr(x) memset(x,0,sizeof (x)) #define For(i,a,b) for (int i=a;i<=b;i++) #define Fod(i,b,a) for (int i=b;i>=a;i--) #define pb(x) push_back(x) #define mp(x,y) make_pair(x,y) #define fi first #define se second #define outval(x) printf(#x" = %d\n",x) #define outtag(x) puts("----------------"#x"----------------"); #define outvec(x) printf("vec "#x" = ");For(_i,0,(int)x.size()-1)printf("%d ",x[i]);puts(""); #define outarr(x,L,R) printf(#x"[%d..%d] = ",L,R);For(__i,L,R)printf("%d ",x[i]);puts(""); using namespace std; typedef long long LL; typedef unsigned long long ULL; LL read(){ LL f=0,x=0; char ch=getchar(); while (!isdigit(ch)) f|=ch=='-',ch=getchar(); while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); return f?-x:x; } const int N=100005,mod=998244353; int Pow(int x,int y){ int ans=1; for (;y;y>>=1,x=(LL)x*x%mod) if (y&1) ans=(LL)ans*x%mod; return ans; } void Add(int &x,int y){ if ((x+=y)>=mod) x-=mod; } void Del(int &x,int y){ if ((x-=y)<0) x+=mod; } int n,m,inv2,P=1; int ans=0; int p[N<<2]; int p2[N<<2],add[N<<2]; void build(int rt,int L,int R){ p[rt]=p2[rt]=0,add[rt]=1; if (L==R) return; int mid=(L+R)>>1,ls=rt<<1,rs=ls|1; build(ls,L,mid); build(rs,mid+1,R); } void pushson(int rt,int v){ add[rt]=(LL)add[rt]*v%mod; p2[rt]=((LL)v*p2[rt]%mod+(LL)(mod+1-v)*(mod+1-p[rt])%mod)%mod; } void pushdown(int rt){ if (add[rt]!=1){ int ls=rt<<1,rs=ls|1; pushson(ls,add[rt]); pushson(rs,add[rt]); add[rt]=1; } } void update(int rt,int L,int R,int xL,int xR){ if (R<xL||L>xR){ Del(ans,p[rt]); p[rt]=((LL)p2[rt]*inv2+p[rt])%mod; Add(ans,p[rt]); p2[rt]=(LL)p2[rt]*inv2%mod; return; } int mid=(L+R)>>1,ls=rt<<1,rs=ls|1; if (xL<=L&&R<=xR){ //no pushdown Del(ans,p[rt]); p[rt]=(LL)(p[rt]+1)*inv2%mod; Add(ans,p[rt]); p2[rt]=(LL)p2[rt]*inv2%mod; if (L!=R){ pushson(ls,inv2); pushson(rs,inv2); } return; } pushdown(rt); Del(ans,p[rt]); p[rt]=(LL)p[rt]*inv2%mod; Add(ans,p[rt]); p2[rt]=(LL)p2[rt]*inv2%mod; update(ls,L,mid,xL,xR); update(rs,mid+1,R,xL,xR); } int main(){ n=read(),m=read(); build(1,1,n); inv2=(mod+1)/2; while (m--){ int type=read(); if (type==1){ P=(LL)P*2%mod; int L=read(),R=read(); update(1,1,n,L,R); } else { int val=(LL)ans*P%mod; printf("%d\n",val); } } return 0; }