快咕一个月了
咕咕咕 咕咕咕咕
LOJ #2865 Luogu P4899（离线）
UOJ #407（强制在线）
题意
给定一棵树和若干组询问$(S,E,L,R)$
表示你初始在$S$,想到达$E$,有一次变身机会,变身前经过的点的编号不得小于$L$,变身后不得大于$R$
判断每组询问是否可行
数据范围差不多都是$2·10^5$
题解
原问题等价于【从$ S$点出发不经过编号小于$ L$的点能到达的点集】和【从$ E$点出发不经过编号大于$ R$的点能到达的点集】是否有交
维护一棵最大克鲁斯卡尔重构树和一棵最小克鲁斯卡尔重构树
现在相当于每次询问两棵树上各一棵子树中是否编号集合有交
转化成二维数点问题
即每个点$ i$的坐标都是$(dfn_1[i],dfn_2[i])$
每次询问一个矩形中有没有点
离线可以树状数组扫描线水过
在线的话强上主席树即可
时间复杂度$ O(Q ·\log n)$
代码
这份是离线的
#include<ctime>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#define M 800010
#define rt register int
#define ll long long
using namespace std;
inline ll read(){
ll x=;char zf=;char ch=getchar();
while(ch!='-'&&!isdigit(ch))ch=getchar();
if(ch=='-')zf=-,ch=getchar();
while(isdigit(ch))x=x*+ch-'',ch=getchar();return x*zf;
}
void write(ll y){if(y<)putchar('-'),y=-y;if(y>)write(y/);putchar(y%+);}
void writeln(const ll y){write(y);putchar('\n');}
int k,m,n,x,y,z,ans,q;
struct ed{
int x,y;
}e[M];
bool cmp1(ed x,ed y){
return max(x.x,x.y)<max(y.x,y.y);
}
bool cmp2(ed x,ed y){
return min(x.x,x.y)>min(y.x,y.y);
}
struct tree{
int cnt,qwq;
int F[M],L[M],N[M],a[M],fa[M],ff[M],val[M],dfn[M],id[M],size[M],up[M][];
int ask(int x){return (x==fa[x])?x:(fa[x]=ask(fa[x]));}
void add(int x,int y){
a[++k]=y;
if(!F[x])F[x]=k;
else N[L[x]]=k;
L[x]=k;
}
int nomore(int x,int v){//包含x的经过边权不超过val的重构树上的点标号
for(rt i=;i>=;i--)if(val[up[x][i]]<=v&&up[x][i])x=up[x][i];
return x;
}
int noless(int x,int v){//包含x的经过边权不少于val的重构树上的点标号
for(rt i=;i>=;i--)if(val[up[x][i]]>=v&&up[x][i])x=up[x][i];
return x;
}
void init(){
for(rt i=;i<=cnt;i++)up[i][]=ff[i]; for(rt i=;i<=;i++)
for(rt j=;j<=cnt;j++)up[j][i]=up[up[j][i-]][i-];
}
void dfs(int x){
dfn[x]=++qwq;id[qwq]=x;size[x]=;
for(rt i=F[x];i;i=N[i]){
dfs(a[i]);
size[x]+=size[a[i]];
}
}
}S1,S2;//<=x和>=x
struct query{
int opt,pl,L,R,id;//opt:0点1,-1差分
bool operator <(const query s)const{
if(pl==s.pl)return (bool)opt<(bool)s.opt;
return pl<s.pl;
}
}a[M];
int anss[M],c[M];
void up(int x){
for(rt i=x;i<=n*;i+=i&-i)c[i]++;
}
int query(int x){
int ret=;
for(rt i=x;i;i&=i-)ret+=c[i];
return ret;
}
int main(){
n=read();m=read();q=read();
for(rt i=;i<m;i++){
x=read()+;y=read()+;
e[i]={x,y};
}
for(rt i=;i<=*n+;i++)S1.fa[i]=S2.fa[i]=S1.ff[i]=S2.ff[i]=i;
S1.cnt=S2.cnt=n;
sort(e,e+m,cmp1);
for(rt i=;i<m;i++){
int ls=S1.ask(e[i].x),rs=S1.ask(e[i].y);if(ls==rs)continue;
S1.cnt++;S1.fa[S1.cnt]=S1.cnt;
S1.fa[ls]=S1.fa[rs]=S1.ff[ls]=S1.ff[rs]=S1.cnt;S1.val[S1.cnt]=max(e[i].x,e[i].y);
S1.add(S1.cnt,ls);S1.add(S1.cnt,rs);
}
sort(e,e+m,cmp2);
for(rt i=;i<m;i++){
int ls=S2.ask(e[i].x),rs=S2.ask(e[i].y);if(ls==rs)continue;
S2.cnt++;S2.fa[S2.cnt]=S2.cnt;
S2.fa[ls]=S2.fa[rs]=S2.ff[ls]=S2.ff[rs]=S2.cnt;S2.val[S2.cnt]=min(e[i].x,e[i].y);
S2.add(S2.cnt,ls);S2.add(S2.cnt,rs);
}
S1.dfs(S1.cnt);S2.dfs(S2.cnt);S1.init();S2.init();
int t=;
for(rt i=;i<=n;i++)a[++t]={,S1.dfn[i],S2.dfn[i],,};
for(rt i=;i<q;i++){
int S=read()+,E=read()+,L=read()+,R=read()+;
int d2=S2.noless(S,L),d1=S1.nomore(E,R);
a[++t]={-,S1.dfn[d1]-,S2.dfn[d2],S2.dfn[d2]+S2.size[d2]-,i};
a[++t]={,S1.dfn[d1]+S1.size[d1]-,S2.dfn[d2],S2.dfn[d2]+S2.size[d2]-,i};
}
sort(a+,a+t+);
for(rt i=;i<=t;i++){
if(a[i].opt==)up(a[i].L);
else anss[a[i].id]+=a[i].opt*(query(a[i].R)-query(a[i].L-));
}
for(rt i=;i<q;i++)writeln((bool)anss[i]);
return ;
}