題意：有一個(gè) $[1,n]$ 的線段樹和 $m$ 個(gè)區(qū)間賦值操作，求任取一個(gè)操作的子集并按順序在線段樹上跑后線段樹上有 lazy 標(biāo)記的點(diǎn)的個(gè)數(shù)之和 模 $998244353$。

$n,m\le 10^5$

真·線段樹上 dp

考慮線段樹的情況很復(fù)雜，所以大概率是強(qiáng)行討論。

顯然分結(jié)點(diǎn)考慮，即設(shè) $f(u)$ 為當(dāng)前線段樹上結(jié)點(diǎn) $u$ 有標(biāo)記的概率。

然后對于一次操作，結(jié)點(diǎn)大概分為以下 $4$ 類：

普通結(jié)點(diǎn)：該操作真實(shí)操作到的 $\log$ 個(gè)結(jié)點(diǎn)，這些結(jié)點(diǎn)操作后一定有標(biāo)記。

文藝結(jié)點(diǎn)：普通線段樹修改時(shí)經(jīng)過但未覆蓋的點(diǎn)。這些點(diǎn)即使有標(biāo)記訪問后也會(huì)被下放，所以一定沒有標(biāo)記。

二逼結(jié)點(diǎn)：在父結(jié)點(diǎn)只往兄弟結(jié)點(diǎn)遞歸時(shí)，可以得到父結(jié)點(diǎn)標(biāo)記的結(jié)點(diǎn)。但它是否有標(biāo)記需要討論。

廢物結(jié)點(diǎn)：和修改沒有任何關(guān)系的結(jié)點(diǎn)。

然后開始討論

• 普通結(jié)點(diǎn)

$$f(u)\leftarrow \frac{f(u)+1}{2}$$

• 文藝結(jié)點(diǎn)

$$f(u)\leftarrow \frac{f(u)}{2}$$

• 二逼結(jié)點(diǎn)

$$f(u)\leftarrow \frac{f(u)+\text{\&\#歪比巴卜……}}{2}$$

發(fā)現(xiàn)這個(gè)修改后有標(biāo)記的概率不好搞。

然后考場上瞎傳參亂搞，然后寫崩了……

冷靜分析我們實(shí)際上需要什么東西。

這個(gè)點(diǎn)有標(biāo)記，當(dāng)且僅當(dāng)祖先傳下來了一個(gè)標(biāo)記，或者自己本來就有標(biāo)記。總之就是 $1～u$ 的路徑上至少有一個(gè)標(biāo)記。

這個(gè)怎么搞呢？容斥？

實(shí)際上直接開個(gè) $g(u)$ 記一下就可以了……

重新推一下

• 普通結(jié)點(diǎn)

自己被標(biāo)記了，所以到根路徑上一定也有標(biāo)記。

$$f(u)\leftarrow \frac{f(u)+1}{2}$$

$$g(u)\leftarrow \frac{g(u)+1}{2}$$

• 文藝結(jié)點(diǎn)

自己有標(biāo)記也會(huì)被傳下去。

$$f(u)\leftarrow \frac{f(u)}{2}$$

$$g(u)\leftarrow \frac{g(u)}{2}$$

• 二逼結(jié)點(diǎn)

本身有標(biāo)記當(dāng)且僅當(dāng)?shù)礁窂缴嫌袠?biāo)記。因?yàn)樽嫦鹊臉?biāo)記都被傳下來了，所以路徑有標(biāo)記相當(dāng)于自己有標(biāo)記。

$$f(u)\leftarrow \frac{f(u)+g(u)}{2}$$

$$g(u)\leftarrow \frac{g(u)+g(u)}{2}=g(u)$$

• 廢物結(jié)點(diǎn)

然后你會(huì)發(fā)現(xiàn)還有兩種小類：

底層結(jié)點(diǎn)

普通結(jié)點(diǎn)子樹內(nèi)被減掉的結(jié)點(diǎn)，標(biāo)記不變，但到根路徑一定有標(biāo)記。

$$g(u)\leftarrow \frac{g(u)+1}{2}$$

路人結(jié)點(diǎn)

純路人，沒有任何變化。

然后 普通，文藝，二逼的結(jié)點(diǎn)是 $O(\log n)$ 的，直接暴力。底層結(jié)點(diǎn)可以打 lazy 標(biāo)記，路人結(jié)點(diǎn)不管。

復(fù)雜度 $O(n\log n)$

#include <iostream> #include <cstdio> #include <cstring> #include <cctype> #define MAXN 100005 using namespace std; inline int read() {int ans=0;char c=getchar();while (!isdigit(c)) c=getchar();while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();return ans; } typedef long long ll; const int MOD=998244353,INV=(MOD+1)>>1; int f[MAXN<<3],g[MAXN<<3],s[MAXN<<3]; int add[MAXN<<3],mul[MAXN<<3]; #define lc p<<1 #define rc p<<1|1 inline void update(int p){s[p]=((ll)f[p]+(ll)s[lc]+s[rc])%MOD;} inline void pushlzy(int p,int m,int v){g[p]=((ll)g[p]*m+v)%MOD;mul[p]=(ll)mul[p]*m%MOD,add[p]=((ll)add[p]*m+v)%MOD;} inline void pushdown(int p) {if (add[p]||mul[p]>1){pushlzy(lc,mul[p],add[p]),pushlzy(rc,mul[p],add[p]);add[p]=0,mul[p]=1;} } void modify(int p,int l,int r,int ql,int qr) {if (ql<=l&&r<=qr) return (void)(f[p]=(f[p]+1ll)*INV%MOD,pushlzy(p,INV,INV),update(p));pushdown(p);f[p]=(ll)f[p]*INV%MOD,g[p]=(ll)g[p]*INV%MOD;int mid=(l+r)>>1;if (qr<=mid){f[rc]=((ll)f[rc]+g[rc])*INV%MOD;update(rc);modify(lc,l,mid,ql,qr);return update(p);}if (ql>mid){f[lc]=((ll)f[lc]+g[lc])*INV%MOD;update(lc);modify(rc,mid+1,r,ql,qr); return update(p);}modify(lc,l,mid,ql,qr),modify(rc,mid+1,r,ql,qr);update(p); } int main() {freopen("segment.in","r",stdin);freopen("segment.out","w",stdout);for (int i=0;i<(MAXN<<3);i++) mul[i]=1;int n=read(),cur=1;for (int m=read();m;m--){int t=read();if (t==1){int l,r;l=read(),r=read();modify(1,1,n,l,r);cur=cur*2%MOD;}else printf("%lld\n",(ll)s[1]*cur%MOD);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的【ZJOI2019】线段树【线段树上dp】【大讨论】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。