VK Cup 2015 - Finals, online mirror D. Restructuring Company
昔の SRM に少し似てる問題がありました。
解法
union_find を使います。ただ, type = 2 のものは素直に x, x+1, ..., y を union_find でつなげるという発想では時間が足りません。
そこで, 例えば 4 から 7 の数字を union_find で繋げたら次からはもう 4 から 7 の数字を調べることはやめにしたいです。実際, 4 から 7 が一度同じグループになったらもうグループ同士が引き離されることは無いので,例えば 4 から 7 をつないだ後に 2 から 5 をつなげることになったら 2 と 3, 3 と 4 を union_find でつなげれば他の 4 から 7 とつながっていることはわかっているので
4 と 5, 5 と 6, 6 と 7 をつなぐ作業は省いても問題ないはずです。
これを上手くやるために set
似てると思ったのはこの問題です。mayokoex.hatenablog.com
setから要素をeraseしていって計算量を減らしているところ。…個人的には SRM バージョンのほうが難しいと思いました。
struct UnionFind { vector<int> par; int n, cnt; UnionFind(const int& x = 0) {init(x);} void init(const int& x) {par.assign(cnt=n=x, -1);} inline int find(const int& x) {return par[x] < 0 ? x : par[x] = find(par[x]);} inline bool same(const int& x, const int& y) {return find(x) == find(y);} inline bool unite(int x, int y) { if ((x = find(x)) == (y = find(y))) return false; --cnt; if (par[x] > par[y]) swap(x, y); par[x] += par[y]; par[y] = x; return true; } inline int count() const {return cnt;} inline int count(int x) {return -par[find(x)];} }; int main() { int n, q; cin >> n >> q; UnionFind uf(n+1); set<int> s; for (int i = 1; i <= n; i++) s.insert(i); while (q--) { int t, x, y; scanf("%d%d%d", &t, &x, &y); if (t == 1) { uf.unite(x, y); } else if (t == 2) { auto it = s.lower_bound(x); while (it != s.end() && (*it) < y) { uf.unite((*it), y); s.erase(it++); } } else { if (uf.same(x, y)) printf("YES\n"); else printf("NO\n"); } } return 0; }