P4899 [IOI2018] werewolf 狼人

题意

你是一个狼人。每次询问给出起点和终点，表示你要从城市 \(S\) 走到城市 \(E\)。不幸的是，你一开始是个人，最后是只狼，并且在作为人的时候，你不能进入编号为 \(0\sim L_i-1\) 的城市；同样在作为狼的时候，你不能进入编号为 \(R_i+1\sim n-1\) 的城市。如果你可以自由选择在路径上任意时刻实现恰好一次变身，求能否到达终点。

Solution

如果我是一个人，那么我肯定挑编号大的城市走，于是我建出一棵关于点的 Kruskal 重构树，使得深度越小的点编号越小。这样我们只要求两个点的 LCA 就行了。

如果我是一只狼，同理。

但我是一个狼人。所以我需要作为一个人，从 \(S\) 到达 \(L\sim R\)，然后作为一只狼，从 \(L\sim R\) 到达 \(E\)。所以对于 \(S,E\)，可以在各自的生成树上跳到深度最小的祖先，这可以倍增，然后考虑二者子树中的点集是否有交。

点集可以用 \(dfn\) 序的区间来表示。所以现在问题转化成：给你两个排列，每次询问给出两个区间，求两个排列分别对应两个区间中的数有没有交。

还是死在 DS 啊。就是考虑把这两个 \(p_x,p_y\) 垂直放置形成一个坐标系，然后我们在满足 \(p_x[i]=p_y[j]\) 位置 \((i,j)\) 点一个点，那么问题就转化成矩阵数点，直接扫描线+树状数组就可以了。

Code

// Problem: 
//     P4899 [IOI2018] werewolf 狼人
//   
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4899
// Memory Limit: 500 MB
// Time Limit: 4000 ms

#include<bits/stdc++.h>
#define ll long long
#define inf (1<<30)
#define INF (1ll<<60)
#define pb emplace_back
#define pii pair<int,int>
#define mkp make_pair
#define fi first
#define se second
#define all(a) a.begin(),a.end()
#define siz(a) (int)a.size()
#define clr(a) memset(a,0,sizeof(a))
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define pt(a) cerr<<#a<<'='<<a<<' '
#define pts(a) cerr<<#a<<'='<<a<<'\n'
// #define int long long
using namespace std;
const int MAXN=2e5+10;
int n;
struct BIT{
	int tr[MAXN];
	void init(){memset(tr,0,sizeof(tr));}
	int lbt(int x){return x&(-x);}
	void upd(int x,int v){for(;x<=n;x+=lbt(x))tr[x]+=v;}
	int ask(int x){int ret=0;for(;x;x-=lbt(x))ret+=tr[x];return ret;}
	int qr(int l,int r){return ask(r)-ask(l-1);}
}T;
struct Kruskal{
	int f[MAXN];
	int find(int x){while(x^f[x])x=f[x]=f[f[x]];return x;}
	bool merge(int x,int y){
		if(find(x)==find(y)) return 0;
		f[find(x)]=find(y);return 1;
	}int p[MAXN],Man=0,vis[MAXN];
	vector<int> g[MAXN],e[MAXN];
	void add(int u,int v){g[u].pb(v);g[v].pb(u);}
	int dfn[MAXN],rk[MAXN],tot=0,siz[MAXN],fa[MAXN][20];
	void dfs(int x){
		dfn[x]=++tot;rk[tot]=x;siz[x]=1;
		for(int s:e[x]){
			fa[s][0]=x;
			rep(i,1,19) fa[s][i]=fa[fa[s][i-1]][i-1];
			dfs(s),siz[x]+=siz[s];
		}
	}
	void init(){
		iota(f+1,f+1+n,1);
		iota(p+1,p+1+n,1);
		if(Man) reverse(p+1,p+1+n);
		rep(i,1,n){
			for(int s:g[p[i]]){
				if(vis[s]){
					int sf=find(s);
					if(merge(sf,p[i]))
						e[p[i]].pb(sf);
				}
			}vis[p[i]]=1;
		}
		dfs(p[n]);
	}
	pii gt(int S,int lmt){
		per(i,19,0){
			if(Man&&fa[S][i]>=lmt&&fa[S][i]) S=fa[S][i];
			if(!Man&&fa[S][i]<=lmt&&fa[S][i]) S=fa[S][i];
		}return mkp(dfn[S],dfn[S]+siz[S]-1);
	}
}Man,Wlf;
struct query{int wl,wr,id,op;};
vector<query> qs[MAXN];
int ans[MAXN];
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int m,Q;cin>>n>>m>>Q;
	rep(i,1,m){
		int x,y;cin>>x>>y;
		x++,y++;
		Man.add(x,y);
		Wlf.add(x,y);
	}Man.Man=1;Wlf.Man=0;
	Man.init();Wlf.init();
	rep(i,1,Q){
		int s,e,l,r;cin>>s>>e>>l>>r;
		s++;e++;l++;r++;
		pii Mn=Man.gt(s,l),Wf=Wlf.gt(e,r);
		qs[Mn.fi-1].pb(query{Wf.fi,Wf.se,i,-1});
		qs[Mn.se].pb(query{Wf.fi,Wf.se,i,1});
	}
	T.init();
	rep(i,1,n){
		T.upd(Wlf.dfn[Man.rk[i]],1);
		for(auto q:qs[i])
			ans[q.id]+=q.op*T.qr(q.wl,q.wr);
	}
	rep(i,1,Q)
		if(ans[i]>0) cout<<1<<'\n';
		else cout<<0<<'\n';
	return 0;
}

原文地址：http://www.cnblogs.com/ZCETHAN/p/16855972.html