题解 P5625 [Celeste-A]Good Karma 因果好循环

· · 题解

题目传送门

前置知识：

Link-Cut Tree。

题意简述：

分析：

记 s_i 为 a_{1\dots i} 的异或和，则操作 1 的信息即为 s_{l-1}\operatorname{xor}s_r=val。这意味着确定了 s_{l-1} 和 s_r 的其中一个，另一个就会被确定。将操作 1 抽象为在 s_{l-1} 与 s_r 之间连一条权值为 val 的边，则对于一个连通块，当其中一个 s 确定后，其他也均可确定。

从左到右依次考虑 a_i 的可能取值。考虑 s_i 的值，如果 s_{0\dots i-1} 中至少有一个与 s_i 在同一个连通块内，那么 s_i 就会被确定，a_i 能且仅能取 s_i\operatorname{xor}s_{i-1}。否则由于 s_i 能取任意值，a_i 也能取任意值，有 2^k 种方案。

故对于一个连通块，只有其中标号最小的有可能取最任意值（若标号最小的是 s_0，则只有一种取值，即 0；否则标号最小的有 2^k 种方案），其他数都可以由这个标号最小的确定。故方案数是 2^{k(m-1)}，m 代表连通块数量。

特殊地，当两条操作 1 矛盾时，没有情况满足条件，应输出 0。

这样问题就转化成：加边，删边，询问连通块数以及边权是否矛盾。

先不考虑边权，只考虑连通块数量。此时操作 1 不会产生矛盾。

如果保证图是森林，则显然可以使用 LCT 维护。考虑怎么把一般的连通图转化为树的情况。

注意到如果要删除的边在某一个环上，则该边的两个端点在删除前后均连通，即删除该边对连通性无影响，不如提前删掉该边。即每次加入一条边，对于形成的环，我们直接删掉该环中最早将被删的边。这样，每次加边都不会形成环，转化成了之前的情况。

现在考虑边权。新边的两个端点之间无边时，两点之间无限制关系，不会产生矛盾；有边时，若两点之间边权异或和不同于新边的边权，则产生矛盾，且矛盾会一直持续到该新边被删除或环上最早将被删的边被删除。

复杂度均摊 \mathcal O(q\log n)。

#include <bits/stdc++.h>
#define rep(i, l, r) for(int i=l, _=r; i<=_; ++i)
#pragma GCC diagnostic ignored "-Wparentheses"
using namespace std;
typedef long long ll;
inline ll read() {
    ll res=0; bool k=1; char ch;
    while(!isdigit(ch=getchar())) k=ch^45;
    do res=res*10+(ch&15); while(isdigit(ch=getchar()));
    return k? res: -res;
}
inline void swap_(int &x, int &y) {int t_=x; x=y, y=t_;}
inline void to_max(int &x, int y) {if(x<y) x=y;}
inline int min_(int x, int y) {return x<y? x: y;}
const int mN=2e5+9, mQ=1e6+9, mS=mN+mQ, modn=998244353;
int n, q, k, cnt, ans, p[mN];   //p 为 2^ki 的预处理
int opt[mQ], cut[mQ], tim[mS], a[mQ][2];
//操作类型、删掉的边标号、边被删的时间、边的两端点

namespace LCT {
    #define lc tr[p].son[0]
    #define rc tr[p].son[1]
    #define f tr[p].fa
    struct Node {
        int fa, son[2], mn; //mn 为最早被删边的标号
        ll val, sum;    //边权，边权和
        bool rev;
    } tr[mS];
    inline bool which(int p) {return tr[f].son[1]==p;}
    inline bool is_rt(int p) {return !f || tr[f].son[0]^p && tr[f].son[1]^p;}
    inline void push_up(int p) {
        tr[p].mn=tr[tr[p].son[tim[tr[rc].mn]<tim[tr[lc].mn]]].mn;
        if(tim[p]<tim[tr[p].mn]) tr[p].mn=p;
        tr[p].sum=tr[p].val^tr[lc].sum^tr[rc].sum;
    }
    inline void push_down(int p) {
        if(!tr[p].rev) return;
        swap_(tr[lc].son[0], tr[lc].son[1]), tr[lc].rev^=1;
        swap_(tr[rc].son[0], tr[rc].son[1]), tr[rc].rev^=1;
        tr[p].rev=0;
    }
    inline void rotate(int p) {
        int x=f, fx=tr[x].fa;
        bool wp=which(p), wx=which(x), isrtx=is_rt(x);
        if(tr[p].son[wp^1]) tr[tr[p].son[wp^1]].fa=x;
        tr[x].son[wp]=tr[p].son[wp^1];
        tr[x].fa=p, tr[p].son[wp^1]=x, f=fx;
        if(!isrtx) tr[fx].son[wx]=p;
        push_up(x), push_up(p);
    }
    int sta[mS], top;
    void splay(int p) {
        for(int x=sta[top=1]=p; !is_rt(x); ) sta[++top]=x=tr[x].fa;
        while(top) push_down(sta[top--]);
        for(; !is_rt(p); rotate(p)) if(!is_rt(f)) rotate(which(f)^which(p)? p: f);
    }
    inline void access(int p) {for(int x=0; p; x=p, p=f) splay(p), rc=x, push_up(p);}
    inline void make_rt(int p) {access(p), splay(p), swap_(lc, rc), tr[p].rev^=1;}
    inline int find_rt(int p) {
        for(access(p), splay(p); lc; ) push_down(p=lc);
        return splay(p), p;
    }
    #undef lc
    #undef rc
    #undef f
}
using namespace LCT;
inline void e_cut(int p) {
    make_rt(p);
    access(a[p-n-1][0]), splay(p), tr[a[p-n-1][0]].fa=0, tr[p].son[1]=0;
    access(a[p-n-1][1]), splay(p), tr[a[p-n-1][1]].fa=0;
}

int main() {
    n=read(), q=read(), k=read();
    p[0]=1, p[1]=(1ll<<k)%modn;
    rep(i, 2, ans=n+1) p[i]=(ll) p[i-1]*p[1]%modn;
    rep(i, 0, n+q+1) tim[i]=q+1, tr[i].mn=i;    //初始化
    rep(i, 1, q) {
        if((opt[i]=read())==0) ++cnt, a[cnt][0]=read(), a[cnt][1]=read()+1, tr[n+1+cnt].sum=tr[n+1+cnt].val=read();
        //因为不想让 a[i][0]=0，故两者均 +1：l-1 -> l； r -> r+1
        else if(opt[i]==1) tim[cut[i]=n+1+read()]=i;
    }
    cnt=0;
    int mx=0;
    rep(i, 1, q) if(opt[i]==0) {
        ++cnt;
        int u=a[cnt][0], v=a[cnt][1], t=tim[n+1+cnt];
        make_rt(u);
        int rt_v=find_rt(v);
        if(rt_v^u) {    //u,v 不在同一连通块中
            --ans;
            swap_(tr[rt_v].son[0], tr[rt_v].son[1]), tr[rt_v].rev^=1;   //相当于 make_rt(v)
            tr[rt_v].fa=tr[u].fa=n+1+cnt;   //相当于 link(u, n+1+cnt), link(v, n+1+cnt)
        } else {
            int id=tr[u].mn;
            if(tr[u].sum^tr[n+1+cnt].val) to_max(mx, min_(tim[id], t));
            //如果不相同，则到 min(tim[id], t) 之前均会矛盾
            if(tim[id]<t) { //最先被删除的边是 id
                e_cut(id), cut[tim[id]]=0;  //标记被删过
                make_rt(cnt+n+1);  
                make_rt(u), splay(u), tr[u].fa=cnt+n+1; //link(u, cnt+n+1)
                make_rt(v), splay(v), tr[v].fa=cnt+n+1; //link(v, cnt+n+1
            } else cut[t]=0;    //最先被删的边是 t，直接不加了
        }
    } else if(opt[i]==1) {
        if(cut[i]) ++ans, e_cut(cut[i]);
    } else printf("%d\n", i<=mx? 0: p[ans-1]);
    return 0;
}