【BZOJ 2588】 Spoj 10628. Count on a tree|树上K大|树链剖分|主席树

本文主要是介绍【BZOJ 2588】 Spoj 10628. Count on a tree|树上K大|树链剖分|主席树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

我沙茶

我沙茶

我沙茶

傻到去写链剖！ 本来求个LCA又好写又快.....

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
#define MAXN 100010int team[MAXN],head,tail;
int fa[MAXN],son[MAXN],size[MAXN],loc[MAXN],top[MAXN],depth[MAXN];int tot,g[MAXN*2],nnext[MAXN*2],num[MAXN*2];
void Add(int x,int y)
{tot++;nnext[tot]=g[x];g[x]=tot;num[tot]=y;
}void Lian_Pou()
{team[++tail]=1;depth[1]=1;while(head<tail){int x=team[++head];for(int i=g[x];i;i=nnext[i]){int tmp=num[i];if(depth[tmp]!=0) continue ;fa[tmp]=x;depth[tmp]=depth[x]+1;team[++tail]=tmp;}}for(int i=tail;i>=1;i--){int x=team[i];size[x]=1;for(int j=g[x];j;j=nnext[j]){int tmp=num[j];if(tmp==fa[x]) continue ;size[x] += size[tmp];if(size[tmp]>size[son[x]]) son[x]=tmp;}}loc[1]=1;top[1]=1;for(int i=1;i<=tail;i++){int x=team[i];int cnt=loc[x];if(son[x]!=0){loc[son[x]]=cnt+1;top[son[x]]=top[x];cnt+=size[son[x]];}for(int j=g[x];j;j=nnext[j]){int tmp=num[j];if(tmp==fa[x]||tmp==son[x]) continue ;loc[tmp]=cnt+1;top[tmp]=tmp;cnt+=size[tmp];}}
}
struct INIT
{int num;int loc;int no;
} init[MAXN];
bool cmp(INIT a,INIT b) 
{return a.loc<b.loc;
}
bool cmp1(INIT a,INIT b)
{return a.num<b.num;
}int cnt;
int seg_tot;
struct H
{int L,R;int sum;
}seg[MAXN*20];void Seg_Add(int now,int l,int r,int x,int last)
{if(l==r) {seg[now].sum=seg[last].sum+1;;return ;}int mid=(l+r)/2;if(x<=mid) {seg[now].L=++seg_tot;seg[now].R=seg[last].R;last=seg[last].L;Seg_Add(seg[now].L,l,mid,x,last);}else{seg[now].R=++seg_tot;seg[now].L=seg[last].L;last=seg[last].R;Seg_Add(seg[now].R,mid+1,r,x,last);}seg[now].sum=seg[seg[now].L].sum+seg[seg[now].R].sum;
}
int hash[MAXN];
int root[MAXN];
int LL[MAXN],RR[MAXN],LN,RN;
void Solve(int x,int y)
{LN=0;RN=0;while(top[x]!=top[y]){if(depth[top[x]]<depth[top[y]]) swap(x,y);LL[++LN]=root[loc[top[x]]-1];RR[++RN]=root[loc[x]];x=fa[top[x]];}if(depth[x]<depth[y]) swap(x,y);LL[++LN]=root[loc[y]-1];RR[++RN]=root[loc[x]];
}int Q(int l,int r,int k)
{	if(l==r) return l;int S=0;for(int i=1;i<=LN;i++) {S-=seg[seg[LL[i]].L].sum;S+=seg[seg[RR[i]].L].sum;}int mid=(l+r)/2;if(k<=S){for(int i=1;i<=LN;i++) LL[i]=seg[LL[i]].L;for(int i=1;i<=RN;i++) RR[i]=seg[RR[i]].L;return Q(l,mid,k);}else{for(int i=1;i<=LN;i++) LL[i]=seg[LL[i]].R;for(int i=1;i<=RN;i++) RR[i]=seg[RR[i]].R;k-=S;return Q(mid+1,r,k);}
}int main()
{
//	freopen("a.in","r",stdin);
//	freopen("wa.out","w",stdout);int n,m;cin >> n >> m;for(int i=1;i<=n;i++) scanf("%d",&init[i].num);for(int i=1;i<n;i++){int x,y;scanf("%d %d",&x,&y);Add(x,y);Add(y,x);}Lian_Pou();for(int i=1;i<=n;i++) init[i].loc=loc[i];sort(init+1,init+1+n,cmp1);init[1].no=1;for(int i=2;i<=n;i++)if(init[i].num!=init[i-1].num)init[i].no=init[i-1].no+1;else init[i].no=init[i-1].no;cnt=init[n].no;for(int i=1;i<=n;i++) hash[init[i].no]=init[i].num;sort(init+1,init+n+1,cmp);for(int i=1;i<=n;i++){root[i]=++seg_tot;Seg_Add(root[i],1,cnt,init[i].no,root[i-1]);}int last=0;for(int i=1;i<=m;i++){int u,v,k;scanf("%d %d %d",&u,&v,&k);u^=last;Solve(u,v);last=hash[Q(1,cnt,k)];if(i!=m) printf("%d\n",last);else printf("%d",last);}return 0;
}

这篇关于【BZOJ 2588】 Spoj 10628. Count on a tree|树上K大|树链剖分|主席树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---