解题报告

ZJOI又双叒叕出线段树，我又双叒叕没做出来。Orz%%%zhouzhendong。

定义 $f_{i,0}​$ 表示线段树节点 $i​$ 没有标记，但是祖先有标记的概率，$f_{i,1}​$ 表示线段树节点 $i​$ 有标记的概率。

每次插入大概就是分 $4​$ 种情况分类讨论一下：

1. 在修改路径上的节点 $x$ ：因为有Pushdown的存在，复制出来的树中 $x$ 祖先和自己一定都没有标记，所以 $f_{i,0}={f'_{i,0}\over 2},f_{i,1}={f'_{i,1}\over 2}$ 。
2. 是修改路径上节点的儿子并且不在修改路径上的点 $x$ ：$x$ 自己不受影响，但祖先都没有标记，且 $x$ 会接收到祖先传下来的标记，所以 $f_{i,0}={f'_{i,0}\over 2},f_{i,1}=f'_{i,1}+{f'_{i,0}\over 2}$ 。
3. 终止节点 $x$ ：$f_{i,1}$ 除了原来的概率，多出这次的 $1\over 2$ ，所以 $f_{i,0}={f'_{i,0}\over 2},f_{i,1}={f'_{i,1}\over 2}+{1\over 2}$ 。
4. 终止节点的子树节点 $x$ ：由于终止节点发生了变化，所以子树内全部需要更新，假设有 $p$ 的概率和原来一样，那么一次更新的变化是这样的 $f_{i,0}=pf'_{i,0}+(1-p)(1-f'_{i,1})$ ，即原来的概率加上新的（终止节点有标记）的概率（也就是自己没有的概率），可以通过打tag实现。

假设插入了 $k​$ 次，那么答案就是 $2^k\sum_{i}f_{i,1}​$ 。

示例程序

#include<cstdio>
#include<cctype>
using namespace std;
typedef long long LL;
const int maxn=100000,MOD=998244353,INV2=MOD+1>>1;

int n,m,pw,P[(maxn<<2)+5][2],tag[(maxn<<2)+5],ans;

#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> inline int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    return lst=='-'?x=-tot:x=tot,Eoln(ch);
}
#define ADD(x,y) (((x)+(y))%MOD)
#define MUL(x,y) ((LL)(x)*(y)%MOD)
inline void Addtag(int p,int k){
    tag[p]=MUL(tag[p],k);
    P[p][0]=ADD(MUL(P[p][0],k),MUL(MOD+1-k,MOD+1-P[p][1]));
}
inline void Pushdown(int p) {if (tag[p]>1) Addtag(p<<1,tag[p]),Addtag(p<<1|1,tag[p]),tag[p]=1;}
void Insert(int L,int R,int l=1,int r=n,int p=1){
    if (R<l||r<L){
        P[p][0]=MUL(P[p][0],INV2);ans=ADD(ans,MOD-P[p][1]);
        P[p][1]=ADD(P[p][1],P[p][0]);ans=ADD(ans,P[p][1]);return;
    }
    if (L<=l&&r<=R){
        P[p][0]=MUL(P[p][0],INV2);ans=ADD(ans,MOD-P[p][1]);P[p][1]=MUL(P[p][1]+1,INV2);
        ans=ADD(ans,P[p][1]);if (l<r) Addtag(p<<1,INV2),Addtag(p<<1|1,INV2);return;
    }int mid=l+(r-l>>1);Pushdown(p);P[p][0]=MUL(P[p][0],INV2);ans=ADD(ans,MOD-P[p][1]);
    P[p][1]=MUL(P[p][1],INV2);ans=ADD(ans,P[p][1]);
    Insert(L,R,l,mid,p<<1);Insert(L,R,mid+1,r,p<<1|1);return;
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    readi(n);for (int i=1;i<=(n<<2);i++) tag[i]=1;readi(m);pw=1;
    for (int i=1;i<=m;i++){
        int tp,L,R;readi(tp);
        if (tp==1) pw=(pw<<1)%MOD,readi(L),readi(R),Insert(L,R);
        else printf("%lld\n",MUL(ans,pw));
    }return 0;
}