点此看题面 https://www.luogu.org/problemnew/show/P2633
大致题意: 给你一棵树, 每次问你两点之间第 \(k\) 小的点权, 强制在线.
主席树
这种题目强制在线一般就是数据结构了.
而看到区间第 \(k\) 小, 很容易就能想到主席树.
至少不会有人想到树套树.
树上主席树
与一般的主席树不同, 这题的主席树是树上主席树 (不过许多奆佬称其为主席树上树).
维护数列的主席树, 我们一般是由前一个数的主席树构造当前树的主席树.
而树上的主席树其实也是类似的, 可以由父亲节点的主席树构造当前树的主席树.
关于查询操作
关于查询两个节点 \(x,y\) 路径间第 \(k\) 小的权值, 我们进行如下操作:
首先, 找到 \(x\) 和 \(y\) 的 \(LCA\), 姑且命名它为 \(z\).
然后, 我们可以进行差分, 即用 \(x\) 和 \(y\) 的值与 \(z\) 和 \(fa_z\) 的值相减, 就可以得出最终的答案 (这与数组版的主席树是类似的).
对于 \(LCA\), 我们可以直接用倍增 \(LCA\).
然后我们就可以发现这是一道主席树板子题.
代码
- #include<bits/stdc++.h>
- #define max(x,y) ((x)>(y)?(x):(y))
- #define min(x,y) ((x)<(y)?(x):(y))
- #define uint unsigned int
- #define LL long long
- #define ull unsigned long long
- #define swap(x,y) (x^=y,y^=x,x^=y)
- #define abs(x) ((x)<0?-(x):(x))
- #define INF 1e9
- #define Inc(x,y) ((x+=(y))>=MOD&&(x-=MOD))
- #define ten(x) (((x)<<3)+((x)<<1))
- #define N 100000
- #define LogN 20
- #define add(x,y) (e[++ee].nxt=lnk[x],e[lnk[x]=ee].to=y)
- using namespace std;
- int n,cnt,ee=0,a[N+5],p[N+5],lnk[N+5],Depth[N+5],fa[N+5][LogN+5];
- struct edge
- {
- int to,nxt;
- }e[(N<<1)+5];
- class FIO
- {
- private:
- #define Fsize 100000
- #define tc() (FinNow==FinEnd&&(FinEnd=(FinNow=Fin)+fread(Fin,1,Fsize,stdin),FinNow==FinEnd)?EOF:*FinNow++)
- #define pc(ch) (FoutSize<Fsize?Fout[FoutSize++]=ch:(fwrite(Fout,1,FoutSize,stdout),Fout[(FoutSize=0)++]=ch))
- int f,FoutSize,OutputTop;char ch,Fin[Fsize],*FinNow,*FinEnd,Fout[Fsize],OutputStack[Fsize];
- public:
- FIO() {FinNow=FinEnd=Fin;}
- inline void read(int &x) {x=0,f=1;while(!isdigit(ch=tc())) f=ch^'-'?1:-1;while(x=ten(x)+(ch&15),isdigit(ch=tc()));x*=f;}
- inline void read_char(char &x) {while(isspace(x=tc()));}
- inline void read_string(string &x) {x="";while(isspace(ch=tc()));while(x+=ch,!isspace(ch=tc())) if(!~ch) return;}
- inline void write(int x) {if(!x) return (void)pc('0');if(x<0) pc('-'),x=-x;while(x) OutputStack[++OutputTop]=x%10+48,x/=10;while(OutputTop) pc(OutputStack[OutputTop]),--OutputTop;}
- inline void write_char(char x) {pc(x);}
- inline void write_string(string x) {register int i,len=x.length();for(i=0;i<len;++i) pc(x[i]);}
- inline void end() {fwrite(Fout,1,FoutSize,stdout);}
- }F;
- inline int LCA(int x,int y)// 倍增 LCA
- {
- register int i;
- if(Depth[x]<Depth[y]) swap(x,y);
- for(i=0;Depth[x]^Depth[y];++i) if((Depth[x]^Depth[y])&(1<<i)) x=fa[x][i];
- if(!(x^y)) return x;
- for(i=0;fa[x][i]^fa[y][i];++i);
- for(--i;i>=0;--i) if(fa[x][i]^fa[y][i]) x=fa[x][i],y=fa[y][i];
- return fa[x][0];
- }
- class Class_ChairmanTree// 主席树
- {
- private:
- int n,tot,Root[N+5];
- struct Tree
- {
- int Val,Size,Son[2];
- }node[N*LogN+5];
- inline void Build(int l,int r,int &rt)// 建树
- {
- if(!rt&&(rt=++tot),!(l^r)) return;
- register int mid=l+r>>1;
- Build(l,mid,node[rt].Son[0]),Build(mid+1,r,node[rt].Son[1]);
- }
- inline void ins(int l,int r,int &rt,int lst,int val)// 插入
- {
- if(node[rt=++tot]=node[lst],++node[rt].Size,!(l^r)) return;
- register int mid=l+r>>1;
- val<=mid?ins(l,mid,node[rt].Son[0],node[lst].Son[0],val):ins(mid+1,r,node[rt].Son[1],node[lst].Son[1],val);
- }
- inline int qry(int l,int r,int rt1,int rt2,int rt3,int rt4,int k)// 查询
- {
- if(!(l^r)) return l;
- register int mid=l+r>>1,t=node[node[rt3].Son[0]].Size+node[node[rt4].Son[0]].Size-node[node[rt1].Son[0]].Size-node[node[rt2].Son[0]].Size;
- if(t>=k) return qry(l,mid,node[rt1].Son[0],node[rt2].Son[0],node[rt3].Son[0],node[rt4].Son[0],k);
- else return qry(mid+1,r,node[rt1].Son[1],node[rt2].Son[1],node[rt3].Son[1],node[rt4].Son[1],k-t);
- }
- public:
- inline void Init(int len) {Build(1,n=len,Root[0]);}// 初始化
- inline void Insert(int v,int nv,int val) {ins(1,n,Root[nv],Root[v],val);}
- inline int Query(int v1,int v2,int k) {return qry(1,n,Root[LCA(v1,v2)],Root[fa[LCA(v1,v2)][0]],Root[v1],Root[v2],k);}
- }ChairmanTree;
- inline int find(int x)// 离散化
- {
- register int l=1,r=cnt,mid=l+r>>1;
- for(;l<=r;mid=l+r>>1) p[mid]<x?l=mid+1:r=mid-1;
- return l;
- }
- inline void Init(int x)// 初始化
- {
- register int i;
- for(ChairmanTree.Insert(fa[x][0],x,find(a[x])),i=1;i<=LogN;++i) fa[x][i]=fa[fa[x][i-1]][i-1];// 由父亲的主席树建树
- for(i=lnk[x];i;i=e[i].nxt) if(fa[x][0]^e[i].to) Depth[e[i].to]=Depth[x]+1,fa[e[i].to][0]=x,Init(e[i].to);// 继续遍历
- }
- int main()
- {
- register int i,x,y,z,s,Q,ans=0;
- for(F.read(n),F.read(Q),i=1;i<=n;++i) F.read(a[i]),p[i]=a[i];
- for(i=1;i<n;++i) F.read(x),F.read(y),add(x,y),add(y,x);
- for(sort(p+1,p+n+1),ChairmanTree.Init(cnt=unique(p+1,p+n+1)-p-1),Init(1);Q;--Q)
- F.read(x),F.read(y),F.read(z),F.write(ans=p[ChairmanTree.Query(x^ans,y,z)]),F.write_char('\n');// 求答案
- return F.end(),0;
- }
来源: http://www.bubuko.com/infodetail-2824941.html