夏晓光(loveJY)的博客

仍要向下扎根,向上结果

首页 归档 标签 关于 友链

P3242 [HNOI2015]接水果

2020-08-24 15 min read # 平面转换 # 扫描线 # 整体二分 # 线段树

预处理部分:

考虑怎么判断一条路径是否被另一条覆盖

设要被包含的路径是(u,v),而去包含的是(x,y)

对于LCA(u,v)==u的,

(x,y)中至少有一个在v子树里面

钦定x在v的子树里,那么dfnv<=dfnx<=dfnv+siz[v]dfn_v<=dfn_x<=dfn_v+siz[v]

而且钦定g为uv方向的儿子,就是y向v走一步走到的节点dfng+siz[g]<=dfny<=ndfn_g+siz[g]<=dfn_y<=n或1<=dfny<dfng1<=dfn_y<dfn_g也就是说在除了g子树外任意一点都可以!

会发现这6个上下界和(x,y)没有关系

这相当于四维限制,只能转换到平面上,就是(dfnx,dfny)(dfn_x,dfn_y)要在(dfnv,dfng+siz[g])(dfn_v,dfn_g+siz[g])为左下角,(dfnv+siz[v],n)(dfn_v+siz[v],n)为右上角的矩形或者(dfnv,1)(dfn_v,1)为左下角(dfnv+siz[v],dfng−1)(dfn_v+siz[v],dfn_g-1)为右上角的矩形里面(这样你会发现x,y坐标都满足了限制)

也就是说,我们如果搞两个矩形加,那么(x,y)包含的路径数查询就是单点查询了!

但是还没完,我们再看看另一类路径

lca(u,v)!=(u∣∣v)lca(u,v)!=(u||v)

那么我们有(x,y)包括(u,v)的话....

dfnv<=dfnx<=dfnv+siz[v]dfn_v<=dfn_x<=dfn_v+siz[v]即x在v的子树里!

dfnu<=dfny<=dfnu+siz[u]dfn_u<=dfn_y<=dfn_u+siz[u]即x在u的子树里!

这个矩阵加的信息也和(x,y)(x,y)是什么没有关系,所以可以处理!

(dfnv,dfnu)(dfn_v,dfn_u)为左下角,(dfnv+siz[v],dfnu+siz[u])(dfn_v+siz[v],dfn_u+siz[u])为右上角的矩形

这样我们可以搞到一个二维平面上,但是问题是第k大怎么处理...QAQ

搞事情部分:

既然我们只能很快的查出有多少个,不妨把第k大用个二分去解决

  1. 二分一个答案,对于一个询问,把所有大于二分值的盘子加入平面

  2. 查询水果点上有多少个数,如果多了就调大二分值,否则调小二分值

但是这样也太太太慢了

整体二分!

所有水果我们一起二分一个答案,把大于这个值的盘子加入平面

然后所有都查询一遍O(mlogm)O(mlogm)

之后我们把数量小于k的(说明要调小)放入左边区间递归,同时把盘子中小于k的放入左边,然后把数量大于k的放入右边区间递归,同时把盘子中大于k的放入右边

最后一步!如何实现矩阵+单点求和?

扫描线好题/se

可以考虑用扫描线,把所有的矩形和询问点都加入分界点中,然后遇到修改在线段树上改,遇到查询就查一下

这样复杂度就会O(nlogn)了

总复杂度我们不难得出

O((m+n)lognlogV)O((m+n)lognlogV)

4e4的范围应该能过了....

后记:

写代码的时候注意线段树清空,以及第一步建边的时候拆询问,可能导致一些在几千组询问的时候WA掉的锅

还有整体二分的时候同时分盘子和水果....不过相对坑较小

附带7.33kb未删除调试code:

//你知道真正的写吐了吗....
//整体分毒
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 7;
int n, p, q, V;
struct rec {
	int x, y, z, w, id;
	bool operator<(const rec &x) const {
		return z < x.z;
	}
} b[MAXN], a[MAXN], mdf[MAXN], qry[MAXN], C[MAXN], D[MAXN], A[MAXN], B[MAXN];
int ccnt, home[MAXN], nxt[MAXN], to[MAXN], dep[MAXN];
inline void ct(int x, int y) {
	ccnt++;
	nxt[ccnt] = home[x];
	home[x] = ccnt;
	to[ccnt] = y;
}

int depp, siz[MAXN], dfn[MAXN], son[MAXN], fa[MAXN];
inline void dfs(int u, int F) {
	siz[u] = 1;
	for(int i = home[u]; i; i = nxt[i]) {
		int v = to[i];
		if(v == F)continue;
		fa[v] = u;
		dep[v] = dep[u] + 1;
		dfs(v, u);
		siz[u] += siz[v];
		if(siz[v] > siz[son[u]])son[u] = v;
	}
	return ;
}
int top[MAXN];
inline void dfs2(int u, int topf) {
	top[u] = topf;
	dfn[u] = ++depp;
	if(!son[u])return ;
	dfs2(son[u], topf);
	for(int i = home[u]; i; i = nxt[i]) {
		int v = to[i];
		if(v == fa[u] || v == son[u])continue;
		dfs2(v, v);
	}
	return ;
}

inline int LCA(int x, int y) {
	while(top[x] != top[y]) {
		if(dep[top[x]] < dep[top[y]])x ^= y ^= x ^= y;
		x = fa[top[x]];
	}
	if(dep[x] > dep[y])x ^= y ^= x ^= y;
	return x;
}

inline int getG(int x, int y) {//y到x第一个点
	if(x == y)return x;
	while(top[x] != top[y]) {
		if(dep[top[x]] < dep[top[y]])x ^= y ^= x ^= y;
		if(fa[top[x]] == y) {
			// printf("G:%d %d? %d\n", x, top[x], y);
			return top[x];//不在一个重链
		}
		x = fa[top[x]];
	}
	if(dep[x] > dep[y])x ^= y ^= x ^= y;
	return son[x];//如果正好在一个重链
}


inline void init() {
	int rc = p;
	for(int i = 1; i <= rc; ++i) {
		int u = b[i].x;
		int v = b[i].y;
		if(dep[u] > dep[v])u ^= v ^= u ^= v;
		int anc = LCA(u, v);
		// printf("%d?/cy\n", i);
		if(anc == u) {//first
			// printf("u,v,anc is %d %d %d?\n", u, v, anc);
			int g = getG(v, anc);
			int nxt = i;
			if(dfn[g] + siz[g] <= n) {
				nxt = p + 1;
				mdf[i].x = dfn[v];
				mdf[i].y = dfn[g] + siz[g];
				mdf[i].w = dfn[v] + siz[v] - 1;
				mdf[i].id = n;
			}
			// printf("%d?\n", nxt);
			if(1 <= dfn[g] - 1) {//好像没用
				if(nxt == p + 1)
					++p;
				mdf[nxt].x = 1;
				mdf[nxt].y = dfn[v];
				mdf[nxt].w = dfn[g] - 1;
				mdf[nxt].id = dfn[v] + siz[v] - 1;
				mdf[nxt].z = b[i].z;
			}
			// printf("%d %d???\n", nxt, p);
			// printf("g is :%d ,(%d,%d)and (%d,%d) bing! (%d,%d)and (%d,%d)\n", g, mdf[i].x, mdf[i].y, mdf[i].w, mdf[i].id, mdf[nxt].x, mdf[nxt].y, mdf[nxt].w, mdf[nxt].id);
		} else {
			if(dfn[u] < dfn[v])swap(u, v);
			mdf[i].x = dfn[v];
			mdf[i].y = dfn[u];
			mdf[i].w = dfn[v] + siz[v] - 1;
			mdf[i].id = dfn[u] + siz[u] - 1;
			// printf("u:%d v:%d (%d,%d)and (%d,%d) \n", u, v, mdf[i].x, mdf[i].y, mdf[i].w, mdf[i].id);
		}
		mdf[i].z = b[i].z;
	}
	// for(int i = 1; i <= p; ++i) {
	// 	printf("%d %d %d %d %d\n", mdf[i].x, mdf[i].y, mdf[i].w, mdf[i].id, mdf[i].z);
	// }
	for(int i = 1; i <= q; ++i) {
		int u = a[i].x;
		int v = a[i].y;
		// printf("%d %dqwerty\n", dfn[u], dfn[v]);
		qry[i].x = dfn[u];
		qry[i].y = dfn[v];
		qry[i].id = a[i].id;
		qry[i].z = a[i].z;
	}
	// puts("It's OK!");
	return;
}

namespace seg {
	int ls[MAXN], rs[MAXN], T, sum[MAXN], tag[MAXN], root;
	inline void pushdown(int k) {
		if(!tag[k])return ;
		if(!ls[k]) {
			ls[k] = ++T;
			ls[T] = 0;
			rs[T] = 0;
			sum[T] = 0;
			tag[T] = 0;
		}
		if(!rs[k]) {
			rs[k] = ++T;
			ls[T] = 0;
			rs[T] = 0;
			sum[T] = 0;
			tag[T] = 0;
		}
		tag[ls[k]] += tag[k];
		sum[ls[k]] += tag[k];
		tag[rs[k]] += tag[k];
		sum[rs[k]] += tag[k];
		tag[k] = 0;
	}
	inline void modify(int &k, int l, int r, int x, int y, int V) {
		if(!k) {
			k = ++T;
			ls[k] = 0;
			rs[k] = 0;
			sum[k] = 0;
			tag[k] = 0;
		}
		// printf("%d?\n", tag[k]);
		if(x <= l && y >= r) {
			// printf("%d?%d %d %d\n", l, r, x, y);
			tag[k] += V;
			sum[k] += V; //非叶节点的这个没用
			// printf("%d?\n", sum[k]);
			return ;
		}
		pushdown(k);
		int mid = (l + r) >> 1;
		if(x <= mid)modify(ls[k], l, mid, x, y, V);
		if(y > mid)modify(rs[k], mid + 1, r, x, y, V);
	}
	inline int query(int k, int l, int r, int pos) {
		if(!k)return 0;
		// printf("%d %d %d\n", k, sum[k], tag[k]);
		if(l == r) {
			// printf("%d %d %d %d\n", l, r, k, sum[k]);
			return sum[k];
		}
		pushdown(k);
		int mid = (l + r) >> 1;
		if(pos <= mid)return query(ls[k], l, mid, pos);
		else return query(rs[k], mid + 1, r, pos);
	}
}
using namespace seg;
int ans[MAXN];

struct SEG {
	int x, L, R;
	bool operator<(const SEG &y) {
		return x == y.x ? L > y.L : x < y.x;
	}
} que[MAXN];

bool cmp(const int &x, const int &y) {
	return mdf[x].z < mdf[y].z;
}
//l1,r1 is mdf
//l2,r2 is ask
inline void fz(int L, int R, int l1, int r1, int l2, int r2) {
	if(L == R) {
		for(int i = l2; i <= r2; ++i) {
			ans[qry[i].id] = L;
		}
		return ;
	}
	if(L > R)return ;
	int mid = (L + R) >> 1;
	// printf("qwq in?%d %d %d %d %d %d %d\n", L, mid, R, l1, r1, l2, r2);
	assert(R >= L);
	int T1 = 0, T2 = 0;
	for(int i = l1; i <= r1; ++i) {
		// printf("%d?%d\n", mdf[i].x, mdf[i].y);
		if(mdf[i].z <= mid) {
			B[++T1] = mdf[i];
		} else {
			A[++T2] = mdf[i];
		}
	}
	int T3 = 0;
	for(int i = 1; i <= T1; ++i) {
		que[++T3].x = B[i].x;
		que[T3].L = B[i].y;
		que[T3].R = B[i].id;
		que[++T3].x = B[i].w + 1;
		que[T3].L = B[i].y;
		que[T3].R = -B[i].id;//del
	}
	//B is < mid;
	for(int i = l2; i <= r2; ++i) {
		que[++T3].x = qry[i].x;
		que[T3].L = -i;
		que[T3].R = qry[i].y;
		// printf("%d???%d\n", qry[i].y, qry[i].x);
	}
	sort(que + 1, que + T3 + 1);
	// for(int i = 1; i <= T3; ++i)if(que[i].L <= 0)printf("%d %d\n", que[i].x, que[i].L);
	// printf("??%d?\n", T3);
	root = T = 0;
	int tot1 = 0, tot2 = 0;
	for(int i = 1; i <= T3; ++i) {
		assert(que[i].L != 0);
		// printf("%d?->\n", que[i].x);
		if(que[i].R < 0) {
			que[i].R = -que[i].R;
			// printf("???what?:%d %d %d\n", que[i].x, que[i].L, que[i].R);
			modify(root, 1, n, que[i].L, que[i].R, -1);
		} else if(que[i].L < 0) {
			que[i].L = -que[i].L;
			int P = que[i].L;
			int tmp = query(root, 1, n, que[i].R);
			// printf("Yes I am :%d?%d %d %d?%d\n", tmp, qry[P].id, qry[P].z, que[i].x, que[i].R);
			if(tmp < qry[P].z) {
				// printf("I am a poor boy");
				C[++tot1] = qry[P];
				C[tot1].z -= tmp;
			} else {
				D[++tot2] = qry[P];//decrease
				ans[qry[P].id] = mid;
			}
		} else {
			// printf("%d %d\n", que[i].L, que[i].R);
			modify(root, 1, n, que[i].L, que[i].R, 1);
		}
	}
	for(int i = 0; i < tot2; ++i) {
		qry[i + l2] = D[i + 1];
	}//C is who need less
	for(int i = 1; i <= tot1; ++i) {
		qry[i + l2 + tot2 - 1] = C[i];
	}//D is who need big
	int fja = tot2 + l2;//分界点
	for(int i = 0; i < T1; ++i) {
		mdf[i + l1] = B[i + 1];
	}//B is who need less
	for(int i = 1; i <= T2; ++i) {
		mdf[i + l1 + T1 - 1] = A[i];
	}//A is who need big
	int fjb = T1 + l1;
	// printf("New R1 :%d,New R2 :	%d\n", fja, fjb);
	if(fjb - 1 >= l1 && fja - 1 >= l2)
		fz(L, mid, l1, fjb - 1, l2, fja - 1);
	if(r1 >= fjb && r2 >= fja)
		fz(mid + 1, R, fjb, r1, fja, r2);
	return;
}

int main() {
	scanf("%d%d%d", &n, &p, &q);
	for(int i = 2, a, b; i <= n; ++i) {
		scanf("%d%d", &a, &b);
		ct(a, b);
		ct(b, a);
	}
	for(int i = 1; i <= p; ++i) {
		scanf("%d%d%d", &b[i].x, &b[i].y, &b[i].z);
		V = max(V, b[i].z);
	}
	dep[1] = 1;
	dfs(1, 0); //init dfn,siz
	dfs2(1, 1);
	// for(int i = 1; i <= n; ++i)printf("well finished....%d %d\n", i, dfn[i]);
	for(int i = 1; i <= q; ++i) {
		scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].z);
		if(dfn[a[i].x] > dfn[a[i].y])
			swap(a[i].x, a[i].y);
		a[i].id = i;
	}
	init();
	fz(1, V, 1, p, 1, q); //整体二分!!
	for(int i = 1; i <= q; ++i) {
		printf("%d\n", ans[i]);
	}
	return 0;
}
Powered by Gridea RSS