BZOJ1146 – [CTSC2008]网络管理Network(dfs序+LCA+主席树)

题目链接:BZOJ1146

【分析】这题最容易想到的就是二分答案+树链剖分+线段树套BST,但是复杂度有q*logn^4,而且代码量极大,本人太懒不想写了,学习了一种神一样的解法;而且复杂度才q*logn^2;

首先BZOJ2588可以知道,对于静态树上第K大,可以在每个点建一棵到根的前缀可持久化线段树,则查询任意两点间(x,y)的第k大可以在主席树T=a[x]+a[y]-2*[LCA(x,y)];由于是点所以变成T = a[x]+a[y]-a[LAC(x,y)]-a[fa[LCA(x,y)]];这个查询可以在主席树带入这四个点实现O(logn)的查询。然后这题是可修改的,如果直接套上树状数组没法在树上维护前缀和,怎么办?可以用DFS序呀!对于每一个点,在其入栈的时候加上,在出栈的时候减去。那么如果查询一个点入栈位置的前缀和,就是它到根的路径的信息。这样就转变成了区间可修改第k大+静态树上K大,查询时带入树状数组表示的值树按照这个公式T=a[x]+a[y]-2*[LCA(x,y)]计算即可。查询复杂度O(logn^2),可以配合静态n*logn预处理加上另外维护修改可以把空间复杂度降到n*logn+n*logn^2

【AC CODE】5188ms

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <set>
//#include <unordered_set>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <set>
//#include <unordered_set>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 80000+10, MAXQ = 80000+10, MAXM = 80*MAXN;
struct IN{
	int k,a,b;
}in[MAXQ];
int a[MAXN],n,num[MAXN+MAXQ],cnt,sot[MAXN+MAXQ],head[MAXN],e,nxt[MAXN<<1],to[MAXN<<1];
int sum[MAXM], lc[MAXM],rc[MAXM],tol;
int rt[MAXN<<2];

inline void add_edge(int u, int v)
{
	nxt[e] = head[u], to[e] = v;
	head[u] = e++;
}
inline int mhash(int v){return lower_bound(sot+1,sot+1+cnt,v)-sot;}
int fa[MAXN], ft[MAXN], d[MAXN<<1],id[MAXN<<1],all;
int df[MAXN<<1],st[MAXN],ed[MAXN],dcnt;
bool ised[MAXN<<1];
void dfs(int u, int dep)
{
	ft[u] = all, d[all] = dep, id[all++] = u;
	df[++dcnt] = a[u];st[u] = dcnt;ised[dcnt] = 0;
	for(int i = head[u]; ~i; i = nxt[i])
	{
		int v = to[i];
		if(v == fa[u]) continue;
		fa[v] = u;
		dfs(v,dep+1);
		d[all] = dep, id[all++] = u;
	}
	df[++dcnt] = a[u];ed[u] = dcnt;ised[dcnt] = 1;
}
int dp[MAXN<<1][21], dp_num[MAXN<<1][21];//dp_num记录dp对应的点的编号
void st_init()
{
	rep(i,0,all) dp[i][0] = d[i], dp_num[i][0] = id[i];
	for(int j = 1; (1<<j) <= all; j++)
	{
		for(int i = 0; i+(1<<j)-1 < all; i++)
		{
			if(dp[i][j-1] < dp[i+(1<<(j-1))][j-1])
			{
				dp[i][j] = dp[i][j-1];
				dp_num[i][j] = dp_num[i][j-1];
			}
			else
			{
				dp[i][j] = dp[i+(1<<(j-1))][j-1];
				dp_num[i][j] = dp_num[i+(1<<(j-1))][j-1];
			}
		}
	}
}
int st_query(int x, int y)
{
	if(x > y) swap(x,y);
	int k = 0;
	while((1<<(k+1)) <= y-x+1) k++;
	if(dp[x][k] <= dp[y-(1<<k)+1][k]) return dp_num[x][k];
	return dp_num[y-(1<<k)+1][k];
}
int lca_query(int x, int y){ return st_query(ft[x],ft[y]);}//x,y的LCA, O(1)
void bulid(int &u, int x, int y, int p, int v)
{
	sum[++tol] = sum[u]+v,lc[tol] = lc[u],rc[tol] = rc[u];
	u = tol;
	if(x == y) return;
	int m = (x+y)>>1;
	if(p <= m) bulid(lc[u],x,m,p,v);
	else bulid(rc[u],m+1,y,p,v);
}
void init()
{
	all = tol = 0;
	clc(rt,0);
	dfs(1,0);
	st_init();
	rt[dcnt+1] = rt[0];
	bulid(rt[dcnt+1],1,cnt,mhash(df[1]),1);
	repe(i,2,dcnt)
	{
		rt[i+dcnt] = rt[i-1+dcnt];
		int v = 1;
		if(ised[i]) v = -1;
		bulid(rt[i+dcnt],1,cnt,mhash(df[i]),v);
	}
}
void t_update(int &u, int x, int y, int p, int v)
{
	if(!u) {lc[++tol] = lc[u],rc[tol] = rc[u], sum[tol] = sum[u];u = tol;}
	sum[u] += v;
	if(x == y) return;
	int m = (x+y)>>1;
	if(p <= m) t_update(lc[u],x,m,p,v);
	else t_update(rc[u],m+1,y,p,v);
}
inline int lowbit(int x){return x&-x;}
void add(int x, int v)
{
	int p = mhash(df[x]);
	while(x <= dcnt)
	{
		t_update(rt[x],1,cnt,p,v);
		x += lowbit(x);
	}
}
void update(int x, int v)
{
	add(st[x],-1);//第一次出现点删掉原来加上新的
	df[st[x]] = v;
	add(st[x],1);
	add(ed[x],1);//最后一次出现点相反
	df[ed[x]] = v;
	add(ed[x],-1);
}
int tx[100],ty[100],len[2];
int query(int x, int y, int k)
{
	if(x == y) return x;
	int m = (x+y)>>1, tmp = 0;
	rep(i,0,len[1]) tmp += sum[rc[ty[i]]];
	rep(i,0,len[0]) tmp -= sum[rc[tx[i]]];
	if(tmp >= k)
	{
		rep(i,0,len[1]) ty[i] = rc[ty[i]];
		rep(i,0,len[0]) tx[i] = rc[tx[i]];
		return query(m+1,y,k);
	}
	rep(i,0,len[1]) ty[i] = lc[ty[i]];
	rep(i,0,len[0]) tx[i] = lc[tx[i]];
	return query(x,m,k-tmp);
}

int main()
{
#ifdef SHY
	freopen("d:\\1.txt", "r", stdin);
#endif
	int q;
	scanf("%d %d",&n, &q);
	int cc = 0;
	repe(i,1,n) scanf("%d", &a[i]), num[++cc] = a[i];
	e = 0;
	clc(head,-1);
	rep(i,1,n)
	{
		int u,v;
		scanf("%d %d", &u, &v);
		add_edge(u,v);
		add_edge(v,u);
	}
	rep(i,0,q)
	{
		scanf("%d %d %d", &in[i].k, &in[i].a, &in[i].b);
		if(!in[i].k) num[++cc] = in[i].b;
	}
	sort(num+1,num+1+cc);
	sot[cnt=1] = num[1];
	repe(i,2,cc) if(num[i] != num[i-1]) sot[++cnt] = num[i];
	init();
	rep(i,0,q)
	{
		if(in[i].k)
		{
			len[0]=len[1]=0;
			int lca = lca_query(in[i].a,in[i].b);
			int ta = st[in[i].a], tb = st[in[i].b],tlca = st[lca],tflca = st[fa[lca]];
			ty[len[1]++] = rt[ta+dcnt],ty[len[1]++] = rt[tb+dcnt];//静态初始值
			for(int j = ta; j > 0; j -= lowbit(j)) ty[len[1]++] = rt[j];
			for(int j = tb; j > 0; j -= lowbit(j)) ty[len[1]++] = rt[j];
			tx[len[0]++] = rt[tlca+dcnt],tx[len[0]++] = rt[tflca?tflca+dcnt:0];
			for(int j = tlca; j > 0; j -= lowbit(j)) tx[len[0]++] = rt[j];
			for(int j = tflca; j > 0; j -= lowbit(j)) tx[len[0]++] = rt[j];
			int tmp = 0;
			rep(j,0,len[1]) tmp += sum[ty[j]];
			rep(j,0,len[0]) tmp -= sum[tx[j]];
			if(tmp < in[i].k) puts("invalid request!");
			else printf("%d\n", sot[query(1,cnt,in[i].k)]);
		}
		else
			update(in[i].a,in[i].b);
	}
	return 0;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

请输入正确的验证码