HNOI 2015 接水果（整体二分+DFS序+树状数组）

发表于 |
字数统计: 2,266字 | 阅读时长 ≈ 11min

[HNOI2015]接水果

问题描述

风见幽香非常喜欢玩一个叫做 osu!的游戏，其中她最喜欢玩的模式就是接水果。由于她已经DT FC 了The big black, 她觉得这个游戏太简单了，于是发明了一个更加难的版本。首先有一个地图，是一棵由 n 个顶点、n-1 条边组成的树（例如图 1给出的树包含 8 个顶点、7 条边）。这颗树上有 P 个盘子，每个盘子实际上是一条路径（例如图 1 中顶点 6 到顶点 8 的路径），并且每个盘子还有一个权值。第 i 个盘子就是顶点$a_i$到顶点$b_i$的路径(由于是树，所以从$a_i$到$b_i$的路径是唯一的)，权值为$c_i$。接下来依次会有Q个水果掉下来，每个水果本质上也是一条路径，第i 个水果是从顶点 $u_i$ 到顶点$v_i $的路径。幽香每次需要选择一个盘子去接当前的水果：一个盘子能接住一个水果，当且仅当盘子的路径是水果的路径的子路径（例如图1中从 3到7 的路径是从1到8的路径的子路径）。这里规定:从a 到b的路径与从b到 a的路径是同一条路径。当然为了提高难度，对于第 i 个水果，你需要选择能接住它的所有盘子中，权值第 $k_i$ 小的那个盘子，每个盘子可重复使用（没有使用次数的上限：一个盘子接完一个水果后，后面还可继续接其他水果，只要它是水果路径的子路径）。幽香认为这个游戏很难，你能轻松解决给她看吗？

输入格式

第一行三个数 n和P 和Q，表示树的大小和盘子的个数和水果的个数。

接下来n-1 行，每行两个数 a、b，表示树上的a和b 之间有一条边。树中顶点按1到 n标号。 接下来 P 行，每行三个数 a、b、c，表示路径为 a 到 b、权值为 c 的盘子，其中$0≤c≤10^9$，a不等于b。

接下来Q行，每行三个数 u、v、k，表示路径为 u到 v的水果，其中 u不等于v，你需要选择第 k小的盘子，第k 小一定存在。

输出格式

对于每个果子，输出一行表示选择的盘子的权值。

样例输入

10 10 10

1 2

2 3

3 4

4 5

5 6

6 7

7 8

8 9

9 10

3 2 217394434

10 7 13022269

6 7 283254485

6 8 333042360

4 6 442139372

8 3 225045590

10 4 922205209

10 8 808296330

9 2 486331361

4 9 551176338

1 8 5

3 8 3

3 8 4

1 8 3

4 8 1

2 3 1

2 3 1

2 3 1

2 4 1

1 4 1

样例输出

442139372

333042360

442139372

283254485

283254485

217394434

217394434

217394434

217394434

217394434

提示

对于所有数据，N,P,Q≤40000

本题要求一条路径的子路径中权值第K小的路径，首先考虑如何判定子路径，容易看出如果一条路径的点集是${p_1,p_2…p_n}$那么，他的一条子路径的两端点都在这个集合中，那么可以将一条子路径$x\rightarrow y$，抽象成一个点$(x,y)$，但是这些点是离散的，因此不好处理，可以利用轻重链剖分，这样的话$DFS$序最多有$\log n$个连续区间，就可以将一条路径的子路径范围抽象成$\log^2$个矩形，这样就只需要求若干矩形中权值第$k$小的点了。

但这样显然不优秀，我们考虑换一个方向，考虑一条路径的父路径，沿用刚才的思路，我们发现问题变得异常简单，因为我们考虑一条路径$x\rightarrow y$，如果$LCA(x,y)\neq x\&\& LCA(x,y)\neq y$，那么它的一条父路径的两个端点必然是$x$和$y$的子树中的两个点，而且由于子树的DFS序是连续的，因此我们就可以将这样的路径抽象成一个矩形，而对于另一种情况，显然一条父路径必然是一个点在子树中，另一个点不在子树中，这就可以抽象成两个矩形。

因此我们可以将盘子看成矩形，将水果看成点，那么问题变成了求二维平面中覆盖一个点的所有矩形中，权值第K小的矩形。这个问题可以用扫描线+线段树套主席树来解决，但他非常的麻烦。

但是求区间第K小问题也是整体二分的经典模型，因此我们考虑扫描线+整体二分+树状数组，二分一个权值，然后将所有权值小于等于$mid$的矩形取出来做扫描线，求一下每个点被覆盖的次数，次数小于$k$的甩到$[mid+1,r]$中去，大于等于$k$的甩到$[l,mid]$中去，这个只需要一个树状差分数组来处理就行了。

复杂度$O(n\log^2 n)$

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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#define N 40005
using namespace std;
char buf[1<<20],*p1,*p2;
#define GC (p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?0:*p1++)
inline void _R(int &x)
{
	char t=GC;
	while(t<48||t>57)t=GC;
	for(x=0;t>47&&t<58;t=GC)x=(x<<3)+(x<<1)+t-48;
}
struct nodd{int x[2],y[2],v;};
struct node{int x,y,k,id;};
struct thh{int pos,l,r,v;};
bool operator<(thh a,thh b)
{return a.pos<b.pos;}
int n,p,q,In[N],Out[N],VT,dep[N],Ans[N],S=17;
int fa[N][20],cnt[N],C[N];
int TOT,LA[N],NE[N<<1],EN[N<<1];
void MD(int x,int d)
{for(int i=x;i<=n;i+=(i&-i))C[i]+=d;}
int GS(int x)
{
	int i,sum=0;
	for(i=x;i;i-=(i&-i))sum+=C[i];
	return sum;
}
void ADD(int x,int y)
{
	TOT++;
	EN[TOT]=y;
	NE[TOT]=LA[x];
	LA[x]=TOT;
}
void DFS(int x,int f)
{
	int i,y;
	dep[x]=dep[f]+1;
	In[x]=++VT;
	fa[x][0]=f;
	for(i=1;i<=S;i++)fa[x][i]=fa[fa[x][i-1]][i-1];
	for(i=LA[x];i;i=NE[i])
	{
		y=EN[i];if(y==f)continue;
		DFS(y,x);
	}
	Out[x]=VT;
}
int LCA(int x,int y)
{
	if(dep[x]<dep[y])swap(x,y);
	int i,t=dep[x]-dep[y];
	for(i=0;i<=S;i++)
	if(t>>i&1)x=fa[x][i];
	if(x==y)return x;
	for(i=S;i>=0;i--)
	if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
	return fa[x][0];
}
int Find(int x,int y)
{
	if(dep[x]<dep[y])swap(x,y);
	int i,t=dep[x]-dep[y]-1;
	for(i=0;i<=S;i++)
	if(t>>i&1)x=fa[x][i];
	return x;
}
void DC(int l,int r,vector<nodd>P,vector<node>Q)
{
	if(!Q.size())return;
	int i,j,k,x,y,mid=l+r>>1;
	if(l==r)
	{
		for(i=0;i<Q.size();i++)Ans[Q[i].id]=l;
		return;
	}
	vector<nodd>P1,P2;
	vector<node>Q1,Q2;
	vector<thh>T1,T2;
	for(i=0;i<P.size();i++)
	{
		if(P[i].v<=mid)
		{
			T1.push_back((thh){P[i].x[0],P[i].y[0],P[i].y[1],1});
			T1.push_back((thh){P[i].x[1]+1,P[i].y[0],P[i].y[1],-1});
			P1.push_back(P[i]);
		}
		else P2.push_back(P[i]);
	}
	for(i=0;i<Q.size();i++)
	{
		cnt[Q[i].id]=0;
		T2.push_back((thh){Q[i].x,Q[i].y,0,Q[i].id});
		T2.push_back((thh){Q[i].y,Q[i].x,0,Q[i].id});
	}
	sort(T1.begin(),T1.end());
	sort(T2.begin(),T2.end());
	for(i=j=0;i<T2.size();i++)
	{
		while(j<T1.size()&&T1[j].pos<=T2[i].pos)
		{
			MD(T1[j].l,T1[j].v);
			MD(T1[j].r+1,-T1[j].v);
			j++;
		}
		cnt[T2[i].v]+=GS(T2[i].l);
	}
	while(j<T1.size())
	{
		MD(T1[j].l,T1[j].v);
		MD(T1[j].r+1,-T1[j].v);
		j++;
	}
	for(i=0;i<Q.size();i++)
	{
		if(cnt[Q[i].id]>=Q[i].k)Q1.push_back(Q[i]);
		else Q[i].k-=cnt[Q[i].id],Q2.push_back(Q[i]);
	}
	DC(l,mid,P1,Q1);DC(mid+1,r,P2,Q2);
}
int main_main()
{
	vector<nodd>P;
	vector<node>Q;
	int i,j,k,x,y,z;
	_R(n);_R(p);_R(q);
	for(i=1;i<n;i++)
	{
		_R(x);_R(y);
		ADD(x,y);ADD(y,x);
	}
	DFS(1,0);
	for(i=1;i<=p;i++)
	{
		_R(x);_R(y);_R(z);
		if(dep[x]<dep[y])swap(x,y);
		int lca=LCA(x,y);
		if(lca!=y)P.push_back((nodd){{In[x],Out[x]},{In[y],Out[y]},z});
		else
		{
			k=Find(x,y);
			P.push_back((nodd){{In[x],Out[x]},{1,In[k]-1},z});
			if(Out[k]<n)P.push_back((nodd){{In[x],Out[x]},{Out[k]+1,n},z});
		}
	}
	for(i=1;i<=q;i++)
	{
		_R(x);_R(y);_R(z);
		Q.push_back((node){In[x],In[y],z,i});
	}
	DC(0,1e9,P,Q);
	for(i=1;i<=q;i++)printf("%d\n",Ans[i]);
}
const int main_stack=16;    
char my_stack[128<<20];    
int main() {    
  __asm__("movl %%esp, (%%eax);\n"::"a"(my_stack):"memory");    
  __asm__("movl %%eax, %%esp;\n"::"a"(my_stack+sizeof(my_stack)-main_stack):"%esp");    
  main_main();    
  __asm__("movl (%%eax), %%esp;\n"::"a"(my_stack):"%esp");    
  return 0;    
}