Count on a tree

|

学习了主席树后被虐了。。。

传送门

题意:

求静态树上第k小,强制在线。

做法:

刚学了主席树开始做这题,一开始以为是树剖还在想零零碎碎的区间怎么合并,但实际上用树上差分就好了。

在树上建主席树,把a结点基于fa[a]结点建树。

查询的时候用$sum[x]+sum[y]-sum[lca]-sum[fa[lca]]$判断

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include<cstdio>
#include<iostream>
#include<algorithm>
#define maxn 100001
using namespace std;
struct node{
int h,z;
}a[maxn];
struct edge{
int next,to;
}w[maxn<<1];
int head[maxn*25],edg,cnt,top[100010*25],sum[maxn*25];
int c[maxn],hs[maxn],size[maxn],ls[maxn*25],n,m;
int b[maxn],deep[maxn],fa[maxn],rs[maxn*25],bs[maxn];
inline bool cmp(node c,node d){
return c.z<d.z;
}
inline void add(int x,int y){
w[++edg].next=head[x];
w[edg].to=y; head[x]=edg;
}
void built(int &rt,int l,int r){
rt=++cnt;
if (l==r) return;
int mid=(l+r)>>1;
built(ls[rt],l,mid);
built(rs[rt],mid+1,r);
}
int build(int rt,int l,int r,int p){
int t=++cnt;
ls[t]=ls[rt],rs[t]=rs[rt],sum[t]=sum[rt]+1;
if (l==r) return t; int mid=(l+r)>>1;
if (p<=mid) ls[t]=build(ls[rt],l,mid,p);
else rs[t]=build(rs[rt],mid+1,r,p);
return t;
}
//void build(int rt,int &now,int l,int r,int p){
// now=++cnt; sum[now]=sum[rt]+1;
// if (l==r) return;
// int mid=(l+r)>>1;
// if (p<=mid) rs[now]=rs[rt],build(ls[rt],ls[now],l,mid,p);
// else ls[now]=ls[rt],build(rs[rt],rs[now],mid+1,r,p);
//}
void dfs1(int x,int da){
fa[x]=da; size[x]=1;
bs[x]=build(bs[da],1,b[a[n].h],b[x]);
for (int i=head[x]; i; i=w[i].next){
if (w[i].to!=da){
deep[w[i].to]=deep[x]+1;
dfs1(w[i].to,x);
size[x]+=size[w[i].to];
if (size[w[i].to]>size[hs[x]]) hs[x]=w[i].to;
}
}
}
void dfs2(int x,int tp){
top[x]=tp;
if (hs[x]) dfs2(hs[x],tp);
for (int i=head[x]; i; i=w[i].next)
if (w[i].to!=fa[x]&&w[i].to!=hs[x])
dfs2(w[i].to,w[i].to);
}
inline int lca(int x,int y){
while (top[x]!=top[y]){
if (deep[top[x]]<deep[top[y]]) swap(x,y);
x=fa[top[x]];
}
if (deep[x]<deep[y]) swap(x,y);
return y;
}
int query(int x,int y,int da,int gr,int l,int r,int k){
if (l>=r) return l; int mid=(l+r)>>1;
int num=sum[ls[x]]+sum[ls[y]]-sum[ls[da]]-sum[ls[gr]];
if (num>=k) return query(ls[x],ls[y],ls[da],ls[gr],l,mid,k);
else return query(rs[x],rs[y],rs[da],rs[gr],mid+1,r,k-num);
}
int main(){
int last=0,x,y,z;
scanf("%d%d",&n,&m);
for (int i=1; i<=n; i++){
scanf("%d",&a[i].z);
a[i].h=i;
}
sort(a+1,a+n+1,cmp); a[0].z=-1;
for (int i=1; i<=n; i++){
b[a[i].h]=b[a[i-1].h];
if (a[i].z!=a[i-1].z) b[a[i].h]++;
c[b[a[i].h]]=a[i].z;
}
for (int i=1; i<=n-1; i++){
scanf("%d%d",&x,&y);
add(x,y); add(y,x);
}
// built(bs[0],1,b[a[n].h]);
deep[1]=1; dfs1(1,0); dfs2(1,1);
while (m--){
scanf("%d%d%d",&x,&y,&z);
x^=last; int lc=lca(x,y);
last=c[query(bs[x],bs[y],bs[lc],bs[fa[lc]],1,b[a[n].h],z)];
printf("%d\n",last);
}
return 0;
}

改天写一下主席树学习笔记 不会咕

文章目录
  1. 1. 题意:
  2. 2. 做法:
,
载入天数...载入时分秒... 字数统计:75.7k