CF1556G Gates to Another World

*3300

这种 \(2 ^ n\) 和区间，看着就很想套上线段树，事实上是对的。

引理 1 ：

在线段数内同一颗子树内的点可以互相到达。

这个是非常容易验证的，把边画出来就是在一条链上挂若干条横着的链。

然后我们考虑把区间挂上去，然后用时光倒流转化为加边。我们发现，我们可以用叶子节点来代表若干区间，然后在上面打上时间戳来看这个时候是否存在。

考虑到不同时间不同子树的联通性，我们要使用线段树合并暴力连边，然后递归到叶子节点的时候可以使用并查集来维护连通性。

整个时间复杂度有点复杂，反正能过。

// LUOGU_RID: 119091043
#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l; i <= r; i ++)
#define per(i, r, l) for (int i = r; i >= l; i --)
#define pb push_back
#define ll long long
using namespace std;

const int _ = 5e4 + 5, __ = _ * 100;

int n, m, qn;
ll lim;
bool ans[_];
int tot = 1, lc[__], rc[__], tim[__], anc[__];
struct query { ll a, b; int id; } q[_];

vector <int> ele[_], e[__];

int find (int x) { 
	return x == anc[x] ? x : anc[x] = find(anc[x]);
}
bool leaf (int x) { return !lc[x] && !rc[x]; }
void pushdown (int x) {
	if (!lc[x]) lc[x] = ++ tot;
	if (!rc[x]) rc[x] = ++ tot;
	if (tim[x]) tim[lc[x]] = tim[rc[x]] = tim[x], tim[x] = 0;
}
int findnode (int x, ll l, ll r, ll p) {
	if (leaf(x)) return x;
	ll mid = (l + r) >> 1ll;
	if (p <= mid) return findnode(lc[x], l, mid, p);
	else return findnode(rc[x], mid + 1, r, p);
}
void cover (int x, ll l, ll r, ll ql, ll qr, int k) {
	if (ql <= l && r <= qr) return tim[x] = k, void();
	ll mid = (l + r) >> 1ll; pushdown(x);
	if (ql <= mid) cover(lc[x], l, mid, ql, qr, k);
	if (qr > mid) cover(rc[x], mid + 1, r, ql, qr, k);
}
void assign (int x, ll l, ll r) {
	if (leaf(x)) return ele[tim[x]].pb(x), void();
	ll mid = (l + r) >> 1ll; pushdown(x); 
	assign(lc[x], l, mid), assign(rc[x], mid + 1, r);
}
void merge (int x, int y) {
	if (leaf(x) && leaf(y)) return ((tim[x] < tim[y]) ? e[x].pb(y) : e[y].pb(x)), void();
	if (leaf(x)) return merge(x, lc[y]), merge(x, rc[y]), void();
	if (leaf(y)) return merge(y, lc[x]), merge(y, rc[x]), void();
	return merge(lc[x], lc[y]), merge(rc[x], rc[y]), void();
}

signed main () {
	cin >> n >> m, lim = (1ll << n) - 1;
	rep(i, 1, m) {
		string x;
		cin >> x;
		scanf("%lld %lld", & q[i].a, & q[i].b);
		if (x[0] == 'a') q[i].id = ++ qn;
	}
	tim[1] = m + 1;
	per(i, m, 1) if (!q[i].id) cover(1, 0, lim, q[i].a, q[i].b, i);
	assign(1, 0, lim);
	rep(x, 1, tot) if (! leaf(x)) merge(lc[x], rc[x]);
	rep(i, 1, tot) anc[i] = i;
	for (int x : ele[m + 1]) 
		for (int y : e[x]) if (find(x) != find(y)) anc[find(x)] = find(y);
	per(i, m, 1) {
		if (! q[i].id) {
			for (int x : ele[i]) 
				for (int y : e[x]) if (find(x) != find(y)) anc[find(x)] = find(y);
		} else {
			int x = findnode(1, 0, lim, q[i].a), y = findnode(1, 0, lim, q[i].b);
			if (find(x) == find(y)) ans[q[i].id] = 1;
	 	}
	}
	rep(i, 1, qn) printf("%lld\n", ans[i]);
	return 0;
}