思路

有加边操作，一眼 LCT。问题在于处理询问操作。

首先，判断联通。如果 \(x,y\) 不在同一个联通块内，则一定没有答案。

其次，求出 \(x,y\) 之间节点的数量 \(num\)（包括 \(x,y\)）。如果 \(num = 3\) 说明 \(x,y\) 之间有一个共同的节点；如果 \(num = 2\) 说明 \(x,y\) 直接连接；如果 \(num > 3\) 说明 \(x,y\) 之间有不止一个节点。

当 \(num = 3\) 时，考虑如何计算该节点的编号。维护节点的编和，查询 \(x,y\) 之间的编号和 \(sum\)，答案显然就是 \(sum - x - y\)。

全都是 LCT 基本操作，难点在于会不会 LCT。

Code

#include <bits/stdc++.h>
#define fst first
#define snd second
#define re register
#define int long long

using namespace std;

typedef pair<int,int> pii;
const int N = 1e5 + 10,mod = 998244353;
int n,q,lst,f[N];

inline int read(){
    int r = 0,w = 1;
    char c = getchar();
    while (c < '0' || c > '9'){
        if (c == '-') w = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9'){
        r = (r << 3) + (r << 1) + (c ^ 48);
        c = getchar();
    }
    return r * w;
}

struct LCT{
    #define fp(u) (tr[u].fa)
    #define son(u,k) (tr[u].ch[k])
    #define getch(u) (u == son(fp(u),1))
    #define isroot(u) (u != son(fp(u),getch(u)))

    struct node{
        int fa,ch[2];
        pii val,sum;
        int tag;
    }tr[N];

    inline void calc(int u){
        if (!u) return;
        tr[u].tag ^= 1;
        swap(son(u,0),son(u,1));
    }

    inline void maintain(int u,int fa,int k,bool falg){
        if (!falg || !isroot(fp(u))) son(fa,k) = u;
        fp(u) = fa;
    }

    inline void pushup(int u){
        tr[u].sum.fst = tr[son(u,0)].sum.fst + tr[son(u,1)].sum.fst + tr[u].val.fst;
        tr[u].sum.snd = tr[son(u,0)].sum.snd + tr[son(u,1)].sum.snd + tr[u].val.snd;
    }

    inline void pushdown(int u){
        if (tr[u].tag){
            calc(son(u,0)); calc(son(u,1));
            tr[u].tag = 0;
        }
    }

    inline void update(int u){
        if (!isroot(u)) update(fp(u));
        pushdown(u);
    }

    inline void rotate(int u){
        int fa = fp(u);
        int ffa = fp(fa);
        int k = getch(u);
        maintain(son(u,k ^ 1),fa,k,false);
        maintain(u,ffa,getch(fa),true);
        maintain(fa,u,k ^ 1,false);
        pushup(fa);
    }

    inline void splay(int u){
        update(u);
        while (!isroot(u)){
            int fa = fp(u);
            if (!isroot(fa)){
                if (getch(u) != getch(fa)) rotate(u);
                else rotate(fa);
            }
            rotate(u);
        }
        pushup(u);
    }

    inline void access(int u){
        int p = 0;
        while (u){
            splay(u);
            son(u,1) = p; pushup(u);
            p = u; u = fp(u);
        }
    }

    inline void makeroot(int u){
        access(u); splay(u);
        calc(u);
    }

    inline int split(int x,int y){
        makeroot(x);
        access(y); splay(y);
        return y;
    }

    inline int find(int u){
        access(u); splay(u);
        pushdown(u);
        while (son(u,0)) pushdown(u = son(u,0));
        splay(u);
        return u;
    }

    inline void link(int x,int y){
        makeroot(x);
        if (find(y) != x) fp(x) = y;
    }

    #undef fp
    #undef son
    #undef getch
    #undef isroot
}T;

inline int find(int x){
    if (f[x] != x) return f[x] = find(f[x]);
    return f[x];
}

inline void merge(int a,int b){
    int x = find(a),y = find(b);
    if (x == y) return;
    f[x] = y;
}

signed main(){
    n = read(),q = read();
    for (re int i = 1;i <= n;i++){
        T.tr[i].val = {i,1};
        f[i] = i;
    }
    while (q--){
        int op,x,y;
        op = (read() * (1 + lst) % mod) % 2 + 1;
        x = (read() * (1 + lst) % mod) % n + 1;
        y = (read() * (1 + lst) % mod) % n + 1;
        if (op == 1){
            T.link(x,y); merge(x,y);
        }
        else{
            if (find(x) != find(y)) printf("%lld\n",lst = 0);
            else{
                pii ans = T.tr[T.split(x,y)].sum;
                if (ans.snd != 3) printf("%lld\n",lst = 0);
                else printf("%lld\n",lst = (ans.fst - x - y));
            }
        }
    }
    return 0;
}