题解 P5280 【[ZJOI2019]线段树】

~~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的时限意义何在…… ```C // 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;//拜拜程序~ } ```