P4899 [IOI2018] werewolf 狼人
LOJ#2865.「IOI2018」狼人，第一次AC交互题
kruskal 重构树+主席树
其实知道重构树的算法的话，难度就主要在主席树上
习惯从 (1) 开始标号，所以以下讲解中的标号都是从 (1) 开始的
从 (s) 开始走，只走点 (L,L+1,cdots,n)，能走到的点集记为 (V_1)
从 (e) 开始，只走 (1,2,cdots,R)，能走到的点集记为 (V_2)
则，若 (V_1cap V_2
eq varnothing)，就说明有解，我们可以在交集内的任意一个点变换人狼形式
第一步，求 (V_1,V_2)
考虑 kruskal 重构树，先去这里看更详细的讲解 不知道详细不详细，在这里不会重头开始讲重构树内容
建立两个重构树
- (A) 为以 (max(u,v)) 为权值，用 最小 生成树重构，可以知道，(u,v) 两点路径中，经过的点的最大编号的最小值，就是得出的重构树中 (lca(u,v)) 的点权
- (B) 为以 (min(u,v)) 为权值，用 最大 生成树重构，可以知道，(u,v) 两点路径中，经过的点的最小编号的最大值，就是得出的重构树中 (lca(u,v)) 的点权
所以，由于 kruskal 重构树的一般性质，也可以知道，以 (A) 树为例，与一个点 (u) 之间的路径，经过的点的最大编号的最小值小于等于 (x) 的节点，就是以 从 (u) 到根的路径中，深度最小的，权值小于等于 (x) 的那个点 为根，的子树中的所有叶子节点
好绕，可以用来练习句子成分的确定
然后 (x=R) 时，这样得到的点集，就是 (V_2)
同理，可以用 (B) 树，以相似的方法求出 (V_1)
第二步，求 (V_1,V_2) 是否交集不为空
用主席树，其实可以离线用树状数组，但是并没有看懂是怎么做
主席树其实可以理解为线段树的前缀和，我们把这些点（(2n-1) 个），按照在 (A) 树中的 dfs 序来排序，并以这些点在 (B) 树上的 dfs 序建主席树
然后我们设通过重构树找到的两个点（子树的根）分别是 (a,b)，那么又因为在一个子树内，dfs 序是连续的，所以每次查询 (dfn_bcdots dfn_b+size_b-1) 中，有没有数在 (dfn_acdots dfn_a+size_a-1) 中
其实也不难
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<iomanip>
#include<cstring>
#define reg register
#define EN std::puts("")
#define LL long long
inline int read(){
register int x=0;register int y=1;
register char c=std::getchar();
while(c<'0'||c>'9'){if(c=='-') y=0;c=std::getchar();}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=std::getchar();}
return y?x:-x;
}
#define N 400006
#define M 400006
int n,m;
struct edge{
int u,v;
}e[M];
inline int get_max(int x,int y){return x>y?x:y;}
inline int get_min(int x,int y){return x<y?x:y;}
struct TREE{
int up[N*2],vertex;
int son[2][N];
int fa[19][N],size[N],dfn[N],dfscnt;
int val[N];
inline int find(int k){
return k==up[k]?k:up[k]=find(up[k]);
}
static inline int cmp_A(edge aa,edge aaa){return get_max(aa.u,aa.v)<get_max(aaa.u,aaa.v);}
static inline int cmp_B(edge aa,edge aaa){return get_min(aa.u,aa.v)>get_min(aaa.u,aaa.v);}
inline void build_A(){
std::sort(e+1,e+1+m,cmp_A);
vertex=n;
for(reg int i=1;i<=2*n;i++) up[i]=i;
for(reg int u,v,i=1,cnt=1;cnt<n;i++){
u=find(e[i].u);v=find(e[i].v);
if(u==v) continue;
val[++vertex]=get_max(e[i].u,e[i].v);
son[0][vertex]=u;son[1][vertex]=v;
cnt++;up[u]=up[v]=vertex;
}
}
inline void build_B(){
std::sort(e+1,e+1+m,cmp_B);
vertex=n;
for(reg int i=1;i<=2*n;i++) up[i]=i;
for(reg int u,v,i=1,cnt=1;cnt<n;i++){
u=find(e[i].u);v=find(e[i].v);
if(u==v) continue;
val[++vertex]=get_min(e[i].u,e[i].v);
son[0][vertex]=u;son[1][vertex]=v;
cnt++;up[u]=up[v]=vertex;
}
}
void dfs(int u,int father){
fa[0][u]=father;size[u]=1;dfn[u]=++dfscnt;
for(reg int i=1;i<19;i++) fa[i][u]=fa[i-1][fa[i-1][u]];
if(!son[0][u]) return;
dfs(son[0][u],u);dfs(son[1][u],u);
size[u]+=size[son[0][u]]+size[son[1][u]];
}
inline int get_A(int u,int x){
for(reg int i=18;~i;i--)if(val[fa[i][u]]<=x) u=fa[i][u];
return u;
}
inline int get_B(int u,int x){
for(reg int i=18;~i;i--)if(val[fa[i][u]]>=x) u=fa[i][u];
return u;
}
}A,B;
//主席树部分
struct tr{
tr *ls,*rs;
int x;
}dizhi[10000006],*root[N];
int tot;
inline int cmp(int x,int y){return A.dfn[x]<A.dfn[y];}
void build(tr *tree,int l,int r){
if(l==r) return;
int mid=(l+r)>>1;
tree->ls=&dizhi[tot++];tree->rs=&dizhi[tot++];
build(tree->ls,l,mid);build(tree->rs,mid+1,r);
}
void insert(tr *last,tr *tree,int l,int r,int num,int k){
if(l==r) return tree->x=last->x+k,void();
int mid=(l+r)>>1;
*tree=*last;
if(num<=mid){
tree->ls=&dizhi[tot++];
insert(last->ls,tree->ls,l,mid,num,k);
}
else{
tree->rs=&dizhi[tot++];
insert(last->rs,tree->rs,mid+1,r,num,k);
}
tree->x=tree->ls->x+tree->rs->x;
}
int find(tr *left,tr *right,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr) return right->x-left->x;
int mid=(l+r)>>1;
if(ql<=mid){
if(find(left->ls,right->ls,l,mid,ql,qr)) return 1;
}
if(qr>mid){
if(find(left->rs,right->rs,mid+1,r,ql,qr)) return 1;
}
return 0;
}
int main(){
n=read();m=read();int q=read();
for(reg int i=1;i<=m;i++){
e[i].u=read()+1;e[i].v=read()+1;
}
A.build_A();B.build_B();
A.dfs(2*n-1,2*n-1);B.dfs(2*n-1,2*n-1);
int tmp[n*2];
for(reg int i=1;i<n*2;i++) tmp[i]=i;
std::sort(tmp+1,tmp+n*2,cmp);
for(reg int i=0;i<2*n;i++) root[i]=&dizhi[tot++];
build(root[0],1,2*n-1);
for(reg int i=1;i<2*n;i++) insert(root[i-1],root[i],1,2*n-1,B.dfn[tmp[i]],tmp[i]<=n);
reg int s,t,L,R;
while(q--){
s=read()+1;t=read()+1;L=read()+1;R=read()+1;
//从 s 开始，能走 L 到 n，最小值不小于 L，用 B 树
//从 t 开始，能走 1 到 R，最大值不大于 R，用 A 树
//找交集
int tmpa=A.get_A(t,R),tmpb=B.get_B(s,L);
std::puts(find(root[A.dfn[tmpa]-1],root[A.dfn[tmpa]+A.size[tmpa]-1],1,2*n-1,B.dfn[tmpb],B.dfn[tmpb]+B.size[tmpb]-1)?"1":"0");
}
return 0;
}