bzoj4009:[HNOI2015]接水果(扫描线+整体二分+树状数组/树套树)

题解

  打错几个字符调一天系列…市选💊
  这题的思路还是比较妙的,将树上的问题用dfs序转化之后就变成了平面上的问题。
  假设一个盘子(x,y)(x,y),满足lca(x,y)lca(x,y)不是xxyy,那么可以被接住的水果两个端点一定分别落在xxyy的子树里,这个用dfs序很好表示。
  如果lca(x,y)lca(x,y)xx,那么能接住的苹果一定满足一个端点在yy的子树中,另一个端点不在xxyy路径上xx的儿子sonxson_x的子树中,这个可以用dfs序转化成两个式子来表示。
  用dfs序表示之后实际上可以把苹果看成平面上的一个点,坐标就是两个端点的dfs序,盘子可以看成平面上的一些矩形,矩形左上和右下的点坐标是盘子两个端点可以接住苹果的dfs序范围上下界。
  那么问题就转化成了对每个点求能覆盖它的矩阵的第kk大权值,那么整体二分时用扫描线+树状数组处理就能解决了。
  因为每次只需要求单点第kk大,所以把整体二分换成树套树也是可以的,就变成有点模板的题了233
  写这题的时候太放荡不羁常数貌似有点爆炸,整体二分貌似跑得比CZL的树套树还慢,但至少还在榜上第55页…有时间补一下树套树。

代码

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=500010, inf=1e9;
struct poi{int too, pre;}e[maxn];
struct que{int x, y, delta, pos, k;}q[maxn], q1[maxn], q2[maxn];
int Q, n, m, s, x, y, k, tot, tott, cnt;
int tree[maxn], size[maxn], last[maxn], fa[maxn], son[maxn], l[maxn], r[maxn], top[maxn], dep[maxn], ans[maxn], z[maxn];	
inline void read(int &k)
{
	int f=1; k=0; char c=getchar();
	while(c<'0' || c>'9') c=='-' && (f=-1), c=getchar();
	while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
	k*=f;
}
inline int abs(int x){return x>0?x:-x;}
bool operator < (que a, que b)
{return a.x<b.x || (a.x==b.x && a.y<b.y) || (a.x==b.x && a.y==b.y && a.k<b.k);}
inline void add(int x, int y){e[++tot]=(poi){y, last[x]}; last[x]=tot;}
inline void update(int x, int delta){for(;x<=n;x+=x&-x) tree[x]+=delta;}
inline int query(int x){int sum=0; for(;x;x-=x&-x) sum+=tree[x]; return sum;}
void dfs1(int x)
{
	size[x]=1;
	for(int i=last[x], too;i;i=e[i].pre)
	if((too=e[i].too)!=fa[x])
	{
		fa[too]=x; dep[too]=dep[x]+1;
		dfs1(too);
		size[x]+=size[too];
		if(size[too]>size[son[x]]) son[x]=too;
	}
}
void dfs2(int x, int tp)
{
	top[x]=tp; l[x]=++tott; 
	if(son[x]) dfs2(son[x], tp);
	for(int i=last[x], too;i;i=e[i].pre)
	if((too=e[i].too)!=fa[x] && too!=son[x]) dfs2(too, too);
	r[x]=tott;
}
inline int lca(int x, int y)
{
	int last=0;
	while(top[x]!=top[y]) last=top[x], x=fa[top[x]];
	return x==y?last:son[y];
}
inline void addquery(int x, int x2, int y, int y2, int w)
{
	q[++cnt]=(que){x, y, 1, w, 0};
	q[++cnt]=(que){x, y2+1, -1, w, 0};
	q[++cnt]=(que){x2+1, y, -1, w, 0};
	q[++cnt]=(que){x2+1, y2+1, 1, w, 0};
}
void solve(int l, int r, int L, int R)
{
	if(l>r || L>R) return;
	if(l==r)
	{
		for(int i=L;i<=R;i++) 
		if(!q[i].delta) ans[q[i].pos]=z[l];
		return;
	}
	sort(q+L, q+R+1);
	int mid=(l+r)>>1, cnt1=0, cnt2=0;
	for(int i=L;i<=R;i++)
	if(q[i].delta)
	{
		if(q[i].pos<=z[mid]) q1[++cnt1]=q[i], update(q[i].y, q[i].delta);
		else q2[++cnt2]=q[i];
	}
	else
	{
		int tmp=query(q[i].y);
		if(tmp>=q[i].k) q1[++cnt1]=q[i];
		else q[i].k-=tmp, q2[++cnt2]=q[i];
	}
	for(int i=1;i<=cnt1;i++) if(q1[i].delta) update(q1[i].y, -q1[i].delta);
	for(int i=1;i<=cnt1;i++) q[L+i-1]=q1[i];
	for(int i=1;i<=cnt2;i++) q[L+cnt1+i-1]=q2[i];
	solve(l, mid, L, L+cnt1-1); solve(mid+1, r, L+cnt1, R);
}
int main()
{
	read(n); read(m); read(Q);
	for(int i=1;i<n;i++) 
	read(x), read(y), add(x, y), add(y, x);	
	dfs1(1); dfs2(1, 1); 
	for(int i=1;i<=m;i++)
	{
		read(x); read(y); read(z[i]);
		if(l[x]>l[y]) swap(x, y);
		if(l[x]<=l[y] && l[y]<=r[x])
		{
			int fa=lca(y, x);
			if(l[fa]>1) addquery(1, l[fa]-1, l[y], r[y], z[i]);
			if(r[fa]<n) addquery(l[y], r[y], r[fa]+1, n, z[i]);
		}
		else addquery(l[x], r[x], l[y], r[y], z[i]);
	}
	for(int i=1;i<=Q;i++)
	{
		read(x); read(y); read(k);
		if(l[x]>l[y]) swap(x, y);
		q[++cnt]=(que){l[x], l[y], 0, i, k};
	}
	sort(z+1, z+1+m);
	solve(1, m, 1, cnt);
	for(int i=1;i<=Q;i++) printf("%d\n", ans[i]);
}