CF1899 G. Unusual Entertainment [二维数点/二维偏序]

传送门:CF

[前题提要]:没什么好说的,区域赛爆炸之后发愤加训思维题.秒了div3 A~F的脑筋急转弯,然后被G卡了,树剖dfs序的想法已经想到了,题目也已经化简为两个线段是否存在一个合法位置了.但是MD不会二维数点,用一个树剖+扫描线搞来搞去最后还是Tle.果然如下图所说:科技还是十分重要的.

---

首先读完题意.不难想到本题应该是一道数据结构题.因为对于$x$的儿子节点我们是可以直接使用$dfs$序或者树链剖分直接维护出来编号的.所以对于我们的每一个询问,相当于求出区间$[l,r]$是否存在一个点,它的$dfs$序在x的子孙节点中.

设我们维护出来的$x$的子孙节点(包括他自己)区间为$[L_x,R_x]$(这里需要提一句的是对于一个节点的所有儿子来说,它的$dfs$序一定是连续的,具体证明此处略).设一个点$u$的$dfs$,为$dfn(u)$.那么现在这道题就是问是否存在一个点在序列中的位置为$k\in [l,r]$,然后$dfn(k)\in [L_x,R_x]$.

额.当时我就卡在了这个维护上.但其实这是一个很模板的二维偏序(二维数点)问题.模板题指路
我们将$x\in [l,r]$看成横坐标,将所有$dfn(x)$看成纵坐标.那么就是问你是否存在一个点$(x,dfn(x))$在一个矩形区域内.这是一个很典型的二维数点问题.考虑将所有的询问矩形区域使用二维前缀和的思想进行化解,然后离线下来一个一个枚举,在枚举的过程中,将所有的点逐个加入到我们的树状数组中.只要保证所有点的横坐标小于当前询问区域,我们就可以将二维询问问题转化为一维询问,只要用树状数组维护一下就行了.

---

下面是具体的代码部分:

#include 
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
inline void print(__int128 x){
	if(x<0) {putchar('-');x=-x;}
	if(x>9) print(x/10);
	putchar(x%10+'0');
}
#define maxn 200010
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
inline int lowbit(int x) {
	return x&(~x+1);
}
int tree[maxn];int n,q;
void Add(int pos,int val) {
	while(pos<=n) {
		tree[pos]+=val;
		pos+=lowbit(pos);
	}
}
int Query(int pos) {
	int ans=0;
	while(pos) {
		ans+=tree[pos];
		pos-=lowbit(pos);
	}
	return ans;
}
vector<int>edge[maxn];
int in[maxn],out[maxn];int tot=0;
void dfs(int u,int per_u) {
	in[u]=++tot;
	for(auto v:edge[u]) {
		if(v==per_u) continue;
		dfs(v,u);
	}
	out[u]=tot;
}
int Ans[maxn];int p[maxn];
int main() {
	int T=read();
	while(T--) {
		n=read();q=read();
		for(int i=1;i<n;i++) {
			int u=read();int v=read();
			edge[u].push_back(v);
			edge[v].push_back(u);
		}
		dfs(1,0);
		for(int i=1;i<=n;i++) {
			p[i]=read();p[i]=in[p[i]];
		}
		vector<tuple<int,int,int,int> >Q;
		for(int i=1;i<=q;i++) {
			int l=read();int r=read();int x=read();
			Q.push_back({l-1,in[x]-1,i,1});
			Q.push_back({l-1,out[x],i,-1});
			Q.push_back({r,in[x]-1,i,-1});
			Q.push_back({r,out[x],i,1});
		}
		sort(Q.begin(),Q.end());
		int cur=0;
		for(auto [a,b,id,val]:Q) {
			while(cur+1<=a) {
				cur++;
				Add(p[cur],1);
			}
			Ans[id]+=val*Query(b);
		}
		for(int i=1;i<=q;i++) {
			cout<<(Ans[i]>0?"YES":"NO")<<endl;
		}
		tot=0;
		for(int i=1;i<=n;i++) {
			tree[i]=0;
			edge[i].clear();in[i]=out[i]=0;
		}
		for(int i=1;i<=q;i++) {
			Ans[i]=0;
		}
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96