https://www.lydsy.com/JudgeOnline/problem.php?id=1146
M公司是一个非常庞大的跨国公司，在许多国家都设有它的下属分支机构或部门。为了让分布在世界各地的N个
部门之间协同工作，公司搭建了一个连接整个公司的通信网络。该网络的结构由N个路由器和N-1条高速光缆组成。
每个部门都有一个专属的路由器，部门局域网内的所有机器都联向这个路由器，然后再通过这个通信子网与其他部
门进行通信联络。该网络结构保证网络中的任意两个路由器之间都存在一条直接或间接路径以进行通信。 高速光
缆的数据传输速度非常快，以至于利用光缆传输的延迟时间可以忽略。但是由于路由器老化，在这些路由器上进行
数据交换会带来很大的延迟。而两个路由器之间的通信延迟时间则与这两个路由器通信路径上所有路由器中最大的
交换延迟时间有关。作为M公司网络部门的一名实习员工，现在要求你编写一个简单的程序来监视公司的网络状况
。该程序能够随时更新网络状况的变化信息（路由器数据交换延迟时间的变化），并且根据询问给出两个路由器通
信路径上延迟第k大的路由器的延迟时间。【任务】 你的程序从输入文件中读入N个路由器和N-1条光缆的连接信息
，每个路由器初始的数据交换延迟时间Ti，以及Q条询问（或状态改变）的信息。并依次处理这Q条询问信息，它们
可能是： 1. 由于更新了设备，或者设备出现新的故障，使得某个路由器的数据交换延迟时间发生了变化。 2. 查
询某两个路由器a和b之间的路径上延迟第k大的路由器的延迟时间。
第一行为两个整数N和Q，分别表示路由器总数和询问的总数。
第二行有N个整数，第i个数表示编号为i的路由器初始的数据延迟时间Ti。
紧接着N-1行，每行包含两个整数x和y。表示有一条光缆连接路由器x和路由器y。
紧接着是Q行，每行三个整数k、a、b。
如果k=0，则表示路由器a的状态发生了变化，它的数据交换延迟时间由Ta变为b
如果k>0，则表示询问a到b的路径上所经过的所有路由器（包括a和b）中延迟
第k大的路由器的延迟时间。
注意N,Q<=80000,任意一个路由器在任何时刻都满足延迟时间小于10^8。
对于所有询问满足0<=K<=N
对于每一个第二种询问（k>0），输出一行。包含一个整数为相应的延迟时间。
如果路径上的路由器不足k个，则输出信息“invalidrequest!”
（全部小写不包含引号，两个单词之间有一个空格）。
5 5 5 1 2 3 4 3 1 2 1 4 3 5 3 2 4 5 0 1 2 2 2 3 2 1 4 3 3 5
3 2 2 invalid request!
思路：树链剖分之后就是区间动态第k大的问题了，树状数组套主席树即可。
#include<iostream> #include<cstdio> #include<vector> #include<algorithm> using namespace std; typedef long long ll; const int maxn=8e4+5; struct node { int lc,rc,siz; }tree[maxn*80];//节点 struct qury { int k,u,v; }q[maxn]; //离线操作 int n,m,ansx,ansy,tot,cnt,len;//n个数 m个查询 tot个节点 len为离散化后的长度 //ansx ansy 用于记录 查询操作 所需要的节点个数 int srt[maxn],rt[maxn],a[maxn],b[maxn<<1],qx[maxn<<1],qy[maxn<<1];//记录静态主席树根节点编号 新增节点编号 原序列 离散化后的序列 // qx qy 用于记录 查询操作 所需要的节点 int siz[maxn];//子树大小 int son[maxn];//重儿子 int fa[maxn];//父节点 int deep[maxn];//深度 int top[maxn];//所在链链顶 int pos[maxn];//dfs序编号 int Index[maxn]; vector<int> vec[maxn];//存边 void dfs1(int u,int f)//处理出重儿子 深度 父亲 子树大小等信息 { siz[u]=1; son[u]=0; fa[u]=f; deep[u]=deep[f]+1; int to; for(int i=0;i<vec[u].size();i++) { to=vec[u][i]; if(to!=f) { dfs1(to,u); siz[u]+=siz[to]; if(siz[son[u]]<siz[to]) son[u]=to; } } } void dfs2(int u,int f,int k)//处理出 链顶 dfs序 映射后的值 等信息 { top[u]=k; pos[u]=++cnt; Index[cnt]=u; if(son[u]) dfs2(son[u],u,k); int to; for(int i=0;i<vec[u].size();i++) { to=vec[u][i]; if(to!=f&&to!=son[u]) dfs2(to,u,to); } } inline int lowbit(int x) { return x&(-x); } inline void update(int &root,int pre,int l,int r,int pos,int num) { root=++tot; tree[root]=tree[pre]; tree[root].siz+=num; if(l==r) return; int mid=(l+r)>>1; if(pos<=mid) update(tree[root].lc,tree[pre].lc,l,mid,pos,num); else update(tree[root].rc,tree[pre].rc,mid+1,r,pos,num); } inline void add(int pos,int p,int v) { for(int i=pos;i<=n;i+=lowbit(i)) update(rt[i],rt[i],1,len,p,v); } inline int query(int l,int r,int k) { if(l==r) return l; int mid=(l+r)>>1; int sum=0; for(int i=1;i<=ansx;++i) sum-=tree[tree[qx[i]].lc].siz; for(int i=1;i<=ansy;++i) sum+=tree[tree[qy[i]].lc].siz; if(k<=sum){ for(int i=1;i<=ansx;++i) qx[i]=tree[qx[i]].lc; for(int i=1;i<=ansy;++i) qy[i]=tree[qy[i]].lc; return query(l,mid,k); } else{ for(int i=1;i<=ansx;++i) qx[i]=tree[qx[i]].rc; for(int i=1;i<=ansy;++i) qy[i]=tree[qy[i]].rc; return query(mid+1,r,k-sum); } } inline void solve(int x,int y,int k) { ansx=ansy=0; while(top[x]!=top[y]) { if(deep[top[x]]<deep[top[y]]) swap(x,y); for(int i=pos[top[x]]-1;i;i-=lowbit(i)) qx[++ansx]=rt[i]; for(int i=pos[x];i;i-=lowbit(i)) qy[++ansy]=rt[i]; qx[++ansx]=srt[pos[top[x]]-1]; qy[++ansy]=srt[pos[x]]; x=fa[top[x]]; } if(deep[x]>deep[y]) swap(x,y); for(int i=pos[x]-1;i;i-=lowbit(i)) qx[++ansx]=rt[i]; for(int i=pos[y];i;i-=lowbit(i)) qy[++ansy]=rt[i]; qx[++ansx]=srt[pos[x]-1]; qy[++ansy]=srt[pos[y]]; int sum=0; for(int i=1;i<=ansx;i++) sum-=tree[qx[i]].siz; for(int i=1;i<=ansy;i++) sum+=tree[qy[i]].siz; if(sum<k) printf("invalid request!\n"); else printf("%d\n",b[query(1,len,sum-k+1)]); } inline void prework()//初始化操作 包括离散化等 { tot=len=rt[0]=0; scanf("%d %d",&n,&m); for(int i=1;i<=n;++i) { scanf("%d",&a[i]); b[++len]=a[i]; } int u,v; for(int i=1;i<n;i++) { scanf("%d%d",&u,&v); vec[u].push_back(v); vec[v].push_back(u); } for(int i=1;i<=m;++i) { scanf("%d%d%d",&q[i].k,&q[i].u,&q[i].v); if(!q[i].k) b[++len]=q[i].v; } sort(b+1,b+1+len); len=unique(b+1,b+1+len)-b-1; for(int i=1;i<=n;++i) a[i]=lower_bound(b+1,b+len+1,a[i])-b; dfs1(1,0); dfs2(1,0,1); for(int i=1;i<=n;i++) update(srt[i],srt[i-1],1,len,a[Index[i]],1); for(int i=1;i<=n;i++) rt[i]=srt[0]; } inline void mainwork()//查询操作 { for(int i=1;i<=m;++i) { if(!q[i].k)//修改 { add(pos[q[i].u],a[q[i].u],-1); a[q[i].u]=lower_bound(b+1,b+1+len,q[i].v)-b; add(pos[q[i].u],a[q[i].u],1); } else solve(q[i].u,q[i].v,q[i].k); } } int main() { prework(); mainwork(); return 0; }
