头像

Donyeoh




在线 


最近来访(36)
用户头像
fw一个
用户头像
cxposition
用户头像
017-CS
用户头像
xhxhxxh_
用户头像
peterHUAN
用户头像
Repeater
用户头像
goMgo
用户头像
笑脸人
用户头像
Fatin
用户头像
lsfzy
用户头像
直言不
用户头像
WY0
用户头像
封禁用户的朋友
用户头像
hemmm_
用户头像
xtk
用户头像
Andy2022
用户头像
beau_emilien
用户头像
acwing_1446
用户头像
firfis
用户头像
XingHe

活动打卡代码 AcWing 248. 窗内的星星

Donyeoh
38分钟前

扫描线 + 线段树 + 延迟标记
1. 一个框要圈住某颗星星就有一定的范围,将这个范围交起来,就是能圈住这些星星的框的范围。
2. 将这些框都设一个值为这颗星星的亮度 c,若某个范围有重叠,那么这个范围的亮度 c 就可以叠加。只需要对这所有框从头扫描一遍,找出重叠值最大的即可,用扫描线处理。
3. 用线段树 + 延迟标便可以快速找出最大的。

#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
const int N = 1e4 + 10;
struct xin {
    int x, y1, y2, c;
    bool operator < (const xin &a) {
        return x < a.x || (x == a.x && c > a.c);
    }
} a[N * 2];
struct node {
    int l, r;
    int dat, add;
} t[N * 8];
int n, w, h;
int b[N * 2], c[N * 2];

void build(int p, int l, int r) {
    t[p].l = l, t[p].r = r, t[p].dat = 0, t[p].add = 0;
    if(l == r) return;
    int mid = l + r >> 1;
    build(p * 2, l, mid);
    build(p * 2 + 1, mid + 1, r);
}

void spread(int p) {
    if(t[p].add) {
        t[p * 2].dat += t[p].add;
        t[p * 2 + 1].dat += t[p].add;
        t[p * 2].add += t[p].add;
        t[p * 2 + 1].add += t[p].add;
        t[p].add = 0;
    }
}

void change(int p, int l, int r, int d) {
    if(l <= t[p].l && r >= t[p].r) {
        t[p].dat += d;
        t[p].add += d;
        return;
    }
    spread(p);
    int mid = t[p].l + t[p].r >> 1;
    if(l <= mid) change(p * 2, l, r, d);
    if(r > mid) change(p * 2 + 1, l, r, d);
    t[p].dat = max(t[p * 2].dat, t[p * 2 + 1].dat);
}

int ask(int p, int l, int r) {
    if(l <= t[p].l && r >= t[p].r) return t[p].dat;
    spread(p);
    int mid = t[p].l + t[p].r >> 1, val = 0;
    if(l <= mid) val += ask(p * 2, l, r);
    if(r > mid) val += ask(p * 2 + 1, l, r);
    return val;
}

signed main() {
    while(cin >> n >> w >> h) {
        for(int i = 1; i <= n; i++) {
            int x, y, c;
            cin >> x >> y >> c;
            a[i * 2 - 1] = {x, y, y + h - 1, c};
            a[i * 2] = {x + w - 1, y, y + h - 1, -c};
            b[i * 2 - 1] = y;
            b[i * 2] = y + h - 1;
        }
        sort(b + 1, b + n * 2 + 1);
        int k = unique(b + 1, b + n * 2 + 1) - b - 1;
        sort(a + 1, a + n * 2 + 1);
        int ans = 0;
        build(1, 1, k);
        for(int i = 1; i <= n * 2; i++) {
            int y1 = lower_bound(b + 1, b + k + 1, a[i].y1) - b;
            int y2 = lower_bound(b + 1, b + k + 1, a[i].y2) - b;
            change(1, y1, y2, a[i].c);
            ans = max(ans, ask(1, 1, k));
        }
        cout << ans << endl;
    }
    return 0;
}


活动打卡代码 AcWing 247. 亚特兰蒂斯

Donyeoh
1小时前

扫描线 + 线段树
1. 我们只关覆盖的长度,并且修改也是成对出现的。因此可以对线段树每个节点维护该节点区间被覆盖的长度 len,以及该节点被覆盖的次数。
2. 如果该节点 cnt > 0 就则说明该节点代表的区间全被覆盖了,无需到子节点去找;否则就等于两个子节点的和。

#include <iostream>
#include <algorithm>
#include <cstdio>
#define PII pair<pair<double, double>, pair<double, int> >
using namespace std;
const int N = 1e4 + 10;
struct node {
    int l, r, cnt;
    double len;
} t[N * 8];
int n;
PII a[N * 2];
double b[N * 2];
int c[N * 2];

void build(int p, int l, int r) {
    t[p].l = l, t[p].r = r, t[p].cnt = 0, t[p].len = 0;
    if(l == r) return;
    int mid = l + r >> 1;
    build(p * 2, l, mid);
    build(p * 2 + 1, mid + 1, r);
}

void change(int p, int l, int r, int w) {
    if(l <= t[p].l && r >= t[p].r) {
        t[p].cnt += w;
        if(t[p].cnt) t[p].len = b[t[p].r + 1] - b[t[p].l];
        else t[p].len = (t[p].r == t[p].l) ? 0 : t[p * 2].len + t[p * 2 + 1].len;
        return;
    }
    int mid = t[p].l + t[p].r >> 1;
    if(l <= mid) change(p * 2, l, r, w);
    if(r > mid) change(p * 2 + 1, l, r, w);
    t[p].len = t[p].cnt ? b[t[p].r + 1] - b[t[p].l] : t[p * 2].len + t[p * 2 + 1].len;
}

int main() {
    int T = 0;
    while(cin >> n && n) {
        printf("Test case #%d\n", ++T);
        for(int i = 1; i <= n; i++) {
            double x1, y1, x2, y2;
            cin >> x1 >> y1 >> x2 >> y2;
            a[i * 2 - 1] = {{x1, y1}, {y2, 1}};
            a[i * 2] = {{x2, y1}, {y2, -1}};
            b[i * 2 - 1] = y1;
            b[i * 2] = y2;
        }
        sort(b + 1, b + n * 2 + 1);
        int k = unique(b + 1, b + n * 2 + 1) - b - 1;
        sort(a + 1, a + n * 2 + 1);
        double ans = 0;
        build(1, 1, k);
        for(int i = 1; i <= n * 2; i++) {
            int l = lower_bound(b + 1, b + k + 1, a[i].first.second) - b;
            int r = lower_bound(b + 1, b + k + 1, a[i].second.first) - b;
            change(1, l, r - 1, a[i].second.second);
            ans += (a[i + 1].first.first - a[i].first.first) * (t[1].len);
        }
        printf("Total explored area: %.2f\n", ans);
        puts("");
    }
    return 0;
}



Donyeoh
5小时前



Donyeoh
5小时前

线段树 + 区间最大公约数 + 更相减损术
1. gcd(x, y) = gcd(x, y - x), 可以扩展到三个数:gcd(x, y, z) = gcd(x, y - x, z - y), 可用数学归纳法证明。
2. 求原序列的最大公约数等价于在它的等差数列上求最大公约数。
3. 对于 l, r 答案即:gcd(a[l], ask(1, l + 1, r)).
4. 另用树状数组来维护 a[i] 的值。
5. 由于线段树保存的是 1 ~ n,对于在等差数列上的修改,若 r = n 时跳过 change(1, r + 1, v) 的操作,因为该操作不合法。
6. 等差序列可能为负数,因此 ask 时返回加上绝对值。

#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
const int N = 5e5 + 10;
struct node {
    int l, r;
    int dat;
} t[N *  4];
int n, m;
int a[N], b[N], c[N];

int ask(int x) {
    int ans = 0;
    for(; x; x -= x & -x) ans += c[x];
    return ans;
}

void add(int x, int y) {
    for(; x <= n; x += x & -x) c[x] += y;
}

void build(int p, int l, int r) {
    t[p].l = l, t[p].r = r;
    if(l == r) {
        t[p].dat = b[l];
        return;
    }
    int mid = (l + r) / 2;
    build(p * 2, l, mid);
    build(p * 2 + 1, mid + 1, r);
    t[p].dat = __gcd(t[p * 2].dat, t[p * 2 + 1].dat);
}

void change(int p, int x, int v) {
    if(t[p].l == t[p].r) {
        t[p].dat += v;
        return;
    }
    int mid = (t[p].l + t[p].r) / 2;
    if(x <= mid) change(p * 2, x, v);
    else change(p * 2 + 1, x, v);
    t[p].dat = __gcd(t[p * 2].dat, t[p * 2 + 1].dat);
}

int ask(int p, int l, int r) {
    if(l <= t[p].l && r >= t[p].r) return abs(t[p].dat);
    int mid = (t[p].l + t[p].r) / 2;
    int ans = 0;
    if(l <= mid) ans = __gcd(ans, ask(p * 2, l, r));
    if(r > mid) ans = __gcd(ans, ask(p * 2 + 1, l, r));
    return ans;
}

signed main() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i], b[i] = a[i] - a[i - 1];
    build(1, 1, n);
    while(m--) {
        char ch;
        cin >> ch;
        if(ch == 'C') {
            int l, r, d;
            cin >> l >> r >> d;
            change(1, l, d);
            if(r < n) change(1, r + 1, -d);
            add(l, d);
            add(r + 1, -d);
        } else {
            int l, r;
            cin >> l >> r;
            cout << __gcd(a[l] + ask(l), ask(1, l + 1, r)) << endl;
        }
    }
    return 0;
}



Donyeoh
6小时前

线段树 + 最大连续子序列和
1. 维护区间和 sum,区间最大连续子段和 dat,紧靠左端的最大连续子段和 lmax,紧靠右端的最大连续子段和 rmax。
2. 在 build 和 change 中从下往上更新信息时:
t[p].sum = t[p * 2].sum + t[p * 2 + 1].sum;
t[p].lmax = max(t[p * 2].lmax, t[p * 2].sum + t[p * 2 + 1].lamx);
t[p].rmax = max(t[p * 2 + 1].rmax, t[p * 2 + 1].sum + t[p * 2].rmax);
t[p].dat = max(max(t[p * 2].dat, t[p * 2 + 1].dat), t[p * 2].rmax, t[p * 2 + 1].lmax);
3. 在 ask 时统计:
ans.dat = max(max(l.dat, r.dat), l.rmax + r.lmax);
ans.lmax = max(l.lmax, l.sum + r.lmax);
ans.rmax = max(r.rmax, r.sum + l.rmax);
ans.sum = l.sum + r.sum;
特别的,当到达两边边界时,可能出现最左端只有一个右子树,即 l > mid 时:
ans.lmax = max(ans.lmax, r.lmax); 同理 ans.rmax = max(ans.rmax, l.rmax);

#include <iostream>
using namespace std;
const int N = 5e5 + 10;
struct node {
    int l, r;
    int dat, sum, lmax, rmax;
} t[N * 4];
int n, m;
int a[N];

void build(int p, int l, int r) {
    t[p].l = l, t[p].r = r;
    if(l == r) {
        t[p].sum = t[p].dat = t[p].lmax = t[p].rmax = a[l];
        return;
    }
    int mid = (l + r) / 2;
    build(p * 2, l, mid);
    build(p * 2 + 1, mid + 1, r);
    t[p].sum = t[p * 2].sum + t[p * 2 + 1].sum;
    t[p].lmax = max(t[p * 2].lmax, t[p * 2].sum + t[p * 2 + 1].lmax);
    t[p].rmax = max(t[p * 2 + 1].rmax, t[p * 2 + 1].sum + t[p * 2].rmax);
    t[p].dat = max(max(t[p * 2].dat, t[p * 2 + 1].dat), t[p * 2].rmax + t[p * 2 + 1].lmax);
}

void change(int p, int x, int v) {
    if(t[p].l == t[p].r) {
        t[p].sum = t[p].dat = t[p].lmax = t[p].rmax = v;
        return;
    }
    int mid = (t[p].l + t[p].r) / 2;
    if(x <= mid) change(p * 2, x, v);
    else change(p * 2 + 1, x, v);
    t[p].sum = t[p * 2].sum + t[p * 2 + 1].sum;
    t[p].lmax = max(t[p * 2].lmax, t[p * 2].sum + t[p * 2 + 1].lmax);
    t[p].rmax = max(t[p * 2 + 1].rmax, t[p * 2 + 1].sum + t[p * 2].rmax);
    t[p].dat = max(max(t[p * 2].dat, t[p * 2 + 1].dat), t[p * 2].rmax + t[p * 2 + 1].lmax);
}

node ask(int p, int l, int r) {
    if(l <= t[p].l && t[p].r <= r) {
        return t[p];
    }
    node ans, a, b;
    a.sum = a.lmax = a.rmax = a.dat = b.sum = b.lmax = b.rmax = b.dat = -(1 << 30);
    ans.sum = 0;
    int mid = (t[p].l + t[p].r) / 2;
    if(l <= mid) {
        a = ask(p * 2, l, r);
        ans.sum += a.sum;
    }
    if(r > mid) {
        b = ask(p * 2 + 1, l, r);
        ans.sum += b.sum;
    }
    ans.dat = max(max(a.dat, b.dat), a.rmax + b.lmax);
    ans.lmax = max(a.lmax, a.sum + b.lmax);
    ans.rmax = max(b.rmax, b.sum + a.rmax);
    if(l > mid) ans.lmax = max(ans.lmax, b.lmax);
    if(r <= mid) ans.rmax = max(ans.rmax, a.rmax);
    return ans;
}

int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);
    while(m--) {
        int k, x, y;
        cin >> k >> x >> y;
        if(k == 1) {
            if(x > y) swap(x, y);
            cout << ask(1, x, y).dat << endl;
        } else change(1, x, y);
    }
    return 0;
}


活动打卡代码 AcWing 244. 谜一样的牛

Donyeoh
20小时前

树状数组 + 二分 \ 倍增
1. 由于是统计前面比当前矮的,因此可以从后面开始枚举。对于每一个,留下最小的 a[i] 个给前面的选,因此从 1 ~ n 中没有被选过中选第 a[i] + 1 小的。
2. 可以用一个标记数组,标记哪些数被选过,然后从中挑第 a[i] + 1 个 1,可以用树状数组来维护,并用二分来找到这个位置。

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n;
int a[N], h[N], c[N];

int ask(int x) {
    int ans = 0;
    for(; x; x -= x & -x) ans += c[x];
    return ans;
}

void add(int x, int y) {
    for(; x <= n; x += x & -x) c[x] += y;
}

int main() {
    cin >> n;
    for(int i = 2; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) add(i, 1);
    for(int i = n; i >= 0; i--) {
        int l = 1, r = n;
        while(l < r) {
            int mid = l + r >> 1;
            if(ask(mid) >= a[i] + 1) r = mid;
            else l = mid + 1;
        }
        h[i] = r;
        add(r, -1);
    }
    for(int i = 1; i <= n; i++) cout << h[i] << endl;
    return 0;
}
  1. 树状数组已经为我们维护了区间长度为 2 的次幂的一些信息。
  2. 设 sum 为 1 累加的数量,ans 为第几个位置,从 log2(n) 开始枚举,若 ans + 2 ^ p <= n && sum + c[ans + 2 ^ p] <= a[i], 则累加 ans += 2 ^ p, sum += c[ans + 2 ^ p].
  3. 因为 01 序列 sum 累加过程中,碰到 0 也是直接加上去的,知道找到 1 或者边界才会停止,因此 sum <= a[i] 而不是 a[i] + 1.最终的答案就是 ans + 1.
#include <iostream>
#include <cmath>
using namespace std;
const int N = 1e5 + 10;
int n;
int a[N], h[N], c[N], f[30];

void add(int x, int y) {
    for(; x <= n; x += x & -x) c[x] += y;
}

int main() {
    cin >> n;
    for(int i = 2; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) add(i, 1);
    int t = log2(n);
    f[0] = 1;
    for(int i = 1; i <= 20; i++) f[i] = f[i - 1] * 2;
    for(int i = n; i >= 0; i--) {
        int sum = 0, ans = 0;
        for(int p = t; p >= 0; p--)
            if(ans + f[p] <= n && sum + c[ans + f[p]] <= a[i])
                ans += f[p], sum += c[ans];
        h[i] = ans + 1;
        add(ans + 1, -1);
    }
    for(int i = 1; i <= n; i++) cout << h[i] << endl;
    return 0;
}



Donyeoh
1天前

树状数组 + 等差的差分数组求和 | 线段树 + 延迟标记
1. sum(sum(b[j]), 1 <= j <= i), l <= i <= r) = sum((r - i + 1) * b[i] - i * b[i], l <= i <= r) = sum(i * b[i] - (l - 1) * b[i], l <= i <= r).
2. 因此求出差分数组 d[i] 前缀和,以及 d[i] * i 前缀和即可。

#include <iostream>
#define int long
using namespace std;
const int N = 1e5 + 10;
int n, m;
int s[N], c[2][N];

int ask(int x, int op) {
    int ans = 0;
    for(; x; x -= x & -x) ans += c[op][x];
    return ans;
}

void add(int x, int y, int op) {
    for(; x <= n; x += x & -x) c[op][x] += y;
}

signed main() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> s[i], s[i] += s[i - 1];
    while(m--) {
        char ch;
        cin >> ch;
        if(ch == 'C') {
            int l, r, d;
            cin >> l >> r >> d;
            add(l, d, 0);
            add(r + 1, -d, 0);
            add(l, l * d, 1);
            add(r + 1, -(r + 1) * d, 1);
        } else {
            int l, r;
            cin >> l >> r;
            cout << (s[r] + (r + 1) * ask(r, 0) - ask(r, 1)) -
                 (s[l - 1] + (l - 1 + 1) * ask(l - 1, 0) - ask(l - 1, 1)) << endl;
        }
    }
    return 0;
}
  1. 延迟标记:它自身保存的信息已经被修改完毕,但子节点等待更新。
  2. 对任意节点的修改指令都延迟到 “在后续操作中递归进入它的父节点时” 再进行。
#include <iostream>
#define int long long
using namespace std;
const int N = 1e5 + 10;
struct node {
    int l, r;
    int sum, add;
} t[N * 4];
int n, m;
int a[N];

void build(int p, int l, int r) {
    t[p].l = l, t[p].r = r;
    if(l == r) {
        t[p].sum = a[l];
        return;
    }
    int mid = l + r >> 1;
    build(p * 2, l, mid);
    build(p * 2 + 1, mid + 1, r);
    t[p].sum = t[p * 2].sum + t[p * 2 + 1].sum;
}

void spread(int p) {
    if(t[p].add) {
        t[p * 2].sum += t[p].add * (t[p * 2].r - t[p * 2].l + 1);
        t[p * 2 + 1].sum += t[p].add * (t[p * 2 + 1].r - t[p * 2 + 1].l + 1);
        t[p * 2].add += t[p].add;
        t[p * 2 + 1].add += t[p].add;
        t[p].add = 0;
    }
}

void change(int p, int l, int r, int d) {
    if(l <= t[p].l && r >= t[p].r) {
        t[p].sum += d * (t[p].r - t[p].l + 1);
        t[p].add += d;
        return;
    }
    spread(p);
    int mid = t[p].l + t[p].r >> 1;
    if(l <= mid) change(p * 2, l, r, d);
    if(r > mid) change(p * 2 + 1, l, r, d);
    t[p].sum = t[p * 2].sum + t[p * 2 + 1].sum;
}

int ask(int p, int l, int r) {
    if(l <= t[p].l && r >= t[p].r) return t[p].sum;
    spread(p);
    int mid = t[p].l + t[p].r >> 1;
    int val = 0;
    if(l <= mid) val += ask(p * 2, l, r);
    if(r > mid) val += ask(p * 2 + 1, l, r);
    return val;
}

signed main() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);
    while(m--) {
        char ch;
        cin >> ch;
        if(ch == 'Q') {
            int l, r;
            cin >> l >> r;
            cout << ask(1, l, r) << endl;
        } else {
            int l, r, d;
            cin >> l >> r >> d;
            change(1, l, r, d);
        }
    }
    return 0;
}



Donyeoh
1天前

树状数组 + 差分
1. 用树状数组维护差分,查询差分数组是多少累加到原数组即可。

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int a[N], c[N];

int ask(int x) {
    int ans = 0;
    for(; x; x -= x & -x) ans += c[x];
    return ans;
}

void add(int x, int y) {
    for(; x <= n; x += x & -x) c[x] += y;
}

int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];
    while(m--) {
        char ch;
        cin >> ch;
        if(ch == 'C') {
            int l, r, d;
            cin >> l >> r >> d;
            add(l, d);
            add(r + 1, -d);
        } else {
            int x;
            cin >> x;
            cout << (long long) ask(x) + a[x] << endl;
        }
    }
    return 0;
}


活动打卡代码 AcWing 241. 楼兰图腾

Donyeoh
1天前

树状数组
1. 树状数组记录个数,查询左边有多少个数大于当前数、小于当前数;查询右边 …

#include <iostream>
#include <cstring>
using namespace std;
const int N = 2e5 + 10;
int n;
int a[N], lu[N], ld[N], ru[N], rd[N], c[N];

int ask(int x) {
    int ans = 0;
    for(; x; x -= x & -x) ans += c[x];
    return ans;
}

void add(int x, int y) {
    for(; x <= n; x += x & -x) c[x] += y;
}

int main() {
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) {
        ld[i] = ask(a[i] - 1);
        lu[i] = ask(n) - ask(a[i]);
        add(a[i], 1);
    }
    memset(c, 0, sizeof(c));
    for(int i = n; i >= 1; i--) {
        rd[i] = ask(a[i] - 1);
        ru[i] = ask(n) - ask(a[i]);
        add(a[i], 1);
    }
    long long up = 0, down = 0;
    for(int i = 1; i <= n; i++)
        up += (long long) lu[i] * ru[i], down += (long long) ld[i] * rd[i];
    cout << up << " " << down <<endl;
    return 0;
}


活动打卡代码 AcWing 240. 食物链

Donyeoh
1天前

扩展域并查集 | 边带权并查集
1. 有三类动物,因此可以将 x 分为:与 x 同类的 x_a,x 吃的类 b,吃 x 的类 c。
2. d = 1 表示 x 与 y 同类, 检查是否有 x 吃的类,以及吃 x 的类,即:(x_b, y_a), (x_a, y_b).合并 (x_a, y_a), (x_b, y_b), (x_c, y_c).
3. d = 2 表示 x 吃 y,检查是否有 x 与 y 同类,以及 y 吃 x,即:(x_a, y_a), (x_a, y_b).合并 (x_b, y_a), (x_c, y_c), (x_a, y_c).还要特判 x = y 的情况。

#include <iostream>
using namespace std;
const int N = 5e4 + 10;
int n, k;
int fa[N * 3];

int get(int x) {
    if(x == fa[x]) return x;
    return fa[x] = get(fa[x]);
}

void merge(int x, int y) {
    fa[get(x)] = get(y);
}

int main() {
    cin >> n >> k;
    int ans = 0;
    for(int i = 1; i <= n * 3; i++) fa[i] = i;
    while(k--) {
        int d, x, y;
        cin >> d >> x >> y;
        if(x > n || y > n) {
            ans++;
            continue;
        }
        int x_a = x, x_b = x + n, x_c = x + 2 * n;
        int y_a = y, y_b = y + n, y_c = y + 2 * n;
        if(d == 1) {
            if(get(x_b) == get(y_a) || get(x_a) == get(y_b)) {
                ans++;
                continue;
            }
            merge(x_a, y_a), merge(x_b, y_b), merge(x_c, y_c);
        } else {
            if(get(x_a) == get(y_a) || get(x_a) == get(y_b)) {
                ans++;
                continue;
            }
            merge(x_b, y_a), merge(x_c, y_b), merge(x_a, y_c);
        }
    }
    cout << ans << endl;
    return 0;
}
  1. 有 3 中状态,0 + 0 = 0, 1 + 0 = 1, 2 + 0 = 2, 因此用 fa[x] = 0 表示 x 和父节点同类。1 + 1 = 2,可以用 fa[x] = 1 表示 x 吃父节点;fa[x] = 2 表示 x 被父节点吃。
  2. 路劲压缩时累加父节点,再取模即可。合并时,若 d = 1,判断 (d[x] - d[y]) % 3 = 0 (因为是有方向的,所以是 - 去。若是加号那么就没有方向了);否则判断 (d[x] - d[y]) % 3 = 1.设 x 的父节点为 p,d[x] + d[p] - d[y] = ans, 即可得出 d[p].
#include <iostream>
using namespace std;
const int N = 5e4 + 10;
int n, k;
int fa[N], w[N];

int get(int x) {
    if(x == fa[x]) return x;
    int root = get(fa[x]);
    w[x] = (w[x] + w[fa[x]]) % 3;
    return fa[x] = root;
}

int main() {
    cin >> n >> k;
    for(int i = 1; i <= n; i++) fa[i] = i;
    int ans = 0;
    while(k--) {
        int d, x, y;
        cin >> d >> x >> y;
        if(x > n || y > n) {
            ans++;
            continue;
        }
        int p = get(x), q = get(y);
        if(d == 1) {
            if(p == q) {
                if(((w[x] - w[y]) % 3 + 3) % 3 != 0) ans++;
                continue;
            } else w[p] = ((0 - w[x] + w[y]) % 3 + 3) % 3;
        } else {
            if(p == q) {
                if(((w[x] - w[y]) % 3 + 3) % 3 != 1) ans++;
                continue;
            } else w[p] = ((1 - w[x] + w[y]) % 3 + 3) % 3;
        }
        fa[p] = q;
    }
    cout << ans << endl;
    return 0;
}