#include <cstdio>
#include <cstdlib>
#include <vector>
#include <queue>
#include <iostream>
//#include "werewolf.h"
using namespace std;
std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
std::vector<int> S, std::vector<int> E,
std::vector<int> L, std::vector<int> R);
struct edge {
int f, t, w;
};
class cmp1 { // MST for wolf
public:
bool operator() (edge x, edge y) {
return x.w > y.w;
}
};
class cmp2 { // MST for human
public:
bool operator() (edge x, edge y) {
return x.w < y.w;
}
};
std::priority_queue<edge, std::vector<edge>, cmp1> wolf;
std::priority_queue<edge, std::vector<edge>, cmp2> human;
const int MAXN = 2e5 + 12;
int dsu1[MAXN], dsu2[MAXN];
int set_of1(int u) {
if(dsu1[u] == u) return u;
return dsu1[u] = set_of1(dsu1[u]);
}
int set_of2(int u) {
if(dsu2[u] == u) return u;
return dsu2[u] = set_of2(dsu2[u]);
}
void union1(int u, int v) {
dsu1[set_of1(u)] = set_of1(v);
}
void union2(int u, int v) {
dsu2[set_of2(u)] = set_of2(v);
}
int rep1[MAXN];
int rep2[MAXN];
std::vector<int> krt_wolf[2 * MAXN];
std::vector<int> krt_human[2 * MAXN];
int wlim_wolf[2 * MAXN];
int wlim_human[2 * MAXN];
int assigned[MAXN];
int stoN;
int q;
int mi[2 * MAXN], ma[2 * MAXN];
int par_wolf[19][2 * MAXN];
int wolfdepth[2 * MAXN];
std::pair<int, int> dfs1(int node, int curdepth) {
wolfdepth[node] = curdepth;
if(node < stoN) {
assigned[node] = q++;
mi[node] = ma[node] = assigned[node];
return {assigned[node], assigned[node]};
}
mi[node] = 1e9, ma[node] = -1;
for(int x: krt_wolf[node]) {
std::pair<int, int> res = dfs1(x, curdepth + 1);
mi[node] = std::min(mi[node], res.first);
ma[node] = std::max(ma[node], res.second);
par_wolf[0][x] = node;
}
return {mi[node], ma[node]};
}
int par_human[19][2 * MAXN];
int A[MAXN];
int humandepth[2 * MAXN];
int rangel[2 * MAXN], ranger[2 * MAXN];
std::pair<int, int> dfs2(int node, int curdepth) {
humandepth[node] = curdepth;
if(node < stoN) {
A[q] = assigned[node];
rangel[node] = ranger[node] = q;
q++;
return {rangel[node], ranger[node]};
}
rangel[node] = 1e9, ranger[node] = -1;
for(int x: krt_human[node]) {
std::pair<int, int> res = dfs2(x, curdepth + 1);
rangel[node] = std::min(rangel[node], res.first);
ranger[node] = std::max(ranger[node], res.second);
par_human[0][x] = node;
}
return {rangel[node], ranger[node]};
}
struct wavelet_tree {
int lo, hi;
wavelet_tree *l, *r;
int *b, *c, bsz, csz; // c holds the prefix sum of elements
wavelet_tree() {
lo = 1;
hi = 0;
bsz = 0;
csz = 0, l = NULL;
r = NULL;
}
void init(int *from, int *to, int x, int y) {
lo = x, hi = y;
if(from >= to) return;
int mid = (lo + hi) >> 1;
auto f = [mid](int x) {
return x <= mid;
};
b = (int*)malloc((to - from + 2) * sizeof(int));
bsz = 0;
b[bsz++] = 0;
c = (int*)malloc((to - from + 2) * sizeof(int));
csz = 0;
c[csz++] = 0;
for(auto it = from; it != to; it++) {
b[bsz] = (b[bsz - 1] + f(*it));
c[csz] = (c[csz - 1] + (*it));
bsz++;
csz++;
}
if(hi == lo) return;
auto pivot = stable_partition(from, to, f);
l = new wavelet_tree();
l->init(from, pivot, lo, mid);
r = new wavelet_tree();
r->init(pivot, to, mid + 1, hi);
}
//kth smallest element in [l, r]
//for array [1,2,1,3,5] 2nd smallest is 1 and 3rd smallest is 2
int kth(int l, int r, int k) {
if(l > r) return 0;
if(lo == hi) return lo;
int inLeft = b[r] - b[l - 1], lb = b[l - 1], rb = b[r];
if(k <= inLeft) return this->l->kth(lb + 1, rb, k);
return this->r->kth(l - lb, r - rb, k - inLeft);
}
//count of numbers in [l, r] Less than or equal to k
int LTE(int l, int r, int k) {
if(l > r || k < lo) return 0;
if(hi <= k) return r - l + 1;
int lb = b[l - 1], rb = b[r];
return this->l->LTE(lb + 1, rb, k) + this->r->LTE(l - lb, r - rb, k);
}
//count of numbers in [l, r] equal to k
int count(int l, int r, int k) {
if(l > r || k < lo || k > hi) return 0;
if(lo == hi) return r - l + 1;
int lb = b[l - 1], rb = b[r];
int mid = (lo + hi) >> 1;
if(k <= mid) return this->l->count(lb + 1, rb, k);
return this->r->count(l - lb, r - rb, k);
}
//sum of numbers in [l ,r] less than or equal to k
int sum(int l, int r, int k) {
if(l > r or k < lo) return 0;
if(hi <= k) return c[r] - c[l - 1];
int lb = b[l - 1], rb = b[r];
return this->l->sum(lb + 1, rb, k) + this->r->sum(l - lb, r - rb, k);
}
//count max element in [l, r] stricly smaller than k
int upper_bound(int l, int r, int k) {
if(l > r) return -1;
int uwu = LTE(l, r, k - 1);
if(uwu == 0) return -1;
return kth(l, r, uwu);
}
~wavelet_tree() {
delete l;
delete r;
}
};
std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
std::vector<int> S, std::vector<int> E,
std::vector<int> L, std::vector<int> R) {
stoN = N;
for(int i=0; i<N; i++) {
dsu1[i] = dsu2[i] = i;
rep1[i] = rep2[i] = i;
wlim_wolf[i] = wlim_human[i] = i; //idk anymore
}
int Q = S.size();
std::vector<int> Answer(Q);
int M = X.size();
for(int i=0; i<M; i++) {
wolf.push({X[i], Y[i], std::max(X[i], Y[i])});
human.push({X[i], Y[i], std::min(X[i], Y[i])});
}
int newnode = N;
while(wolf.size()) {
if(set_of1(wolf.top().f) != set_of1(wolf.top().t)) {
int ff = rep1[set_of1(wolf.top().f)];
int tt = rep1[set_of1(wolf.top().t)];
union1(wolf.top().f, wolf.top().t);
krt_wolf[newnode].push_back(ff);
krt_wolf[newnode].push_back(tt);
wlim_wolf[newnode] = wolf.top().w;
rep1[set_of1(wolf.top().f)] = newnode;
newnode++;
}
wolf.pop();
}
int wolfrt = newnode - 1;
newnode = N;
while(human.size()) {
if(set_of2(human.top().f) != set_of2(human.top().t)) {
int ff = rep2[set_of2(human.top().f)];
int tt = rep2[set_of2(human.top().t)];
union2(human.top().f, human.top().t);
krt_human[newnode].push_back(ff);
krt_human[newnode].push_back(tt);
wlim_human[newnode] = human.top().w;
rep2[set_of2(human.top().f)] = newnode;
newnode++;
}
human.pop();
}
int humanrt = newnode - 1;
dfs1(wolfrt, 0);
par_wolf[0][wolfrt] = wolfrt;
for(int i=1; i<19; i++) {
for(int j=0; j<=wolfrt; j++) {
par_wolf[i][j] = par_wolf[i-1][par_wolf[i-1][j]];
}
}
q = 0;
dfs2(humanrt, 0);
par_human[0][humanrt] = humanrt;
for(int i=1; i<19; i++) {
for(int j=0; j<=humanrt; j++) {
par_human[i][j] = par_human[i-1][par_human[i-1][j]];
}
}
/*
std::cout << "wolf\n";
for(int i=wolfrt; i >= 0; i--) {
std::cout << "node "<<i<<". weight limit = "<<wlim_wolf[i]<<", node new ids range = [" << mi[i] << ", " << ma[i] << "]\n";
for(int x: krt_wolf[i]) std::cout << i << ' ' << x << '\n';
}
std::cout << "human\n";
for(int i=humanrt; i >= 0; i--) {
std::cout << "node " <<i<<". weight limit = "<<wlim_human[i]<<"\n";
for(int x: krt_human[i]) std::cout << i << ' ' << x << '\n';
}
for(int i=0; i<N; i++) {
for(int j=0; j<N; j++) {
if(assigned[j] == i) {
std::cout << "order " << i <<": " << j <<"\n";
}
}
}
*/
wavelet_tree wlt;
int B[N + 1];
for(int i=0; i<N; i++) B[i + 1] = A[i];
wlt.init(B + 1, B + N + 1, 0, N - 1);
/*
std::cout << "A array:";
for(int i=0; i<N; i++) std::cout << " " << A[i];
std::cout << "\n";
cout << wlt.LTE(0, 0, 5) << "\n";
cout << wlt.kth(1, 1, 1) <<"\n";
cout << wlt.upper_bound(0, 0, 6) << " uss\n";
*/
for(int i=0; i<Q; i++) {
for(int j=18; j>=0; j--) {
if(humandepth[S[i]] >= (1 << j) && wlim_human[par_human[j][S[i]]] >= L[i]) S[i] = par_human[j][S[i]];
if(wolfdepth[E[i]] >= (1 << j) && wlim_wolf[par_wolf[j][E[i]]] <= R[i]) E[i] = par_wolf[j][E[i]];
}
int l = mi[E[i]];
int r = ma[E[i]];
int humanl = rangel[S[i]];
int humanr = ranger[S[i]];
/*
std::cout << "query "<<i<<": ";
std::cout<<S[i]<<" "<<E[i]<<" ";
std::cout << "human array range [" << humanl << ", " << humanr << "] see see if any element in [" << l << ", " << r << "], ";
*/
int res = wlt.upper_bound(humanl + 1, humanr + 1, r + 1);
/*
int res = -1;
for(int i = humanl; i <= humanr; i++) {
if(A[i] <= r) res = std::max(res, A[i]);
}
*/
/*
std::cout << "res=" << res<<"\n";
*/
if(res != -1 && l <= res && res <= r) {
Answer[i] = 1;
}
else {
Answer[i] = 0;
}
}
return Answer;
}
Compilation message
werewolf.cpp: In member function 'void wavelet_tree::init(int*, int*, int, int)':
werewolf.cpp:145:18: error: 'stable_partition' was not declared in this scope
145 | auto pivot = stable_partition(from, to, f);
| ^~~~~~~~~~~~~~~~
