「ZJOI2019」线段树 解题报告

时间：2022-10-30 07:25:38

「ZJOI2019」线段树

听说有人喷这个题简单，然后我就跑去做，然后自闭感++，rp++（雾）

理性分析一波，可以发现最后形成的\(2^k\)个线段树，对应的操作的一个子集，按时间顺序作用到这颗线段树上。

首先考虑研究一下tag的性质，比如两个操作时间先后是否没有影响，操作是否可以以某种形式进行合并，然后啥也没发现。

然后考虑一下一颗树是否可以被压成某个状态，比如实际上只有\(\log\)个状态然后去dp，发现也不行

再次冷静分析一波，发现好像每个节点可以独立考虑，结合上面\(2^n\)，不妨考虑转换成概率，算出每个点被打上tag的概率，在数值上同时也是它的期望，这样我们最后乘上线段树个数就好了。

然后这时候就只对一个线段树操作了，考虑咋去搞

这差不多是我做题时的心路历程，但是我写了好几个做法都过不了大样例，十分自闭，总是以为自己没想清楚哪里假了之类的赶紧改过来，结果大样例输出了十几个不同的答案

心态崩了.jpg

又被什么pkuthusc的报名表填的心烦意乱的，就直接去看题解了

发现自己压根没有对节点分类讨论的意识...

设\(dp_i\)表示\(i\)节点被打上标记的概率

「ZJOI2019」线段树 解题报告

考虑对区间\([4,6]\)进行操作后，节点的改变。

后文中，原来的一半因为不变，所以节点改变指变化的那一半的改变。

  • 红色点

    有标记也全部被push了

    \[dp_i=\frac{dp_i}{2}
    \]

  • 绿色点

    一定被打上标记了

    \[dp_i=\frac{dp_i+1}{2}
    \]

  • 黑色点

    考虑它到跟的红色点是不是有一个点给它放标记了，或者原本是它自己的

    这个没法直接搞，定义一个辅助数组\(f_i\)表示\(i\)到根至少有一个点有标记的概率

    那么有

    \[dp_i=\frac{dp_i+f_i}{2}
    \]

  • 白色点不变

那考虑球一下辅助数组\(f\)

  • 红色点

    直接没了

    \[f_i=\frac{f_i}{2}
    \]

  • 绿色点

    发现绿色点的子树，都有了一个绿色点，即

    \[f_i=\frac{f_i+1}{2}
    \]

    需要实现一个子树加

    我们发现形如\(x\leftarrow\frac{x+1}{2}\)的式子，如果进行\(n\)次，会变成\(\frac{x+2^n-1}{2^n}\)

    于是可以直接打标记记录一下次数

  • 灰色点

    发现有就放到灰色点，没有仍然没有，所以灰色点的子树不变

总复杂度\(O(n\log n)\)

Code:

#include <cstdio>

#include <cctype>

const int SIZE=1<<21;

char ibuf[SIZE],*iS,*iT;

#define gc() (iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,SIZE,stdin),iS==iT?EOF:*iS++):*iS++)

template <class T>

void read(T &x)

{

	x=0;char c=gc();

	while(!isdigit(c)) c=gc();

	while(isdigit(c)) x=x*10+c-'0',c=gc();

}

const int mod=998244353;

const int inv2=499122177;

const int N=1e5+10;

#define mul(a,b) (1ll*(a)*(b)%mod)

inline int add(int a,int b){return a+b>=mod?a+b-mod:a+b;}

#define ls id<<1

#define rs id<<1|1

int fdp[N<<2],dp[N<<2],sum[N<<2],tag[N<<2];

int n,m,in2[N];

void updata(int id)

{

    sum[id]=add(add(sum[ls],sum[rs]),dp[id]);

}

void pushdown(int id)

{

    tag[ls]+=tag[id];

    tag[rs]+=tag[id];

    fdp[ls]=add(mul(fdp[ls],in2[tag[id]]),add(1,mod-in2[tag[id]]));

    fdp[rs]=add(mul(fdp[rs],in2[tag[id]]),add(1,mod-in2[tag[id]]));

    tag[id]=0;

}

void modify(int id,int L,int R,int l,int r)

{

    if(l==L&&r==R)

    {

        sum[id]=add(sum[id],mod-dp[id]);

        dp[id]=mul(dp[id]+1,inv2);

        fdp[id]=mul(fdp[id]+1,inv2);

        sum[id]=add(sum[id],dp[id]);

        ++tag[id];

        return;

    }

    dp[id]=mul(dp[id],inv2);

    fdp[id]=mul(fdp[id],inv2);

    pushdown(id);

    int Mid=L+R>>1;

    if(r<=Mid)

    {

        sum[rs]=add(sum[rs],mod-dp[rs]);

        dp[rs]=mul(add(dp[rs],fdp[rs]),inv2);

        sum[rs]=add(sum[rs],dp[rs]);

        modify(ls,L,Mid,l,r);

    }

    else if(l>Mid)

    {

        sum[ls]=add(sum[ls],mod-dp[ls]);

        dp[ls]=mul(add(dp[ls],fdp[ls]),inv2);

        sum[ls]=add(sum[ls],dp[ls]);

        modify(rs,Mid+1,R,l,r);

    }

    else

        modify(ls,L,Mid,l,Mid),modify(rs,Mid+1,R,Mid+1,r);

    updata(id);

}

int main()

{

	read(n),read(m);

	in2[0]=1;

	for(int i=1;i<=n;i++) in2[i]=mul(in2[i-1],inv2);

	for(int t=1,op,l,r,i=1;i<=m;i++)

	{

		read(op);

		if(op==1)

        {

            read(l),read(r);

            modify(1,1,n,l,r);

            t=add(t,t);

        }

		else printf("%lld\n",mul(sum[1],t));

	}

	return 0;

}

2019.5.10

相关文章