BZOJ4009:[HNOI2015]接水果
? 解题记录 ? ? BZOJ ? ? 整体二分 ? ? 树状数组 ? ? 树链剖分 ?    2019-01-05 11:01:15    658    0    0

【题目描述】

风见幽香非常喜欢玩一个叫做 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。 

一道经典的整体二分。

盘子能接到水果的条件是盘子是水果的子路径。

考虑一个盘子(u,v)可以接到哪些水果。

假设原树为有根树,那么有两种情况。(下文中LCA指最近公共祖先)

  1. lca(u,v)为u或v
  2. lca(u,v)不为u且不为v

对于第二种情况来说,相当于把水果的两个端点卡死在了u,v的子树内。

子树限制的问题就可以用dfs序。

为了方便我们规定一条路径用(x,y)表示,其中x的dfs序小于y。

这样相当于水果(x,y)种,x有一个取值范围,y有一个取值范围。

我们把盘子看成一个矩形,把水果看成一个点,那么被接到的条件等价于这个点落在矩形内。

问题就变成了对于每个点,求出覆盖它的权值第K大的矩形。

那么对于第一种情况怎么办呢?

现在已知(u,v)满足lca(u,v)=u (已经定义u的dfs序小于v)

设路径u->v上u之后的第一个点为t

我们发现只要满足一端在t的子树外,一端在v的子树内就可以了

为什么不是在u的子树外呢?画图可以发现,另一个端点在u的其它子树内其实也满足条件。

考虑我们规定了(u,v)的顺序,那么讨论一下u在t内还是v在t内就得到两个矩形。

这样落在其中任意一个就满足条件。

现在问题相当于对于每个点,求出覆盖它的权值第K大的图形(包括一个矩形、两个矩形)

这个就可以直接整体二分,二分一个权值,然后用扫描线加树状数组验证就行了。

整体二分写成扣除左边对右边的贡献比较好写。

居然1A了,真的高兴qwq

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 1e5 + 5;
struct edge {
	int v, next;
} e[maxn << 1];
int head[maxn], cnt;
void adde(const int &u, const int &v) {
	e[++cnt] = (edge) {v, head[u]};
	head[u] = cnt;
}

int dfn[maxn], dfned[maxn], dcnt, n, N, M, u, v, w;
int tp[maxn], fa[maxn], son[maxn], sz[maxn], dep[maxn];
void dfs(int u, int p) {
	sz[u] = 1, fa[u] = p;
	for(register int i = head[u]; i; i = e[i].next) {
		int v = e[i].v;
		if(v == p) continue;
		dfs(v, u);
		sz[u] += sz[v];
		if(!son[u] || sz[son[u]] < sz[v])
			son[u] = v;
	}
}

void dfs2(int u, int top) {
	dfn[u] = ++dcnt;
	tp[u] = top, dep[u] = dep[fa[u]] + 1;
	if(son[u]) dfs2(son[u], top);
	for(register int i = head[u]; i; i = e[i].next) {
		int v = e[i].v;
		if(v == fa[u] || v == son[u])
			continue;
		dfs2(v, v);
	}
	dfned[u] = dcnt;
}

int LCA(int u, int v) {
	while(tp[u] != tp[v]) {
		if(dep[tp[u]] < dep[tp[v]]) swap(u, v);
		u = fa[tp[u]]; 
	}
	return dep[u] > dep[v] ? v : u;
}

int Fdown(int p, int u) {
	while(tp[u] != tp[p]) {
		if(fa[tp[u]] == p) return tp[u];
		u = fa[tp[u]];
	}
	return son[p];
}

struct Fruit {int x, y, k, id;} frts[maxn], ftmp[maxn];
struct Rect {int l, r, d, u;};
struct Plate {
	int t, w; Rect r1, r2;
	bool operator < (const Plate &A) const {
		return w < A.w;
	}
} plts[maxn], ptmp[maxn];
struct Event {
	int x, d, u, t;
	bool operator < (const Event &A) const {
		return x < A.x;
	}
} ev[maxn << 1];
struct Query {
	int x, y, id;
	bool operator < (const Query &A) const {
		return x < A.x;
	}
} qs[maxn << 1];
int ans[maxn], tmp[maxn], ecnt, qcnt, ep;

namespace BIT {
	int t[maxn];
	#define lowbit(x) ((x) & (-(x)))
	void add(int x, int dt) {
		for(; x <= n; x += lowbit(x))
			t[x] += dt;
	}
	void add(int l, int r, int dt) {
		add(l, dt), add(r + 1, -dt);
	}
	int query(int x) {
		int ans = 0;
		for(; x; x -= lowbit(x))
			ans += t[x];
		return ans;
	}
}

void solve(int pl, int pr, int fl, int fr, int L, int R) {
	if(L >= R - 1) {
		for(register int i = fl; i < fr; ++i)
			ans[frts[i].id] = L;
		return ;
	}
	if(fl == fr || pl == pr) return;
	int mid = L + R >> 1;
	int tmp, p1 = fl, p2 = fr - 1, p3 = pl, p4 = pr - 1;
	ecnt = qcnt = 0, ep = 1;
	for(register int i = fl; i < fr; ++i) {
		qs[++qcnt] = (Query) {frts[i].x, frts[i].y, i};
	}
	for(register int i = pl; i < pr; ++i) {
		if(plts[i].w < mid) {
			ptmp[p3++] = plts[i];
			ev[++ecnt] = (Event) {plts[i].r1.l, plts[i].r1.d, plts[i].r1.u, 1};
			ev[++ecnt] = (Event) {plts[i].r1.r + 1, plts[i].r1.d, plts[i].r1.u, -1};
			if(plts[i].t > 1) {
				ev[++ecnt] = (Event) {plts[i].r2.l, plts[i].r2.d, plts[i].r2.u, 1};
				ev[++ecnt] = (Event) {plts[i].r2.r + 1, plts[i].r2.d, plts[i].r2.u, -1};
			}
		} else {
			ptmp[p4--] = plts[i];
		}
	}
	sort(ev + 1, ev + ecnt + 1);
	sort(qs + 1, qs + qcnt + 1);
	for(register int i = 1; i <= qcnt; ++i) {
		while(ep <= ecnt && ev[ep].x <= qs[i].x)
			BIT::add(ev[ep].d, ev[ep].u, ev[ep].t), ++ep;
		tmp = BIT::query(qs[i].y);
		if(tmp < frts[qs[i].id].k) 
			frts[qs[i].id].k -= tmp, ftmp[p2--] = frts[qs[i].id];
		else ftmp[p1++] = frts[qs[i].id];
	}
	for(register int i = fl; i < fr; ++i)
		frts[i] = ftmp[i];
	for(register int i = pl; i < pr; ++i)
		plts[i] = ptmp[i];
	while(ep <= ecnt) BIT::add(ev[ep].d, ev[ep].u, ev[ep].t), ++ep;
	solve(pl, p3, fl, p1, L, mid);
	solve(p3, pr, p1, fr, mid, R);
}

int main() {
	scanf("%d%d%d", &n, &N, &M);
	for(register int i = 1; i < n; ++i) {
		scanf("%d%d", &u, &v);
		adde(u, v), adde(v, u);
	} 
	dfs(1, 0), dfs2(1, 1);
	int lca;
	for(register int i = 1; i <= N; ++i) {
		scanf("%d%d%d", &u, &v, &w);
		lca = LCA(u, v);
		if(dfn[u] > dfn[v]) swap(u, v);
		if(lca == u) {
			lca = Fdown(u, v);
			if(dfned[lca] == n) {
				plts[i] = (Plate) {1, w, 
					(Rect) {1, dfn[lca] - 1, dfn[v], dfned[v]}, 
					0, 0, 0, 0};
			} else {
				plts[i] = (Plate) {2, w, 
						(Rect) {1, dfn[lca] - 1, dfn[v], dfned[v]}, 
						(Rect) {dfn[v], dfned[v], dfned[lca] + 1, n}};
			}
		} else {
			plts[i] = (Plate) {1, w, 
					(Rect) {dfn[u], dfned[u], dfn[v], dfned[v]}, 
					0, 0, 0, 0};
		}
	}
	for(register int i = 1; i <= M; ++i) {
		scanf("%d%d%d", &u, &v, &w);
		if(dfn[u] > dfn[v]) swap(u, v);
		frts[i] = (Fruit) {dfn[u], dfn[v], w, i};
	}
	sort(plts + 1, plts + N + 1);
	solve(1, N + 1, 1, M + 1, 0, 1e9 + 1);
	for(register int i = 1; i <= M; ++i)
		printf("%d\n", ans[i]); 
	return 0;
}

上一篇: BZOJ5091: [Lydsy1711月赛]摘苹果

下一篇: BZOJ4530:[Bjoi2014]大融合

658 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航