Overcooked（并查集、线段树）

• • Overcooked!
  • • 题目描述
    • 输入描述
    • 输出描述
    • 样例
    • 并查集
    • • 题解
      • 代码
    • 线段树
    • • 题解
      • 代码

传送门

输入

5 5
1 1 2
3 1 2
2 2 4
3 1 4
3 2 5

输出

YES
YES
NO

题意：

读入 o p , x , y {op,x,y} op,x,y

• o p = = 1 {op == 1} op==1： x 与 y 合 并 {x与y合并} x与y合并
• o p = = 2 {op == 2} op==2： x 到 y 之 间 合 并 {x到y之间合并} x到y之间合并
• o p = = 3 {op ==3} op==3： 询 问 x 与 y 是 否 一 个 集 合 {询问x与y是否一个集合} 询问x与y是否一个集合

思路

1、3操作容易，重点就在2操作，如果正常用并查集拉x、y范围会TLE。

所以在这里，加上一个数组 n e {ne} ne 优化。 n e [ x ] {ne[x]} ne[x] 表示 x {x} x 向右的第一个不在同一个集合中的数。

对于 n e {ne} ne 的初始化， n e [ i ] = i + 1 {ne[i] = i + 1} ne[i]=i+1。在执行 o p = = 2 {op==2} op==2时， n e [ ] {ne[]} ne[] 可以快速跨越 [ x , y ] {[x,y]} [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 
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;
}