正題

---

題目大意

開始時有一張$n$個點沒有邊的圖，$q$次操作加入一條邊，如果加入后圖是一個沙漠（只有邊仙人掌的圖）時才能夠加入。

每次加入后詢問：開始所有點都是白色，$k$次隨機挑一個點染黑，求最后白色點的連通塊數和黑色點的連通塊數的和。

強制在線

$1\le n\le 10^5,1\le q\le 3\times 10^5,1\le k\le 10^9$

---

解題思路

因為強制在線肯定需要用$LCT$維護，至于仙人掌我們維護在環上的邊就好了。

然后考慮怎么求答案。

仙人掌的連通塊數=點數-邊數+環數。

至于本題我們可以考慮這些東西存在的期望數量。

設$w_i$表示指定$i$個點是白點的概率，那么顯然就是$(\frac{n?i}{n}{)}^k$。

然后設$b_i$表示指定$i$個點是黑點的概率，我們考慮容斥指定一些點是白點就是
$$b_i=\sum _{j=0}^i\left(\genfrac{}{}{0ex}{}{i}{j}\right)(?1{)}^j{\left(\frac{n?j}{n}\right)}^k$$

這樣是$O(i)$的，但是其實我們只有求環的出現概率時這個值會很大，但是環的大小和不超過$n$，所以可以在需要的時候暴力求。

時間復雜度：$O(q\log n)$

---

code

#include<cstdio> #include<cstring> #include<algorithm> #include<stack> #define ll long long using namespace std; const ll N=2e5+10,P=998244353; struct LCT{ll fa[N],t[N][2],siz[N];bool w[N],v[N],lazy[N],r[N],p[N],hp[N];stack<ll> s;bool Nroot(ll x){return fa[x]&&(t[fa[x]][0]==x||t[fa[x]][1]==x);}bool Direct(ll x){return t[fa[x]][1]==x;}void PushUp(ll x){siz[x]=siz[t[x][0]]+siz[t[x][1]]+(!p[x]);w[x]=(p[x]&v[x])|w[t[x][0]]|w[t[x][1]];hp[x]=p[x]|hp[t[x][0]]|hp[t[x][1]]; return;}void Rev(ll x){r[x]^=1;swap(t[x][0],t[x][1]);return;}void Rvy(ll x){w[x]=hp[x];lazy[x]=v[x]=1;return;}void PushDown(ll x){if(r[x])Rev(t[x][0]),Rev(t[x][1]),r[x]=0;if(lazy[x]){if(t[x][0])Rvy(t[x][0]);if(t[x][1])Rvy(t[x][1]);lazy[x]=0;}PushUp(x);return;}void Rotate(ll x){ll y=fa[x],z=fa[y];ll xs=Direct(x),ys=Direct(y);ll w=t[x][xs^1];if(Nroot(y))t[z][ys]=x;t[y][xs]=w;t[x][xs^1]=y;if(w)fa[w]=y;fa[x]=z;fa[y]=x;PushUp(y);PushUp(x);return; }void Splay(ll x){ll y=x;s.push(x);while(Nroot(y))y=fa[y],s.push(y);while(!s.empty())PushDown(s.top()),s.pop();while(Nroot(x)){y=fa[x];if(!Nroot(y))Rotate(x);else if(Direct(x)==Direct(y))Rotate(y),Rotate(x);else Rotate(x),Rotate(x);}return;}void Access(ll x){for(ll y=0;x;y=x,x=fa[x])Splay(x),t[x][1]=y,PushUp(x);return;}void MakeRoot(ll x){Access(x);Splay(x);Rev(x);return;}void Link(ll x,ll y){MakeRoot(x);fa[x]=y;Access(x);return;}void Split(ll x,ll y){MakeRoot(x);Access(y);Splay(y);return;} }T; ll n,q,k,op,ans,fa[N],inv[N],fac[N],fnv[N]; ll find(ll x) {return (fa[x]==x)?x:(fa[x]=find(fa[x]));} ll power(ll x,ll b){ll ans=1;while(b){if(b&1)ans=ans*x%P;x=x*x%P;b>>=1;}return ans; } ll C(ll n,ll m) {return fac[n]*fnv[m]%P*fnv[n-m]%P;} ll W(ll x) {return power((n-x)*inv[n]%P,k);} ll B(ll x){ll ans=0;for(ll i=0;i<=x;i++){ll w=power((n-i)*inv[n]%P,k);w=w*C(x,i)%P;(ans+=w*((i&1)?-1:1))%=P;}return (ans+P)%P; } signed main() {freopen("graph.in","r",stdin);freopen("graph.out","w",stdout);inv[1]=fnv[0]=fac[0]=1;for(ll i=2;i<N;i++)inv[i]=P-inv[P%i]*(P/i)%P;for(ll i=1;i<N;i++)fnv[i]=fnv[i-1]*inv[i]%P,fac[i]=fac[i-1]*i%P;scanf("%lld%lld%lld%lld",&n,&q,&k,&op);for(ll i=1;i<=n;i++)fa[i]=i,T.siz[i]=1;ll w2=W(2),b2=B(2),las=0;ans=(W(1)*n+op*B(1)*n)%P;int cnt=n;while(q--){ll x,y;scanf("%lld%lld",&x,&y);x^=las;y^=las;if(find(x)!=find(y)){fa[find(x)]=find(y);++cnt;T.p[cnt]=T.hp[cnt]=1;T.Link(x,cnt);T.Link(y,cnt);(ans-=w2+op*b2)%=P;}else if(x!=y){T.Split(x,y);if(!T.w[y]){T.w[y]=T.v[y]=T.lazy[y]=1;ll S=T.siz[y];(ans+=W(S)-w2)%=P;if(op)(ans+=B(S)-b2)%=P;}}ans=(ans+P)%P;printf("%lld\n",las=ans);}return 0; }

總結

以上是生活随笔為你收集整理的YbtOJ-毒瘤染色【LCT】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。