【bzoj2588】Count on a tree

Portal -->bzoj2588

Solution

　　不行我一定要来挂这道题qwq很气愤qwq（其实还不是因为自己蠢。。）

　　额首先说一下正解

　　如果这个问题放在序列上面的话。。直接离散化一下然后一个可持久化权值线段树就好了

　　然后放在树上的话，我们可以考虑处理树上点对问题的一个很常见的套路：

\[info(x\rightarrow y)=info(root\rightarrow x)+info(root\rightarrow y)-info(root\rightarrow lca)*2
\]

　　那所以我们还是用可持久化权值线段树，每一个节点\(x\)从\(fa[x]\)更新过来就好了

　　一个小trick是在查询的时候直接传参这样比较方便

　　还有就是因为是点值，所以要记得算上\(lca\)处的值

　　好的然而我在场上想到的是这样的：

　　“放在序列上直接可持久化权值线段树那放在树上当然是套个树链剖分啊”

　　然后码了个线段树合并什么的qwq总共4k，然后T掉了，原因是。。貌似这题的合并还是怎么的并不是log的。。。

　　综上，这题一定要挂上来，太气了qwq被自己蠢哭我需要智力康复qwq

　　

　　正解的代码大概长这个样子

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define TOP 20

using namespace std;

const int N=100010,SEG=(N+20)*20;

struct xxx{

	int y,nxt;

}a[N*2];

int pre[TOP+1][N],dep[N],V[N],val[N],Lis[N];

int h[N],sz[N],son[N];

int n,m,lastans,tot,dfn_t;

namespace Seg{/*{{{*/

	int ch[SEG][2],sz[SEG],rt[N];

	int n,tot,tot1;

	void pushup(int x){sz[x]=sz[ch[x][0]]+sz[ch[x][1]];}

	int newnode(int pre){

		ch[++tot][0]=ch[pre][0]; ch[tot][1]=ch[pre][1]; sz[tot]=sz[pre];

		return tot;

	}

	void _insert(int pre,int &x,int d,int lx,int rx){

		x=newnode(pre);

		if (lx==rx){++sz[x]; return;}

		int mid=lx+rx>>1;

		if (d<=mid) _insert(ch[pre][0],ch[x][0],d,lx,mid);

		else _insert(ch[pre][1],ch[x][1],d,mid+1,rx);

		pushup(x);

	}

	void insert(int pre,int x,int d){_insert(rt[pre],rt[x],d,1,n);tot1=tot;}

	int _query(int l,int r,int lca,int lx,int rx,int k,int pos){//pos=val[lca]

		if (lx==rx) return lx;

		int mid=lx+rx>>1,lsz=sz[ch[r][0]]+sz[ch[l][0]]-2*sz[ch[lca][0]];

		if (lx<=pos&&pos<=mid) ++lsz;

		if (k<=lsz) return _query(ch[l][0],ch[r][0],ch[lca][0],lx,mid,k,pos);

		return _query(ch[l][1],ch[r][1],ch[lca][1],mid+1,rx,k-lsz,pos);

	}

	int query(int l,int r,int lca,int k){return _query(rt[l],rt[r],rt[lca],1,n,k,val[lca]);}

	void _debug(int x,int l,int r){

		if (!x){

			for (int i=l;i<=r;++i) printf("%d %d\n",i,0);

			return;

		}

		if (l==r) {printf("%d %d\n",l,sz[x]);return;}

		int mid=l+r>>1;

		_debug(ch[x][0],l,mid);

		_debug(ch[x][1],mid+1,r);

	}

	void debug(int x){_debug(rt[x],1,n);}

}/*}}}*/

void add(int x,int y){a[++tot].y=y; a[tot].nxt=h[x]; h[x]=tot;}

void dfs(int fa,int x,int d){

	pre[0][x]=fa; dep[x]=d;

	Seg::insert(fa,x,val[x]);

	for (int i=1;i<=TOP;++i) pre[i][x]=pre[i-1][pre[i-1][x]];

	int u;

	for (int i=h[x];i!=-1;i=a[i].nxt){

		u=a[i].y;

		if (u==fa) continue;

		dfs(x,u,d+1);

	}

}

void prework(){

	sort(Lis+1,Lis+1+n);

	Lis[0]=unique(Lis+1,Lis+1+n)-Lis-1;

	int x;

	for (int i=1;i<=n;++i){

		x=lower_bound(Lis+1,Lis+1+Lis[0],val[i])-Lis;

		V[x]=val[i];

		val[i]=x;

	}

	Seg::n=Lis[0];

}

int get_lca(int x,int y){

	if (dep[x]<dep[y]) swap(x,y);

	for (int i=TOP;i>=0;--i)

		if (dep[pre[i][x]]>=dep[y]) x=pre[i][x];

	if (x==y) return x;

	for (int i=TOP;i>=0;--i)

		if (pre[i][x]!=pre[i][y]) x=pre[i][x],y=pre[i][y];

	return pre[0][x];

}

void solve(int x,int y,int k){

	int lca=get_lca(x,y);

	/*Seg::debug(x); printf("\n");

	Seg::debug(y); printf("\n");

	Seg::debug(lca); printf("\n");*/

	lastans=Seg::query(x,y,lca,k);

	printf("%d\n",V[lastans]);

	lastans=V[lastans];

}

int main(){/*{{{*/

#ifndef ONLINE_JUDGE

	freopen("a.in","r",stdin);

#endif

	int x,y,k;

	scanf("%d%d",&n,&m);

	memset(h,-1,sizeof(h));

	tot=0;

	for (int i=1;i<=n;++i) scanf("%d",val+i),Lis[++Lis[0]]=val[i];

	for (int i=1;i<n;++i){

		scanf("%d%d",&x,&y);

		add(x,y); add(y,x);

	}

	prework();

	dfs(0,1,1);

	lastans=0;

	for (int i=1;i<=m;++i){

		scanf("%d%d%d",&x,&y,&k);

		x^=lastans;

		solve(x,y,k);

	}

}/*}}}*/

巴特西

【bzoj2588】Count on a tree

Solution

最新文章

热门文章