[ZJOI2019]线段树

「爱情、让人受尽委屈。」 2023-10-11 11:16 54阅读 0赞

[题目][Link 1]

神题，神题

首先有一个思想就是计数转概率期望，我们发现每次复制一遍线段树最后会有\\(2^m\\)棵线段树过于自闭，于是我们把这个问题转化成一个概率问题，对于每次修改操作，我们另其只有\\(\\frac\{1\}\{2\}\\)的概率发生，这样我们维护每个点是\\(1\\)的概率，最后乘上总情况数就是答案了

于是我们设\\(dp\_i\\)表示线段树上\\(i\\)节点\\(\\operatorname\{tag=1\}\\)的概率，我们对于线段树上的点分成三类

*  修改操作中实际经过的点

对于这些点，如果这次修改操作发生，那么这个点的\\(\\operatorname\{tag\}\\)肯定被\\(\\operatorname\{pushdown\}\\)掉了，于是肯定是\\(0\\)，所以对于这类点\\(dp\_i=dp\_i/2\\)

*  最后被打\\(\\operatorname\{tag\}\\)的点

如果修改操作发生，那么\\(\\operatorname\{tag\}\\)肯定为\\(1\\)，所以直接\\(dp\_i=(dp\_i+1)/2\\)

*  其父亲被访问到，但是这个节点本身吗没有被访问到

大力思考后会发现这类点没有办法维护，能影响这类点只有\\(\\operatorname\{pushdown\}\\)，而一旦这个点到根的路径上有\\(1\\)，那么这个\\(1\\)就一定会被\\(\\operatorname\{pushdown\}\\)到这个点上来，所以我们需要维护一下每个到根的路径上的情况

于是设\\(t\_i\\)表示节点\\(i\\)到根的路径上\\(\\operatorname\{tag\}\\)全部为\\(0\\)的概率

首先考虑\\(t\_i\\)的修改问题

对于第一类点，显然修改进行的话这个点到根就被清空了，于是\\(t\_i=(t\_i+1)/2\\)

对于第二类点，修改进行这点以及这个点子树里的点到根上就都会至少有这一个点\\(\\operatorname\{tag=1\}\\)，所以这个节点子树内部都会有\\(t\_i=t\_i/2\\)，这个我们直接打上标记就好了

对于第二类点，首先现在有了这个\\(dp\_i\\)随便搞搞就能维护出来了，考虑一下对于这种点我们只是利用\\(\\operatorname\{pushdown\}\\)把这个点到根的路径上点的\\(\\operatorname\{tag\}\\)推到了这个点上，所以对于这个点及其子树内部的\\(t\_i\\)没有影响

所以直接写个线段树模拟一下就好了

代码

#include<bits/stdc++.h>
    #define re register
    #define LL long long
    inline int read() {
        char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();
        while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
    }
    const int mod=998244353;
    const int Inv=mod+1>>1;
    const int maxn=1e5+5;
    int l[maxn<<2],r[maxn<<2],dp[maxn<<2],t[maxn<<2];
    int tag[maxn<<2],n,m,pw=1,ans;
    void build(int x,int y,int i) {
        l[i]=x,r[i]=y;t[i]=tag[i]=1;
        if(x==y) return;
        int mid=x+y>>1;
        build(x,mid,i<<1),build(mid+1,y,i<<1|1);
    }
    inline void pushdown(int i) {
        if(tag[i]==1) return;
        tag[i<<1]=1ll*tag[i<<1]*tag[i]%mod;
        tag[i<<1|1]=1ll*tag[i<<1|1]*tag[i]%mod;
        t[i<<1]=1ll*t[i<<1]*tag[i]%mod;
        t[i<<1|1]=1ll*t[i<<1|1]*tag[i]%mod;
        tag[i]=1;
    }
    void change(int x,int y,int i) {
        if(x<=l[i]&&y>=r[i]) {
            ans=(ans-dp[i]+mod)%mod;
            dp[i]=1ll*(dp[i]+1)*Inv%mod;
            t[i]=1ll*t[i]*Inv%mod;
            tag[i]=1ll*tag[i]*Inv%mod;
            ans=(ans+dp[i])%mod;
            return;
        }
        if(r[i]<x||l[i]>y) {
            ans=(ans-dp[i]+mod)%mod;
            int v=(mod+1-dp[i])%mod;
            dp[i]=1ll*(v+t[i]%mod)%mod*Inv%mod;
            dp[i]=(mod+1-dp[i])%mod;
            ans=(ans+dp[i])%mod;
            return;
        }
        pushdown(i);
        change(x,y,i<<1),change(x,y,i<<1|1);
        t[i]=1ll*(t[i]+1)*Inv%mod;
        ans=(ans-dp[i]+mod)%mod;
        dp[i]=1ll*dp[i]*Inv%mod;
        ans=(ans+dp[i])%mod;
    }
    int main() {
        n=read(),m=read();build(1,n,1);
        int op,x,y;
        while(m--) {
            op=read();
            if(op==2) printf("%d\n",1ll*pw*ans%mod);
            else {
                x=read(),y=read();pw=(pw+pw)%mod;
                change(x,y,1);
            }
        }
        return 0;
    }

转载于:https://www.cnblogs.com/asuldb/p/11354655.html

[Link 1]: https://www.luogu.org/problem/P5280