P5280 [ZJOI2019]线段树(线段树+dp)

· · 题解

P5280 [ZJOI2019]线段树

我们分类讨论 modify 操作的影响，设询问区间为 [ql,qr]（图来自题解区小粉兔的题解，侵删歉）

  1. 若 [l,r]\cap [ql,qr]=[l,r] 且它的父亲不满足上述性质 （即下图中的浅蓝色部分），那么这个区间在这轮操作中一定会被覆盖到，即操作后它们必然有懒标记 。
  2. 若 [l,r]\cap [ql,qr]\neq \emptyset 且不满足性质①（即下图中的紫色部分），那么这个区间的 lazytag 一定会被下传， 即操作后它们必然无懒标记。
  3. 若 [l,r]\cap [ql,qr]=\emptyset 但它的父亲区间与 [ql,qr] 有交集（即下图中的黄色部分），那么这个区间在这轮操作中只能接受祖先的 lazytag， 操作后它们有无懒标记取决于操作前这个节点到根的链上有无懒标记。
  4. 若 [l,r]\cap [ql,qr]=\emptyset 但它的父亲区间与 [ql,qr] 交集为空（即下图中的橙色部分），那么这轮操作与这个区间无关
  5. 若 [l,r]\cap [ql,qr]=[l,r] 且它的祖先满足上述性质 （即下图中的深蓝色部分），那么这个区间在这轮操作中一定不会被覆盖到。

由于概率具有可乘性，我们将问题转化为求概率，最后再\times 2^{now} 即可，now 为当前修改操作的次数。我们设 f_u 表示结点 u 有懒标记的概率。由于第3类节点是否有 tag 与其祖先有关，我们再设 g_u 表示每个节点 u 到根的路径上有懒标记的概率。 最终答案即为\sum f_u\times 2^{now}。

对于第1类节点，一半保持原样，一半有标记，那么 f_u=\frac {f_u}{2}+\frac {1}{2}，g_u=\frac {g_u}{2}+\frac {1}{2}

对于第2类节点，一半保持原样，一半无标记，那么 f_u=\frac {f_u}{2}，g_u=\frac {g_u}{2}

对于第3类节点， 一半保持原样，另一半的标记取决于 u 到根的路径 f_u=\frac{f_u+g_u}{2}，g_u 不变。

对于第4类节点，标记不受影响，到根路径上的标记也不受影响。我们不用管。

对于第5类节点，标记不受影响，操作后新一半到根路径上一定有标记。f_u 不变，g_u=\frac {g_u}{2}+\frac {1}{2}。

1,2,3类节点都只有 O(\log n ) 个，可以直接修改。

第5类节点个数过多，只能用打懒标记的方法维护。若当前节点到根的路径上有 x 个标记，那么只有 x 次操作都不执行才可能使当前区间 lazytag 为 0，g_u=1-\frac{1-g_u}{2^x}

如果把各种情况都考虑清楚了，代码其实非常好写

#include<bits/stdc++.h>
#define ll long long
#define mid (l+r)/2
using namespace std;
namespace FGF
{
    int n,m;
    int read()
    {
        int s=0;char ch=getchar();
        while(!isdigit(ch))ch=getchar();
        while(isdigit(ch))s=s*10+ch-'0',ch=getchar();
        return s;
    }
    const int mo=998244353;
    const int N=1e5+5;
    const ll inv2=(mo+1)/2; 
    ll inv[N],f[N<<2],g[N<<2],ta[N<<2],ans,now;
    void updat(int ro,int x)
    {
        ans=(ans-f[ro])%mo;
        f[ro]=(f[ro]+x)*inv2%mo;
        g[ro]=(g[ro]+x)*inv2%mo;
        ans=(ans+f[ro])%mo;
    }
    void pushdown(int ro)
    {
        if(ta[ro])
        {
            g[ro<<1]=(1LL-(1LL-g[ro<<1])*inv[ta[ro]]%mo+mo)%mo;
            g[ro<<1|1]=(1LL-(1LL-g[ro<<1|1])*inv[ta[ro]]%mo+mo)%mo;
            ta[ro<<1]+=ta[ro];
            ta[ro<<1|1]+=ta[ro];
            ta[ro]=0;
        }
    }
    void modif(int ro,int l,int r,int L,int R)
    {
        if(r<L||l>R)//处理第3类节点的第一个转移式
        {
            updat(ro,g[ro]);
            return;
        }
        if(L<=l&&r<=R)//处理第1类节点
        {
            updat(ro,1);
            ta[ro]++;//按照题意模拟
            return;
        }
        updat(ro,0);//处理第2类节点
        pushdown(ro);//处理第3类节点的第二个转移式及x
        modif(ro<<1,l,mid,L,R),modif(ro<<1|1,mid+1,r,L,R);
    }
    void work()
    {
        n=read(),m=read();
        now=inv[0]=1;
        for(int i=1;i<=m;i++)
            inv[i]=inv[i-1]*inv2%mo;//预处理2^n的逆元
        int op,l,r;
        while(m--)
        {
            op=read();
            if(op==1)
            {
                l=read(),r=read();
                modif(1,1,n,l,r);
                now=now*2%mo;
            }
            else printf("%lld\n",(ans+mo)*now%mo);
        }
    }
}
int main()
{
    FGF::work();
    return 0;
}