主席树总结（题目合集）

主席树总结（题目合集）

1、HDU  2665

题意：无修改区间第k大

思路：主席树（离线算法）网上都有各种详细的解释了，就不多说了。。。主席树的核心思想包括前缀和、二分查找、空间重复利用、转化（区间表示在此范围内的数的个数，即权值线段树）。时间和空间复杂度为nlogn。

代码：

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 1e5+10;
int L[20*maxn],R[20*maxn],T[20*maxn],sum[20*maxn],a[maxn],b[maxn];
int tot;void build(int& rt,int l,int r){///建立空树T[0]rt=++tot;sum[rt]=0;if(l==r) return ;int mid=(l+r)>>1;build(L[rt],l,mid);build(R[rt],mid+1,r);
}
///对所有前缀更新树
void update(int& rt,int pre,int l,int r,int pos){rt = ++tot;L[rt]=L[pre];R[rt]=R[pre];sum[rt]=sum[pre]+1;if(l==r) return ;int mid=(l+r)/2;if(pos<=mid) update(L[rt],L[pre],l,mid,pos);else update(R[rt],R[pre],mid+1,r,pos);
}
///二分查找
int query(int s,int e,int l,int r,int k){if(l==r) return l;int res=sum[L[e]]-sum[L[s]];int mid=(l+r)/2;if(k<=res) return query(L[s],L[e],l,mid,k);else return query(R[s],R[e],mid+1,r,k-res);
}int main(){int t,n,m;cin>>t;while(t--){tot=0;cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i],b[i]=a[i];///离散化 使用 sort + unique + lower_bound 比较方便 map也行 或者二分查找sort(b+1,b+n+1);int num=unique(b+1,b+n+1)-b-1;build(T[0],1,num);for(int i=1;i<=n;i++)update(T[i],T[i-1],1,num,lower_bound(b+1,b+num+1,a[i])-b);///(先排序)lower_bounder函数返回第一个大于或者等于该元素的下标while(m--) {int s,e,k;cin>>s>>e>>k;int ans=query(T[s-1],T[e],1,num,k);cout<<b[ans]<<endl;}}
}

2、The Preliminary Contest for ICPC Asia Nanjing 2019 F. Greedy Sequence

题意：给出n,k，然后给出一个长度为n的序列A，构造n个序列Si。要求Si序列的开头必须是Ai，问每个序列的长度。看第二组样例，A[1]=3，在前k个和后k个元素中找一个小于A[1]的最大的数，找到这个数后在找这个数前k个到后k个小于他的最大的数，直到找不到为止。

第二组样例构造的序列：
1
2
3 1
4 3 1
5 2
6 5 2
7 5 2

分析：从小到大找答案，对于答案i开头的序列，通过主席树找到[pos[i]-k,pos[i]+k]区间内小于i的最大值（pos[i]表示i的位置），主席树查询的时候，先贪心往右查询，如果往右找不到，再往左找，代码细节要注意。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5+5;
int t,n,k,a[N],ans[N],pos[N];
int rt[N*20],ls[N*20],rs[N*20],sum[N*20],cnt=0;void up(int pre,int& o,int l,int r,int pos) {o=++cnt;ls[o]=ls[pre];rs[o]=rs[pre];sum[o]=sum[pre]+1;if(l==r) return ;int m=(l+r)/2;if(pos<=m) up(ls[pre],ls[o],l,m,pos);else up(rs[pre],rs[o],m+1,r,pos);
}int qu(int pre,int o,int l,int r,int kk) {if(l==r) {if(l>kk) return -1;return l;}int m=(l+r)/2;if(kk>m && sum[rs[o]]-sum[rs[pre]]) {int ans = qu(rs[pre],rs[o],m+1,r,kk);if(ans==-1) {if(kk>=l && sum[ls[o]]-sum[ls[pre]])return qu(ls[pre],ls[o],l,m,kk);return -1;}else return ans;}if(kk>=l && sum[ls[o]]-sum[ls[pre]])return qu(ls[pre],ls[o],l,m,kk);return -1;
}int main(){scanf("%d",&t);while(t--) {cnt = 0;scanf("%d%d",&n,&k);for(int i=1;i<=n;i++) {scanf("%d",&a[i]);pos[a[i]]=i;up(rt[i-1],rt[i],1,n,a[i]);}for(int i=1;i<=n;i++) {int l=max(1,pos[i]-k),r=min(n,pos[i]+k);int s1=qu(rt[l-1],rt[pos[i]-1],1,n,i-1);int s2=qu(rt[pos[i]],rt[r],1,n,i-1);int res = max(s1,s2);if(res==-1) ans[i] = 1;else ans[i] = ans[res]+1;}for(int i=1;i<n;i++) printf("%d ",ans[i]);printf("%dn",ans[n]);}return 0;
}

3、洛谷 P2617 Dynamic Rankings

题意：动态区间第k大。

分析：树套树，树状数组+主席树，纯模板。

代码（纯模板）：

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;const int N = 100007;int n, m, num, n1, n2;
int a[N], b[N << 1], c[N], d[N], e[N], t1[N], t2[N];
int Top, Root[N], val[N * 400], ls[N * 400], rs[N * 400];inline int lowbit(int x) {return x & (-x);
}void Add(int &rt, int l, int r, int ind, int c) {if (!rt) rt = ++Top;val[rt] += c;if (l == r) return;int m = (l + r) >> 1;if (ind <= m) Add(ls[rt], l, m, ind, c);else Add(rs[rt], m+1, r, ind, c);
}void Change(int ind, int val) {int x = lower_bound(b + 1, b + 1 + num, a[ind]) - b;for (int i = ind; i <= n; i += lowbit(i))Add(Root[i], 1, num, x, val);
}int Kth(int l, int r, int k) { ///求第 k 大if (l == r) return l;int m = (l + r) >> 1, sum = 0;for (int i = 1; i <= n2; ++i)sum += val[ls[t2[i]]];for (int i = 1; i <= n1; ++i)sum -= val[ls[t1[i]]];if (sum >= k) {for (int i = 1; i <= n1; ++i) ///所有树的节点保持对应t1[i] = ls[t1[i]];for (int i = 1; i <= n2; ++i)t2[i] = ls[t2[i]];return Kth(l, m, k);} else {for (int i = 1; i <= n1; ++i)t1[i] = rs[t1[i]];for (int i = 1; i <= n2; ++i)t2[i] = rs[t2[i]];return Kth(m+1, r, k - sum);}
}int Kth_pre(int l, int r, int k) {n1 = n2 = 0;for (int i = l - 1; i >= 1; i -= lowbit(i)) ///处理出需要求和的 n1 棵树t1[++n1] = Root[i];for (int i = r; i >= 1; i -= lowbit(i))t2[++n2] = Root[i];return Kth(1, num, k);
}int main(){///读入scanf("%d%d", &n, &m);for (int i = 1; i <= n; ++i) {scanf("%d", &a[i]);b[++num] = a[i];}for (int i = 1; i <= m; ++i) {char ch = getchar();while (ch != 'Q' && ch != 'C')ch = getchar();if (ch == 'Q')scanf("%d%d%d", &c[i], &d[i], &e[i]);else {scanf("%d%d", &c[i], &d[i]);b[++num] = d[i]; ///对于所有出现过的值（包括插入操作中的值）离散化}}///离散化sort(b + 1, b + 1 + num);num = unique(b + 1, b + 1 + num) - b - 1;///建树for (int i = 1; i <= n; ++i)Change(i, 1);///处理操作&询问 因为要离散化所以要离线处理for (int i = 1; i <= m; ++i) {if (e[i]) {printf("%dn", b[Kth_pre(c[i], d[i], e[i])]);} else {Change(c[i], -1);a[c[i]] = d[i];Change(c[i], 1);}}return 0;
}

4、Codeforces 840D Destiny

题意：给出一个长为n的数组，q次询问，每次问[l, r]区间出现次数超过(r-l+1)/k的最小数是多少，不存在返回-1。

分析：主席树（权值线段树）上进行搜索，先往左子树（值小的）优先搜索，加个剪枝，如果区间内出现的次数已经小于(r-l+1)/k，就直接返回。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 3e5+5;
int n,q,a[N];int rt[N*20],ls[N*20],rs[N*20],sum[N*20],cnt=0;
void up(int pre,int& o,int l,int r,int pos) {o=++cnt;ls[o]=ls[pre];rs[o]=rs[pre];sum[o]=sum[pre]+1;if(l==r) return ;int m=(l+r)/2;if(pos<=m) up(ls[pre],ls[o],l,m,pos);else up(rs[pre],rs[o],m+1,r,pos);
}int qu(int pre,int o,int l,int r,int k) {if(l==r) return l;int m=(l+r)/2;if(sum[ls[o]]-sum[ls[pre]]>k) {int res = qu(ls[pre],ls[o],l,m,k);if(res != -1) return res;}if(sum[rs[o]]-sum[rs[pre]]>k) {int res = qu(rs[pre],rs[o],m+1,r,k);if(res != -1) return res;}return -1;
}int main(){scanf("%d%d",&n,&q);for(int i=1;i<=n;i++) {scanf("%d",&a[i]);up(rt[i-1],rt[i],1,n,a[i]);}while(q--) {int l,r,k;scanf("%d%d%d",&l,&r,&k);int ans = qu(rt[l-1],rt[r],1,n,(r-l+1)/k);printf("%dn",ans);}return 0;
}

5、P1972 [SDOI2009]HH的项链

题意：求区间数的种类数（不同数的个数）

分析：与以往的权值线段树不同，这里主席树保存的是每个数出现的位置，区间[l,r]表示位置属于这个区间的数有多少个，因为要去掉重复数的影响，所以在当前这颗线段树上要在对应区间（相同数上一次出现的位置）减去影响（-1），再在这个位置相应区间加上影响（+1）。查询[l,r]的时候直接在rt[r]这个前缀查询就好了。）（现在下面这份代码会T，数据加强了，要加读入优化或者一些卡常技巧）

代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
int n,q,a[N],p[N];int rt[N*40],ls[N*40],rs[N*40],sum[N*40],cnt=0;
void up(int pre,int& o,int l,int r,int pos,int val) {o=++cnt;ls[o]=ls[pre];rs[o]=rs[pre];sum[o]=sum[pre]+val;if(l==r) return ;int m=(l+r)/2;if(pos<=m) up(ls[pre],ls[o],l,m,pos,val);else up(rs[pre],rs[o],m+1,r,pos,val);
}int qu(int o,int l,int r,int ql,int qr) {if( ql<=l && qr>=r )  return sum[o];int ans = 0,m = (l+r)/2;if(ql<=m) ans += qu(ls[o],l,m,ql,qr);if(qr>m) ans += qu(rs[o],m+1,r,ql,qr);return ans;
}int main(){scanf("%d",&n);for(int i=1;i<=n;i++) {scanf("%d",&a[i]);if(!p[a[i]]) {up(rt[i-1],rt[i],1,n,i,1);}else {int tp;up(rt[i-1],tp,1,n,p[a[i]],-1);up(tp,rt[i],1,n,i,1);}p[a[i]] = i;}scanf("%d",&q);while(q--) {int l,r;scanf("%d%d",&l,&r);int ans = qu(rt[r],1,n,l,r);printf("%dn",ans);}return 0;
}

6、BZOJ 3585 mex

题意：求区间内未出现过的最小自然数（0，正无穷）。

分析：和上题差不多的思想，主席树也是维护位置，主席树节点对应[l,r]区间表示值域在此范围内的每个数最后出现位置的最小值。查询的时候在rt[r]这颗线段树上面查询，如果区间每个数最后出现位置的最小值小于查询区间左端点l时，继续往左找，这样可以保证结果是最小的且未在区间[l,r]内出现过。思想很奇特，思路很巧妙。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5+5;
const int M = 1e9;int rt[N*30],ls[N*30],rs[N*30],mn[N*30],cnt=0;
void up(int pre,int& o,int l,int r,int val,int pos) {o=++cnt;ls[o]=ls[pre];rs[o]=rs[pre];mn[o]=pos;if(l==r) return ;int m=(l+r)/2;if(val<=m) up(ls[pre],ls[o],l,m,val,pos);else up(rs[pre],rs[o],m+1,r,val,pos);mn[o]=min(mn[ls[o]],mn[rs[o]]);
}int qu(int o,int l,int r,int pos) {if(l==r) return l;int m=(l+r)/2;if( mn[ls[o]]<pos ) return qu(ls[o],l,m,pos);return qu(rs[o],m+1,r,pos);
}int a[N],n,q,l,r;
int main(){scanf("%d%d",&n,&q);for(int i=1;i<=n;i++) {scanf("%d",&a[i]);up(rt[i-1],rt[i],0,M,a[i],i);}while(q--) {scanf("%d%d",&l,&r);int ans = qu(rt[r],0,M,l);printf("%dn",ans);}return 0;
}

7、The Preliminary Contest for ICPC Asia Xuzhou 2019  I. query

题意：求区间[l,r]内满足min(a[i],a[j])=gcd(a[i],a[j])(l<=i<j<=r)的对数。

分析：题目实际上是求一个区间内一个数是另外一个数的倍数的有序对数，因为是一个排列，所以容易知道这样的对数不超过nlogn。我们可以建立主席树，每颗主席树保存在他前面是当前位置数的因子的数的位置，然后直接在第r颗线段树上查找位置在询问区间里面的个数就好了。（感觉空间复杂度吃不消，差不多是n*logn*logn，但是卡过去了）

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5+1;int rt[N],ls[N*200],rs[N*200],sum[N*200],cnt=0;
void up(int pre,int& o,int l,int r,int pos) {o=++cnt;ls[o]=ls[pre];rs[o]=rs[pre];sum[o]=sum[pre]+1;if(l==r) return ;int m=(l+r)/2;if(pos<=m) up(ls[pre],ls[o],l,m,pos);else up(rs[pre],rs[o],m+1,r,pos);
}int qu(int o,int l,int r,int ql,int qr) {if( ql<=l && qr>=r ) return sum[o];int m=(l+r)/2,ans=0;if(ql<=m) ans += qu(ls[o],l,m,ql,qr);if(qr>m) ans += qu(rs[o],m+1,r,ql,qr);return ans;
}int n,q,l,r,a[N],p[N];
vector<int> g[N];
int main(){scanf("%d%d",&n,&q);for(int i=1;i<=n;i++) {scanf("%d",&a[i]);p[a[i]]=i;}for(int i=1;i<=n;i++) {for(int j=2*i;j<=n;j+=i) {///防止重复计数if (p[i] < p[j]) g[p[j]].push_back(p[i]);if (p[i] > p[j]) g[p[i]].push_back(p[j]);}}for(int i=1;i<=n;i++) {rt[i] = rt[i-1];///技巧for(auto u:g[i])up(rt[i],rt[i],1,n,u);}while(q--) {scanf("%d%d",&l,&r);int ans = qu(rt[r],1,n,l,r);printf("%dn",ans);}return 0;
}

8、牛客练习赛51 F ABCBA

题意：给出一颗树，树上节点为一个字母，q次询问，每次询问u，v，从v到u的链上组成的字符串，包含序列"ABCBA"的个数（不是子串，可以不连续）。

分析：树上主席树，和树上路径第k大的思想差不多，以深度作为位置建立线段树，每次子节点从父节点转移过来。查询的时候（和权值线段树有所不同，这里不满足可减性），以lca分段，每段查询出对应深度范围内的结果，然后再合并，如果lca不是u或者v，那么合并的时候一段的子串要取反，这和插入的顺序对应起来。代码量稍大，这题内存是真的恶心，改了半天，主要领悟思想吧。

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 3e4 + 10, mod = 10007;
vector<int> g[N];
char s[N];struct nd {int ABCBA, A, AB, ABC, ABCB, B, BC, BCB, BCBA, C, CB, CBA, BA;nd operator+(const nd &t) const {nd tmp;tmp.ABCBA = (ABCBA + t.ABCBA + A * t.BCBA + AB * t.CBA + ABC * t.BA + ABCB * t.A) % mod;tmp.A = (A + t.A) % mod;tmp.AB = (AB + t.AB + A * t.B) % mod;tmp.ABC = (ABC + t.ABC + A * t.BC + AB * t.C) % mod;tmp.ABCB = (ABCB + t.ABCB + A * t.BCB + AB * t.CB + ABC * t.B) % mod;tmp.B = (B + t.B) % mod;tmp.BC = (BC + t.BC + B * t.C) % mod;tmp.BCB = (BCB + t.BCB + B * t.CB + BC * t.B) % mod;tmp.BCBA = (BCBA + t.BCBA + B * t.CBA + BC * t.BA + BCB * t.A) % mod;tmp.C = (C + t.C) % mod;tmp.CB = (CB + t.CB + C * t.B) % mod;tmp.CBA = (CBA + t.CBA + C * t.BA + CB * t.A) % mod;tmp.BA = (BA + t.BA + B * t.A) % mod;return tmp;}
}tr[N * 20];
int rt[N], ls[N * 20], rs[N * 20], cnt, f[N][20], dep[N], n;
#define mid (l + r) / 2
void up(int &o, int pre, int l, int r, int k, char c) {o = ++cnt;ls[o] = ls[pre];rs[o] = rs[pre];if (l == r) {if (c == 'A')tr[o].A = 1;else if (c == 'B')tr[o].B = 1;else if (c == 'C')tr[o].C = 1;return;}if (k <= mid)up(ls[o], ls[pre], l, mid, k, c);elseup(rs[o], rs[pre], mid + 1, r, k, c);tr[o] = tr[ls[o]] + tr[rs[o]];
}void dfs(int u, int fa) {f[u][0] = fa;dep[u] = dep[fa] + 1;for (int i = 1; i < 18; i++)f[u][i] = f[f[u][i - 1]][i - 1];up(rt[u], rt[fa], 1, n, dep[u], s[u]);for (auto v : g[u])if (v != fa)dfs(v, u);
}int LCA(int u, int v) {if (dep[u] < dep[v])swap(u, v);for (int i = 17; ~i; i--)if (dep[f[u][i]] >= dep[v])u = f[u][i];if (u == v)return u;for (int i = 17; ~i; i--)if (f[u][i] != f[v][i])u = f[u][i], v = f[v][i];return f[u][0];
}nd qu(int o, int l, int r, int ql, int qr) {if (l >= ql && r <= qr)return tr[o];if (qr <= mid)return qu(ls[o], l, mid, ql, qr);else if (ql > mid)return qu(rs[o], mid + 1, r, ql, qr);elsereturn qu(ls[o], l, mid, ql, qr) + qu(rs[o], mid + 1, r, ql, qr);
}int main() {int m, u, v;scanf("%d%d", &n, &m);scanf("%s", s + 1);for (int i = 1; i < n; i++) {scanf("%d%d", &u, &v);g[u].push_back(v);g[v].push_back(u);}dfs(1, 0);while (m--) {scanf("%d%d", &u, &v);int lca = LCA(u, v);int ans = 0;nd tmp;if(u==lca) {ans = qu(rt[v], 1, n, dep[lca], dep[v]).ABCBA;}else if(v==lca) {ans = qu(rt[u], 1, n, dep[lca], dep[u]).ABCBA;}else {/// u-lca v-lca 正反都行 因为ABCBA回文nd t1 = qu(rt[v], 1, n, dep[lca], dep[v]);nd t2 = qu(rt[u], 1, n, dep[lca] + 1, dep[u]);ans = (t1.ABCBA + t2.ABCBA + t1.A * t2.BCBA + t1.BA * t2.CBA + t1.CBA * t2.BA + t1.BCBA * t2.A) % mod;}printf("%dn", ans);}return 0;
}

9、洛谷 P4197 Peaks

题意：有N座山峰，每座山峰有他的高度hi​。有些山峰之间有双向道路相连，共M条路径，每条路径有一个困难值，这个值越大表示越难走，现在有Q组询问，每组询问询问从点v开始只经过困难值小于等于x的路径所能到达的山峰中第k高的山峰，如果无解输出-1。

分析：知道Kruskal重构树就好办了，询问的是高度中的第k大，会自然地想到要用主席树，只是说，要注意一个细节。不难发现，重构树的某一个非叶节点（边）会管辖某些叶子节点(点)，有趣的是，其管辖的叶子节点构成一个区间，换而言之是连续的。所以我可以先Kruskal重构树，然后做一遍dfs，这遍dfs的过程中，我们把所有的叶子节点 "摘" 下来，形成一个序列，并对每个节点维护其管辖的区间。然后每次询问就变成了：先在重构树上跳，跳到某个节点x后询问L[x]到R[x]这一段区间内第k大的数是谁？需要特别注意离散化。很容易搞混，而且能过样例。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e6+5;
int n,m,qq,f[N];
struct nd{int u,v,w;
}e[N];
bool cmp(nd x,nd y) {return x.w<y.w;
}int fd(int x) {if(x==f[x]) return x;else return f[x]=fd(f[x]);
}struct Node{int x, y, z;
}q[N],hh[N];vector<int> g[N];
int wt[N],num;///点权和总点数///克鲁斯卡尔重构树
void kru() {sort(e+1,e+m+1,cmp);for(int i=1;i<N;i++) f[i] = i;for(int i=1;i<=m;i++) {int x=fd(e[i].u),y=fd(e[i].v);if(x != y) {wt[++num] = e[i].w;g[num].push_back(x);g[num].push_back(y);f[x] = f[y] = num;}}
}int dep[N],fa[N][20],L[N],R[N],b[N],c[N],sz,tot;
void dfs(int pre,int u) {dep[u] = dep[pre] + 1;fa[u][0] = pre;for(int i=1;i<20;i++)fa[u][i] = fa[fa[u][i-1]][i-1];L[u] = tot;if(g[u].size() == 0) {b[++tot] = u;R[u] = tot;return ;}for(auto v:g[u])dfs(u,v);R[u] = tot;
}
///主席树求第k大
int rt[N],ls[N*20],rs[N*20],sum[N*20],cnt=0;
void up(int pre,int& o,int l,int r,int pos) {o=++cnt;ls[o]=ls[pre];rs[o]=rs[pre];sum[o]=sum[pre]+1;if(l==r) return ;int m=(l+r)/2;if(pos<=m) up(ls[pre],ls[o],l,m,pos);else up(rs[pre],rs[o],m+1,r,pos);
}int qu(int pre,int o,int l,int r,int k) {if(l==r) return l;int m=(l+r)/2;if(sum[ls[o]]-sum[ls[pre]]>=k) return qu(ls[pre],ls[o],l,m,k);else return qu(rs[pre],rs[o],m+1,r,k-(sum[ls[o]]-sum[ls[pre]]));
}int h[N];
void solve() {kru();dfs(num,num);///注意以什么离散化，不要搞混了for(int i=1;i<=tot;i++)up(rt[i-1],rt[i],1,n,h[b[i]]);while(qq--) {int v,x,k;scanf("%d%d%d",&v,&x,&k);for(int i=19;i>=0;i--)if(fa[v][i] && wt[fa[v][i]] <= x) v = fa[v][i]; ///找到深度最小且点权不大于k的祖先if(R[v]-L[v]<k) puts("-1");else {int ans = qu(rt[L[v]],rt[R[v]],1,n,R[v]-L[v]-k+1);printf("%dn",hh[ans].z);}}
}bool cmp1(Node x, Node y){return x.z < y.z;
}int main(){scanf("%d%d%d",&n,&m,&qq);for(int i=1;i<=n;i++) scanf("%d",&h[i]);///离散化部分，先将h数组离散化for(int i = 1; i <= n; i++) hh[i].x = i, hh[i].z = h[i];sort(hh + 1, hh + n + 1, cmp1);for(int i = 1; i <= n; i++) h[hh[i].x] = i;num = n;for(int i=1;i<=m;i++)scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);solve();return 0;
}

10、洛谷 P3899 [湖南集训]谈笑风生

题意：一棵树，给定a，求任何一个距a距离不超过给定的k的b，然后求一个c使得是a,b的后代。

分析：容易知道，a，b，c肯定在一条链上，如果b是a祖先，那么这部分的贡献通过乘法原理很容易求出来，如果b是a的儿子呢，似乎有些麻烦，要枚举与b相距不超过k的儿子子树大小，再累加起来。由于是子树问题，可以通过dfs序+主席树来解决。把深度看成下标，按dfs序对每个节点建立主席树，我们希望查询一个子树中，深度在deep[p]+1--deep[p]+k的点的权值和，由于在dfn序中，一个子树的编号连续，那么直接查询子树开始和结束的权值差即可。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e6+5;
int n,q,dep[N],dfn[N],son[N],tot,mxdep;
vector<int> g[N];int rt[N],ls[N*20],rs[N*20],cnt=0;
ll sum[20*N];
void up(int pre,int& o,int l,int r,int pos,int val) {o=++cnt;ls[o]=ls[pre];rs[o]=rs[pre];sum[o]=sum[pre]+val;if(l==r) return ;int m=(l+r)/2;if(pos<=m) up(ls[pre],ls[o],l,m,pos,val);else up(rs[pre],rs[o],m+1,r,pos,val);///sum[o]=sum[ls[o]]+sum[rs[o]];加不加都行
}ll qu(int pre,int o,int l,int r,int ql,int qr) {if(ql <= l && qr >= r) return sum[o]-sum[pre];int m=(l+r)/2;ll ans = 0;if(ql<=m) ans += qu(ls[pre],ls[o],l,m,ql,qr);if(qr>m) ans += qu(rs[pre],rs[o],m+1,r,ql,qr);return ans;
}void dfs(int u,int fa) {son[u] = 1;dfn[u] = ++tot;dep[u] = dep[fa] + 1;mxdep = max(mxdep,dep[u]);for(auto v:g[u]) {if(v==fa) continue;dfs(v,u);son[u] += son[v];}
}void dfs2(int u,int fa) {up(rt[dfn[u]-1],rt[dfn[u]],1,mxdep,dep[u],son[u]-1);for(auto v:g[u]) {if(v==fa) continue;dfs2(v,u);}
}int main(){scanf("%d%d",&n,&q);for(int i=1;i<n;i++) {int u,v;scanf("%d%d",&u,&v);g[u].push_back(v);g[v].push_back(u);}dfs(1,0);dfs2(1,0);while(q--) {int p,k;scanf("%d%d",&p,&k);ll ans=1LL*(son[p]-1)*min(dep[p]-1,k);ans += qu(rt[dfn[p]],rt[dfn[p]+son[p]-1],1,mxdep,min(mxdep,dep[p]+1),min(mxdep,dep[p]+k));printf("%lldn",ans);}return 0;
}

11、洛谷 P2633 Count on a tree

题意：给定一颗树,每个点有一个点权,询问两点简单路径上第k小的点权。

分析：之前用树链剖分做过，现在再用主席树做一下，对于一条链u−>v上的信息，我们可以把它看成(u−>root)+(v−>root)−LCA−>root−faLCA−>root。这样我们把每个点在它的父节点的基础上建立主席树，查询的时候就不再是两棵树相减，而是四棵树相加减了。算是树上主席树的模板题了。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5+5;
int n,q,a[N],b[N],sz;
vector<int> g[N];int rt[N],ls[N*20],rs[N*20],sum[N*20],cnt=0;
void up(int pre,int& o,int l,int r,int pos) {o=++cnt;ls[o]=ls[pre];rs[o]=rs[pre];sum[o]=sum[pre]+1;if(l==r) return ;int m=(l+r)/2;if(pos<=m) up(ls[pre],ls[o],l,m,pos);else up(rs[pre],rs[o],m+1,r,pos);
}int qu(int u,int v,int lca,int flca,int l,int r,int k) {if(l==r) return b[l];int m=(l+r)/2;int num = sum[ls[u]]-sum[ls[lca]]+sum[ls[v]]-sum[ls[flca]];if(num>=k) return qu(ls[u],ls[v],ls[lca],ls[flca],l,m,k);return qu(rs[u],rs[v],rs[lca],rs[flca],m+1,r,k-num);
}int dep[N],f[N][20];
void dfs(int u,int fa) {dep[u] = dep[fa] + 1;f[u][0] = fa;for(int i = 1; i<20; i++)f[u][i] = f[f[u][i-1]][i-1];int pos = lower_bound(b+1,b+1+sz,a[u]) - b;up(rt[fa],rt[u],1,sz,pos);for(auto v:g[u]) {if(v==fa) continue;dfs(v,u);}
}int LCA(int u,int v) {if(dep[u]<dep[v]) swap(u,v);///注意是交换u和v,不是交换dep[u]和dep[v]int d=dep[u]-dep[v];for(int i=0;i<20;i++)///先调整到同一深度if(d&(1<<i)) u=f[u][i];if(u==v) return u;for(int i=19;i>=0;i--) {///注意是倒着for，二进制拆分，从大到小尝试if(f[u][i]!=f[v][i]) {u=f[u][i];v=f[v][i];}}return f[u][0];
}int main(){scanf("%d%d",&n,&q);for(int i=1;i<=n;i++) scanf("%d",&a[i]),b[i]=a[i];sort(b+1,b+1+n);sz = unique(b+1,b+1+n) - b - 1;for(int i=1;i<n;i++) {int u,v;scanf("%d%d",&u,&v);g[u].push_back(v);g[v].push_back(u);}dfs(1,0);int last=0,u,v,k,lca,flca;while(q--) {scanf("%d%d%d",&u,&v,&k);u^=last;lca = LCA(u,v);flca = f[lca][0];last = qu(rt[u],rt[v],rt[lca],rt[flca],1,sz,k);printf("%dn",last);}return 0;
}