shadowice1984 的博客

shadowice1984 的博客

题解 P5280 【[ZJOI2019]线段树】

posted on 2019-04-02 17:14:28 | under 题解 |

4年zjoi3年线段树

zjoi的开题顺序永远是231

zjoi只有数据结构题能做

说实话这题真的该蓝,因为它 实 在 是 太 简 单 了

前置芝士:线段树

你只需要提高组的基础线段树芝士就可以通过此题


本题题解

一个小转化

首先你会发现那个复制线段树操作其实是假的

通过归纳法我们就可以证明,假设经过了$m$次操作1,那么你手中的$2^m$棵线段树刚好对应了操作集合的$2^m$个子集

因此我们的操作2实际上在询问对于每一个操作集合的子集,线段树上为1的tag个数之和

dp!

根据计数题的一般套路,我们应该考虑每一个节点对答案的贡献,

所以我们不妨设$dp(i)$表示节点的tag值为1的方案数

但是这样设我们会很快的发现一个问题是,我们每执行一次操作,线段树上所有节点的dp值都会变动,尽管你会发现只有$O(logn)$个节点的tag可能会发生变动,其他节点的tag应该和上一次操作一模一样,但是这些节点的dp值都要乘2……

这样设计dp实在是太蠢了,所以不如让我们想点trick,减少dp值变动的点的个数

方案数转概率

我们重新定义一下dp数组的定义$dp(i)$表示,如果我们等概率的从$2^m$个操作集合当中选择一个操作集合并执行,那么$i$的tag是1的概率

这样搞有什么好处呢?

如果这个节点在这一次修改当中没有被改到,那么这个点是1的概率将保持不动,那么一次修改下来只有$O(logn)$个节点的$dp$值会发生变动,我们就可以暴力更改这些点的dp值了

此时我们把各个点是1的概率加起来就得到了线段树中是1的tag的期望个数了

啊可是答案要算的是1的个数之和不是期望啊?

平常我们算期望的时候是计算所有方案下的和然后除总的方案数,这里我们反过来,算出期望然后乘总的方案数,这样我们就能算出来1的个数之和啦~

有了船新的dp定义之后自然要推转移啦~

为了规避繁杂的细节和分类讨论,我们需要重新看待一次修改的过程

正常状态下,我们会把线段树的修改操作看成按照一定顺序连续执行的pushdown,这样会很好写也很好实现

但是这样你会发现你的转移不好推了,怎么办呢?

考虑这样一个问题:如果知道了操作之前的线段树长什么,那么我们能不能直接推出操作之后的线段树呢?

答案是可行的~,我们把线段树的节点分为3类(似乎这样设计的状态会比分5种情况讨论的做法细节少一点?)

当修改区间$[3,5]$的时候,dp值会发生变化的的点在图中被染成了红色,灰色,和黑色

接下来我们分情况讨论一下红点和灰点和黑点的转移情况

红点

容易看出,只要执行了这一次操作那么红点的tag必然是0,所以这里的转移只需要把红点的dp值除2就行了

$$dp(u)=dp(u)/2$$

黑点

容易看出,只要执行了这一次操作那么黑点的tag必然是1,所以这里我们把黑点的dp值加1然后除2就行了

$$dp(u)=(dp(u)+1)/2$$

灰点

容易看出,我们什么性质也看不出来

因为即使执行了这次操作,灰点的tag也可能是0

因此灰点莫得转移,这个状态定义翻!车!了!

新的状态定义

因为灰点没法转移,所以我们要定义一些新的状态,让我们可以转移

考虑一个灰点的tag什么时候会变成1,我们发现只要这个灰点到线段树的根的路径上有tag为1的节点,那么这个灰点的tag在操作之后就是1

因此我们新增一个$fdp(i)$状态表示这个点到根的路径上有1的概率

$fdp(i)$的引入会带来一些问题,就是一次修改之后$fdp$值发生变化的节点数目不再是$O(logn)$的了,这个问题我们过一会再说,先让我们重新推一推转移

红点

容易看出,执行了这次操作后,红点到根的路径全部是红点,所以红点到根的路径不会有1,因此直接把fdp值除2就行了

$$fdp(u)=fdp(u)/2$$

灰点

容易看出,执行了这次操作之后,如果灰点到根的路径上有1,那么灰点的tag就是1,否则不是1,所以把灰点的dp值加上fdp值除2就行了

另一个性质是对于在灰点子树当中的节点,修改之前如果到根的路径上有1,那么这个1最多是被push到灰点上而已,因此这一次修改并不会改变这个节点到根的路径上是否有1这个命题的真假,所以灰点子树当中的节点fdp值并不会动

$$dp(u)=(dp(u)+fdp(u))/2$$

黑点

容易看出,执行这次操作之后,对于黑点子树当中的所有点,他们到根的路径上肯定有1了,那么我们把fdp值加上1然后除2就行了

$$fdp(u)=(fdp(u)+1)/2$$

打标记

上面的转移方程涉及到对黑点子树当中的所有点做$x=(x+1)/2$这样的操作,显然我们不能暴力做,所以我们维护一个懒标记表示这个点被执行了几次这样的操作

容易看出,如果一个节点原来的值是$val$,被连续执行了$n$次操作,那么这个点的真实值将会是

$$(val+2^n-1)/2^n$$

然后我们就可以打标记维护fdp值了,每次修改的时候用bfs找出所有的红点黑点灰点按照转移方程转移即可~

总复杂度$O(mlogn)$,不是很清楚3000ms的时限意义何在……

// luogu-judger-enable-o2
#include<cstdio>
#include<algorithm>
using namespace std;const int N=1e5+10;typedef unsigned long long ll;const ll mod=998244353;
const ll iv2=(mod+1)/2;ll imi[N];ll dmi[N];ll mi[N];int n;int m;
# define md(x) (x=(x>=mod)?x-mod:x)
struct linetree
{
    ll sum;ll dp[N<<2];ll fdp[N<<2];int l[N<<2];int r[N<<2];int add[N<<2];
    int qu1[N];int hd1;int qu2[N];int hd2;int qu3[N];int hd3;
    int qu[N];int hd;int tl;
    inline void chan(int p,int tmp)
    {sum+=mod-dp[p];md(sum);dp[p]=(dp[p]+tmp)*iv2%mod;sum+=dp[p];md(sum);}
    inline void pd(int p)//下传标记 
    {
        if(add[p]!=0)
        {
            fdp[p<<1]=(fdp[p<<1]+dmi[add[p]])*imi[add[p]]%mod;
            fdp[p<<1|1]=(fdp[p<<1|1]+dmi[add[p]])*imi[add[p]]%mod;
            add[p<<1]+=add[p];add[p<<1|1]+=add[p];add[p]=0;
        }
    }inline void extract(int dl,int dr)//bfs
    {
        hd=1;tl=0;qu[++tl]=1;hd1=hd2=hd3=0;
        while(hd<=tl)
        {
            int nw=qu[hd++];
            if(dl<=l[nw]&&r[nw]<=dr){qu2[++hd2]=nw;continue;}
            if(r[nw]<dl||l[nw]>dr){qu3[++hd3]=nw;continue;}
            qu1[++hd1]=nw;pd(nw);qu[++tl]=nw<<1;qu[++tl]=nw<<1|1;
        }
    }inline void modify(int dl,int dr)//按照转移方程转移同时打标记 
    {
        extract(dl,dr);for(int i=1;i<=hd1;i++)chan(qu1[i],0);
        for(int i=1;i<=hd2;i++)chan(qu2[i],1);
        for(int i=1;i<=hd2;i++)add[qu2[i]]++,fdp[qu2[i]]=(fdp[qu2[i]]+1)*iv2%mod;
        for(int i=1;i<=hd3;i++)chan(qu3[i],fdp[qu3[i]]);
        for(int i=1;i<=hd1;i++)fdp[qu1[i]]=fdp[qu1[i]]*iv2%mod;

    }inline void build(int p,int pl,int pr)//建树 
    {
        if(pl>pr)return;l[p]=pl;r[p]=pr;if(pl==pr)return;
        int mid=(pl+pr)>>1;build(p<<1,pl,mid);build(p<<1|1,mid+1,pr);
    }
}lt;
int main()
{
    imi[0]=1;for(int i=1;i<N;i++)imi[i]=imi[i-1]*iv2%mod;
    mi[0]=1;for(int i=1;i<N;i++)mi[i]=mi[i-1]*2%mod;
    dmi[0]=0;for(int i=1;i<N;i++)dmi[i]=(mi[i]+mod-1)%mod;
    scanf("%d%d",&n,&m);lt.build(1,1,n);int tot=0;
    for(int i=1,tp,l,r;i<=m;i++)
    {
        scanf("%d",&tp);
        if(tp==1)scanf("%d%d",&l,&r),lt.modify(l,r),tot++;
        else printf("%lld\n",lt.sum*mi[tot]%mod);
    }return 0;//拜拜程序~ 
}