#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
//10:20
const int mxN = 2e5;
template <class T>
struct KRT {
int ncnt, dsu[2*mxN], val[2*mxN], anc[2*mxN][19];
vector<int> g[2*mxN];
T cmp;
int f(int x) {return dsu[x] == x ? x : dsu[x] = f(dsu[x]);}
KRT (int n, vector<int> &u, vector<int> &v) : ncnt(n) {
iota(begin(dsu), end(dsu), 0);
vector<int> order(u.size());
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int a, int b) {return cmp(max(u[a], v[a], cmp), max(u[b], v[b], cmp));});
for (int e: order) {
int a = f(u[e]), b = f(v[e]);
if (a != b) {
anc[a][0] = anc[b][0] = dsu[b] = dsu[a] = ncnt;
val[ncnt] = max(u[e], v[e], cmp);
g[ncnt].push_back(a);
g[ncnt].push_back(b);
ncnt++;
}
}
anc[ncnt-1][0] = ncnt-1;
for (int i = 1; i < 19; ++i) for (int j = 0; j < ncnt; ++j) anc[j][i] = ncnt-1;
for (int i = 1; i < 19; ++i) {
for (int j = 0; j < ncnt; ++j) {
anc[j][i] = anc[anc[j][i-1]][i-1];
}
}
}
int thresh(int x, int v) {
for (int i = 19; i--;) {
if (!cmp(v,val[anc[x][i]])) x = anc[x][i];
}
return x;
}
};
int tcnt, st[2*mxN], en[2*mxN];
void dfs1(int u, KRT<less<int>> &k) {
st[u] = tcnt++;
for (int v: k.g[u]) dfs1(v, k);
en[u] = tcnt;
}
struct qry {int l, r, id;};
vector<qry> qrys[2*mxN];
vector<int> ans;
set<int> sts[2*mxN];
void dfs2(int u, KRT<greater<int>> &k) {
for (int v: k.g[u]) {
dfs2(v, k);
sts[u].merge(sts[v]);
}
for (qry q: qrys[u]) {
auto it = sts[u].lower_bound(q.l);
ans[q.id] = it != sts[u].end() && *it < q.r;
}
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y,
vector<int> S, vector<int> E,
vector<int> L, vector<int> R) {
int Q = S.size();
ans.resize(Q);
KRT<less<int>> wolf(N,X,Y);
KRT<greater<int>> human(N,X,Y);
dfs1(wolf.ncnt-1, wolf);
for (int i = 0; i < N; ++i) sts[i].insert(st[i]);
for (int i = 0; i < Q; ++i) {
int x = wolf.thresh(E[i], R[i]);
qrys[human.thresh(S[i], L[i])].push_back({st[x], en[x], i});
}
dfs2(human.ncnt-1, human);
return ans;
}
Compilation message
werewolf.cpp: In function 'void dfs2(int, KRT<std::greater<int> >&)':
werewolf.cpp:59:16: error: 'class std::set<int>' has no member named 'merge'
59 | sts[u].merge(sts[v]);
| ^~~~~
