BZOJ 2588: Spoj 10628. Count on a tree-可持久化线段树+LCA(点权)(树上的操作) 无语(为什么我的LCA的板子不对)

2588: Spoj 10628. Count on a tree

Time Limit: 12 Sec  Memory Limit: 128 MB
Submit: 9280  Solved: 2421
[Submit][Status][Discuss]

Description

给定一棵N个节点的树,每个点有一个权值,对于M个询问(u,v,k),你需要回答u xor lastans和v这两个节点间第K小的点权。其中lastans是上一个询问的答案,初始为0,即第一个询问的u是明文。
 

Input

第一行两个整数N,M。
第二行有N个整数,其中第i个整数表示点i的权值。
后面N-1行每行两个整数(x,y),表示点x到点y有一条边。
最后M行每行两个整数(u,v,k),表示一组询问。
 

Output

M行,表示每个询问的答案。最后一个询问不输出换行符

Sample Input

8 5
105 2 9 3 8 5 7 7
1 2
1 3
1 4
3 5
3 6
3 7
4 8
2 5 1
0 5 2
10 5 3
11 5 4
110 8 2

Sample Output

2
8
9
105
7

HINT




HINT:

N,M<=100000

暴力自重。。。
 
 
 
题意很好理解,就是树上查找区间第K大,因为不是在线性上的操作,所以建树更新的时候在dfs里更新,查找路径上的第K大,就是区间查找的操作,从x到LCA(x,y),然后再从LCA(x,y)到y就可以了,因为是点权的操作,所以是去掉lca,然后去掉lca的爸爸,这样就对了。我写的时候写了好久,RE了无数次,最后发现:竟然是我以前LCA的板子不对!!!!(暴风哭泣,气死),但是我并不知道为什么我的LCA写的为什么不对。。。
 
代码:
  1 //BZOJ 2588 可持久化线段树+LCA
  2 #include<iostream>
  3 #include<cstdio>
  4 #include<cstring>
  5 #include<algorithm>
  6 #include<bitset>
  7 #include<cassert>
  8 #include<cctype>
  9 #include<cmath>
 10 #include<cstdlib>
 11 #include<ctime>
 12 #include<deque>
 13 #include<iomanip>
 14 #include<list>
 15 #include<map>
 16 #include<queue>
 17 #include<set>
 18 #include<stack>
 19 #include<vector>
 20 using namespace std;
 21 typedef long long ll;
 22 
 23 const double PI=acos(-1.0);
 24 const double eps=1e-6;
 25 const ll mod=1e9+7;
 26 const int inf=0x3f3f3f3f;
 27 const int maxn=1e5+10;
 28 const int maxm=100+10;
 29 #define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
 30 #define lson l,m
 31 #define rson m+1,r
 32 
 33 int ans,tot,cnt,lca;
 34 int n,d,q;
 35 int a[maxn],b[maxn],h[maxn],L[maxn<<5],R[maxn<<5];
 36 int to[maxn<<5],head[maxn],Next[maxn<<5];//存图
 37 int sum[maxn<<5],root[maxn],dep[maxn];
 38 int fa[maxn][20];
 39 
 40 void add(int x,int y)//存图
 41 {
 42     tot++;
 43     Next[tot]=head[x];
 44     head[x]=tot;
 45     to[tot]=y;
 46 }
 47 
 48 int LCA(int x,int y)
 49 {
 50     if(dep[x]<dep[y]) swap(x,y);
 51     for(int i=0;i<=19;i++) if(((dep[x]-dep[y])&(1<<i))!=0) x=fa[x][i];//不知道为什么我注释掉的那种写法为什么不对。。。
 52     //for(int i=0;i<=19;i++) if(dep[x]==dep[y]-(1<<i)) x=fa[x][i];
 53     if(x==y) return x;
 54     for(int i=19;i>=0;i--){
 55         if(fa[x][i]!=fa[y][i]){
 56             x=fa[x][i];
 57             y=fa[y][i];
 58         }
 59     }
 60     return fa[x][0];
 61 }
 62 
 63 void update(int pre,int &rt,int l,int r,int k)
 64 {
 65     rt=++cnt;sum[rt]=sum[pre]+1;
 66     L[rt]=L[pre];R[rt]=R[pre];
 67     if(l==r){
 68         return ;
 69     }
 70 
 71     int m=(l+r)>>1;
 72     if(k<=m) update(L[pre],L[rt],lson,k);
 73     else     update(R[pre],R[rt],rson,k);
 74 }
 75 
 76 int query(int x,int y,int lca,int fa,int l,int r,int k)
 77 {
 78     if(l==r){
 79         return h[l];
 80     }
 81 
 82     int m=(l+r)>>1;
 83     int now=sum[L[x]]+sum[L[y]]-sum[L[lca]]-sum[L[fa]];
 84     if(now>=k) return query(L[x],L[y],L[lca],L[fa],lson,k);
 85     else       return query(R[x],R[y],R[lca],R[fa],rson,k-now);
 86 }
 87 
 88 void dfs(int x,int fath)//按照dfs进行更新
 89 {
 90     dep[x]=dep[fath]+1;
 91     int k=lower_bound(b+1,b+1+d,a[x])-b;
 92     h[k]=a[x];
 93     update(root[fath],root[x],1,n,k);
 94     for(int i=1;i<=19;i++){
 95         fa[x][i]=fa[fa[x][i-1]][i-1];
 96     }
 97     for(int i=head[x];i;i=Next[i]){
 98         if(to[i]!=fath){
 99             fa[to[i]][0]=x;
100             dfs(to[i],x);
101         }
102     }
103 }
104 
105 int main()
106 {
107     scanf("%d%d",&n,&q);
108     for(int i=1;i<=n;i++){
109         scanf("%d",&a[i]);
110         b[i]=a[i];
111     }
112     sort(b+1,b+1+n);
113     d=unique(b+1,b+1+n)-(b+1);//去重建立权值线段树
114     for(int i=1;i<n;i++){
115         int x,y;
116         scanf("%d%d",&x,&y);
117         add(x,y);
118         add(y,x);
119     }
120     dfs(1,0);
121     while(q--){
122         int x,y,k;
123         scanf("%d%d%d",&x,&y,&k);
124         x=x^ans;
125         lca=LCA(x,y);
126         ans=query(root[x],root[y],root[lca],root[fa[lca][0]],1,n,k);//按照LCA,从x到lca,然后从lca到y,去掉lca的爸爸。
127         printf("%d
",ans);
128     }
129 }
原文地址:https://www.cnblogs.com/ZERO-/p/10281726.html