Overcooked!
题目描述
输入描述
输出描述
样例
输入
5 5
1 1 2
3 1 2
2 2 4
3 1 4
3 2 5
输出
YES
YES
NO
并查集
题解
题意：
读入 op,x,y
op==1： x 与 y 合 并
op==2： x 到 y 之 间 合 并
op==3： 询 问 x 与 y 是 否 一 个 集 合
思路
1、3操作容易，重点就在2操作，如果正常用并查集拉x、y范围会TLE。
所以在这里，加上一个数组ne 优化。ne[x] 表示 x 向右的第一个不在同一个集合中的数。
对于 n e 的初始化，ne[i]=i+1。在执行op==2时，ne[] 可以快速跨越[x,y] 区间并且并到一个集合中。
代码
int n, m; int fa[N], ne[N]; int find(int x) { return fa[x] = fa[x] == x ? x : find(fa[x]); } void solve() { cin >> n >> m; for (int i = 1; i <= n; i++) fa[i] = i, ne[i] = i + 1; while(m--) { int op, x, y; cin >> op >> x >> y; if(op == 1) { fa[find(x)] = find(y); } else if(op == 2) { while(x <= y) { int t = ne[x]; fa[find(x)] = find(y); ne[x] = ne[y]; x = t; } } else { if(find(x) == find(y)) cout << "YES" << endl; else cout << "NO" << endl; } } }
线段树
题解
思路
- 区间修改+单点修改
- 单点查询
代码
#include <bits/stdc++.h> using namespace std; #define ls u<<1 #define rs u<<1|1 const int N = 1000010; struct node { int l, r; int v, add; } tr[N << 2]; int n, m; int fa[N]; int find(int x) { return fa[x] = fa[x] == x ? x : find(fa[x]); } void pushup(int u) { if(tr[ls].v == tr[rs].v) tr[u].v = tr[ls].v; } void pushdown(int u) { if(tr[u].add) { tr[ls].v = tr[rs].v = tr[ls].add = tr[rs].add = tr[u].add; tr[u].add = 0; } } void build(int u, int l, int r) { tr[u] = {l, r}; if(l == r) { tr[u].v = fa[l]; return ; } int mid = l + r >> 1; build(ls, l, mid), build(rs, mid + 1, r); pushup(u); } void modify(int u, int l, int r, int v) { if(tr[u].l >= l && tr[u].r <= r) { tr[u].v = tr[u].add = v; return ; } int mid = tr[u].l + tr[u].r >> 1; // pushdown(u); if(l <= mid) modify(ls, l, r, v); if(r > mid) modify(rs, l, r, v); pushup(u); } int query(int u, int x) { if(tr[u].l == tr[u].r) return tr[u].v; int mid = tr[u].l + tr[u].r >> 1; pushdown(u); if(x <= mid) return query(ls, x); return query(rs, x); } int main() { cin >> n >> m; for (int i = 1; i <= n; i++) fa[i] = i; build(1, 1, n); int op, x, y; int a, b; for (int i = 1; i <= m; i++) { cin >> op >> x >> y; a = query(1, x); b = query(1, y); if(op == 1) { if(find(a) != find(b)) { fa[find(a)] = find(b); modify(1, x, x, find(b)); // modify(1, y, y, find(b)); } } else if(op == 2) { if(find(a) != find(b)) fa[find(a)] = find(b); modify(1, x, y, find(b)); } else { if(find(a) != find(b)) cout << "NO" << endl; else cout << "YES" << endl; } } return 0; }
