社区讨论

这题的叉点是什么

P5787【模板】线段树分治 / 二分图参与者 1已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@lo2divqh
此快照首次捕获于
2023/10/23 12:04
2 年前
此快照最后确认于
2023/11/03 12:11
2 年前
查看原帖
这份代码Subtask 2 T了
CPP
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cctype>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <cstdlib>
#include <bitset>
#include <deque>
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3fll
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 100005;
int fa[maxn << 1], sz[maxn << 1];
void init() {
    for (int i = 1; i < maxn * 2; i++) fa[i] = i, sz[i] =1;
}
int find(int x) {
    if (x == fa[x]) return fa[x];
    return find(fa[x]);
}
void merge(int a, int b) {
    a = find(a), b = find(b);
    if (a == b) return;
    sz[a] += sz[b];
    fa[b] = a;
}
vector<pair<int, int> > e;
struct node {
    vector<int> g;
} d[maxn << 2];
void update(int l, int r, int s, int t, int v, int p) {
    if (l > r) return;
    if (l <= s && t <= r) {
        d[p].g.push_back(v);
        return;
    }
    int mid = (s + t) >> 1;
    if (l <= mid) update(l, r, s, mid, v, p << 1);
    if (mid < r) update(l, r, mid + 1, t, v, p << 1 | 1);
}
int n, m, k, tot;
struct Opt {
    int x, y;
};
stack<Opt> s;
void solve(int l, int r, int p) {
    int now = s.size();
    bool flag = 1;
    for (int i : d[p].g) {
        int u = e[i].first, v = e[i].second;
        int fu = find(u), fv = find(v);
        if (fu == fv) {
            flag = 0;
            for (int j = l; j <= r; j++) {
                cout << "No" << "\n";
            }
            break;
        }
        merge(find(u + n), fv), merge(find(v + n), fu);
        s.push((Opt){find(u + n), fv});
        s.push((Opt){find(v + n), fu});
    }
    if (flag) {
        if (l == r) {
            cout << "Yes" << "\n";
        } else {
            int mid = (l + r) >> 1;
            solve(l, mid, p << 1);
            solve(mid + 1, r, p << 1 | 1);
        }
    }
    while (s.size() > now) {
        auto p = s.top();
        s.pop();
        sz[p.x] -= sz[p.y], fa[p.y] = p.y;
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> k;
    init();
    for (int i = 1; i <= m; i++) {
        int x, y, l, r;
        cin >> x >> y >> l >> r;
        e.push_back(make_pair(x, y));
        update(l + 1, r, 1, k, e.size() - 1, 1);
    }
    solve(1, k, 1);
    return 0;
}

回复

2 条回复,欢迎继续交流。

正在加载回复...