CSP田地丈量问题c语言

这题依然是看的其他人的题解，主要是参考的CSDN上另一位博主的代码，传送门
用到的知识是树链剖分线段树。
因为没有用LCT（动态树），所以只能拿50分。（异或操作强制在线，树链剖分要知道树的形态）。LCT目前我还没学，我上面发的那个博主写了，b站也有一个题解。大家可以自行搜索。

#include <bits/stdc++.h>

#define mid ((l+r)>>1)
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r

using namespace std;

typedef long long ll;

const int maxm = 300000 + 10;

struct req {
    ll type, x2, s, l, r, y2;

    req(ll type, ll x2, ll s, ll l, ll r, ll y2)
            : type(type), x2(x2), s(s), l(l), r(r), y2(y2) {}
};

vector<req> R;
ll m, p, T;
//ll e = 0, beg[maxm], nex[maxm], to[maxm];
ll dep[maxm], siz[maxm], fa[maxm], son[maxm];
ll id[maxm], top[maxm], cnt = 0;
ll sum[maxm << 2], lazy[maxm << 2];
ll now, res, tot = 0,rt;
ll A = 0;
vector<ll> edge[maxm];
vector<pair<ll, ll> > E[maxm];

//inline void add(ll x, ll y) {
//    to[++e] = y;
//    nex[e] = beg[x];
//    beg[x] = e;
//}

inline void dfs1(ll x) {//x当前节点，f父亲，deep深度
    siz[x] = 1;
    ll maxson = 0;

    for (ll y:edge[x]) {
//        ll y = to[i];
        if (y == fa[x])
            continue;
        dfs1(y);
        siz[x] += siz[y];
        if (siz[y] > maxson) {
            son[x] = y;
            maxson = siz[y];
        }
    }
}

inline void dfs2(ll x, ll topf) {//x当前节点，topf当前链的最顶端的节点
    id[x] = ++cnt;
    top[x] = topf;
    if (!son[x])
        return;
    dfs2(son[x], topf);
    for (ll y:edge[x]) {
//        ll y = to[i];
        if (y == fa[x] || y == son[x])
            continue;
        dfs2(y, y);
    }
}

inline void pushdown(ll rt) {
    if (lazy[rt] != 1) {
        lazy[rt << 1] = (lazy[rt] * lazy[rt << 1]) % p;
        lazy[rt << 1 | 1] = (lazy[rt] * lazy[rt << 1 | 1]) % p;

        sum[rt << 1] = (lazy[rt] * sum[rt << 1]) % p;
        sum[rt << 1 | 1] = (lazy[rt] * sum[rt << 1 | 1]) % p;
        lazy[rt] = 1;
    }
}

inline void insert(ll rt, ll l, ll r, ll v, ll y) {
    if (l == r) {
        sum[rt] = y;
        sum[rt] %= p;
        lazy[rt] = 1;
        return;
    } else {
        if (lazy[rt] != 1)
            pushdown(rt);
        if (v <= mid)
            insert(lson, v, y);
        if (v > mid)
            insert(rson, v, y);
        sum[rt] = (sum[rt << 1] + sum[rt << 1 | 1]) % p;
    }
}

inline void query(ll rt, ll l, ll r, ll L, ll R) {
    if (L <= l && r <= R) {
        res += sum[rt];
        res %= p;
        return;
    } else {
        if (lazy[rt] != 1)
            pushdown(rt);
        if (L <= mid)
            query(lson, L, R);
        if (R > mid)
            query(rson, L, R);
    }
}

inline void update(ll rt, ll l, ll r, ll L, ll R, ll k) {
    if (L <= l && r <= R) {
        lazy[rt] = (lazy[rt] * k) % p;
        sum[rt] = (sum[rt] * k) % p;
    } else {
        if (lazy[rt] != 1)pushdown(rt);
        if (L <= mid)update(lson, L, R, k);
        if (R > mid)update(rson, L, R, k);
        sum[rt] = (sum[rt << 1] + sum[rt << 1 | 1]) % p;
    }
}

inline ll qRange(ll x, ll y) {
    ll ans = 0;
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]])swap(x, y);
        res = 0;
        query(1, 1, tot, id[top[x]], id[x]);
        ans += res;
        ans %= p;
        x = fa[top[x]];
    }

    if (dep[x] > dep[y])swap(x, y);
    res = 0;
    query(1, 1, tot, id[x], id[y]);
    ans += res;
    return ans % p;
}

inline void updRange(ll x, ll y, ll k) {
    k %= p;
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        update(1, 1, tot, id[top[x]], id[x], k);
        x = fa[top[x]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    update(1, 1, tot, id[x], id[y], k);
}

inline ll find(ll x, ll y) {
    ll l = 0, r = E[x].size() - 1, ans = 0;
    while (l <= r) {
        ll mi = (l + r) >> 1;
        if (E[x][mi].first <= y) {
            ans = E[x][mi].second;
            l = mi + 1;
        } else
            r = mi - 1;
    }
    return ans;
}


int main() {
    ll type;
    scanf("%lld%lld%lld", &m, &p, &T);
    rt = now = 0;
    tot = 0;
    for (int i = 1; i <= m << 2; i++) {
        lazy[i] = 1;
        sum[i] = 0;
    }
    dep[0] = 0;
    for (ll t = 1, x2, y2, s, l, r; t <= m; t++) {
        scanf("%lld", &type);
        x2 = y2 = s = l = r = 0;
        if (type == 1) {
            scanf("%lld", &x2);
            if (x2 == 0) {
                now = fa[now];
            } else {
                s = ++tot;
                fa[tot] = now;
                dep[tot] = dep[now] + 1;
                edge[now].push_back(tot);
//                add(now, tot);
//                add(tot, now);
                E[dep[tot]].push_back({t, tot});
                now = tot;
            }
        } else if (type == 2) {
            scanf("%lld%lld%lld%lld", &s, &l, &r, &y2);
        } else if (type == 3) {
            scanf("%lld%lld%lld", &s, &l, &r);
        }
        R.push_back(req(type, x2, s, l, r, y2));
    }
    A = 0;
    tot++;
    dfs1(rt);
    dfs2(rt, rt);
    for (req re: R) {
        if (re.type == 1) {
            if (re.x2) {
                insert(1, 1, tot, id[re.s], re.x2 ^ A);
            }
        } else {
            ll x = find(re.l, re.s);
            ll y = find(re.r, re.s);
            if (re.type == 2) {
                updRange(x, y, re.y2 ^ A);
            } else {
                res = qRange(x, y);
                printf("%lld\n", res);
                if (T)
                    A = res;
            }
        }
    }
    return 0;
}