题解 P5280 【[ZJOI2019]线段树】

我考场上就打了 $20pts$ 暴力，后来听人口胡会了 $O(n\log n)$ 的做法。昨晚调了一个晚上没调出来，结果后来改变一下 $dp$ 的思路就 $A$ 了。。。 不得不说，这是一道很好的题目。$orz\ \text{jls}$ ### 前置知识：线段树 其实不会线段树应该也不会去 $ZJOI$。。。 ### 1、挖掘线段树修改操作的重要性质 设询问的区间为 $[ql,qr]$ ① 若 $[l,r]\cap [ql,qr]=[l,r]$ 且它的祖先**不满足**上述性质 ，那么这个区间在这轮操作中**一定会被覆盖到**，我们定义 $[l,r]$ 为**可打标记全覆盖区间**。 ② 若 $[l,r]\cap [ql,qr]=[l,r]$ 且它的祖先**满足**上述性质，那么这个区间在这轮操作中**一定不会被覆盖到**，我们定义 $[l,r]$ 为**不可打标记全覆盖区间**。 ③ 若 $[l,r]\cap [ql,qr]\neq \emptyset$ 且**不满足**性质①②，那么这个区间的 $lazytag$ **一定会被下传**，我们定义 $[l,r]$ 为**半覆盖区间**。 ④ 若 $[l,r]\cap [ql,qr]=\emptyset$ ，那么这个区间在这轮操作中**只能接受祖先的 $lazytag$**，我们定义 $[l,r]$ 为**未覆盖区间**。 概率具有**可乘性**，我们将其转化为概率，然后乘以 $2^{now}$，$now$ 为当前修改操作的次数。 ### 2、考虑维护什么哪些值 首先，我们要维护每个区间 $lazytag$ 为 $1$ 的概率 $f$ 其实对于满足性质①②③的区间都是好 $dp$ 的，就是满足性质④的区间有些麻烦。 我们发现对于满足性质④的区间只要当前区间到根**至少有一个**区间 $lazytag$ 为 $1$ 并且在操作的时候**祖先被遍历到**即可。 考虑再维护每个区间到根上**至少有一个**区间 $lazytag$ 为 $1$ 的概率 $g$ 一次 $add$： ```cpp inline void add(int rt,int x) { ans=(ans-f[rt])%mod; f[rt]=1ll*(f[rt]+x)*inv2%mod; g[rt]=1ll*(g[rt]+x)*inv2%mod; ans=(ans+f[rt])%mod; } ``` 对于可打标记全覆盖区间/半覆盖区间，直接 $add(1/0)$ 就可以了。 对于未覆盖区间，我们考虑在每次操作的可打标记覆盖区间打一个标记。若当前区间到根有 $x$ 个可打标记覆盖区间，那么只有 $x$ 次操作**都不执行**才可能使当前区间 $lazytag$ 为 $0$ 一次 $pushdown$： ```cpp inline void pushdown(int rt) { if(tag[rt]) { g[lson]=(1ll-1ll*(1ll-g[lson])*pw[tag[rt]]%mod)%mod; g[rson]=(1ll-1ll*(1ll-g[rson])*pw[tag[rt]]%mod)%mod; tag[lson]+=tag[rt];tag[rson]+=tag[rt];tag[rt]=0; } } ``` 这个思路可能是目前我理解的最简单的思路了。 时间复杂度 $O(n\log n)$ ```cpp #include <bits/stdc++.h> #define lson (rt<<1) #define rson (rt<<1|1) using namespace std; const int maxn=100000+10; const int mod=998244353; const int inv2=(mod+1)>>1; int n,m,now,ans,pw[maxn],f[maxn<<2],g[maxn<<2],tag[maxn<<2]; inline int read() { register int x=0,f=1;char ch=getchar(); while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();} while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} return (f==1)?x:-x; } inline void add(int rt,int x) { ans=(ans-f[rt])%mod; f[rt]=1ll*(f[rt]+x)*inv2%mod; g[rt]=1ll*(g[rt]+x)*inv2%mod; ans=(ans+f[rt])%mod; } inline void pushdown(int rt) { if(tag[rt]) { g[lson]=(1ll-1ll*(1ll-g[lson])*pw[tag[rt]]%mod)%mod; g[rson]=(1ll-1ll*(1ll-g[rson])*pw[tag[rt]]%mod)%mod; tag[lson]+=tag[rt];tag[rson]+=tag[rt];tag[rt]=0; } } void update(int L,int R,int l,int r,int rt) { if(r < L || R < l){add(rt,g[rt]);return;} if(L <= l && r <= R){add(rt,1);tag[rt]++;return;} pushdown(rt);add(rt,0); int mid=(l+r)>>1; update(L,R,l,mid,lson);update(L,R,mid+1,r,rson); } int main() { n=read(),m=read(); now=pw[0]=1; for(int i=1;i<=m;i++) pw[i]=1ll*pw[i-1]*inv2%mod; int op,l,r; while(m--) { op=read(); if(op==1) l=read(),r=read(),update(l,r,1,n,1),now=2ll*now%mod; else printf("%d\n",1ll*(ans+mod)*now%mod); } return 0; } ```