Peaks题解
浅提离线算法
将询问按照 \(x\) 排序，在最小生成树加边的过程中，每加一条边就把所有 \(x\) 小于当前边权的询问处理掉。
求第 \(k\) 大可以用平衡树搞定，将并查集合并时也将平衡树进行启发式合并（启发式合并也就是小的合并到大的上面）
在线做法
其实题目描述已经很明显了，Debug难度也不太大，只要学会主席树和Kruskal重构树即可。
每次询问都要求走权值小于等于一个值 \(x\) 的边，也就是能走的边的权值是有要求的，那么很自然就能想到Kruskal重构树，只需要将边按权值从小到大排序，求一棵Kruskal重构树。那么所有从当前点 \(v\) 出发，只走边权值小于等于\(x\)的边所能到达的点，全部都在 \(v\) 的最浅的权值小于等于 \(x\) 的祖先的子树内。所以我们只需要找到这个祖先，在其子树内寻找即可。
我们可以按叶子节点DFS序的大小，将所有的叶子节点排成一个序列，这样一个子树内的所有叶子节点的编号都是连续的。那么将这个序列的所有点的海拔建成一棵主席树，这样，对于每次询问，我们都将符合条件的祖先挑出来，查询它的子树中DFN序最小的记为 \(Left\)，DFN序最大的记为 \(Right\)，如果 \(Right-Left+1\) 是小于我们要求的排名的，那么直接输出 \(-1\) 即可，否则直接在主席树上查找 \(Left\) 到 \(Right\) 之间的第 \(k\) 大即可。
代码（强制在线）
/*
* Author:Ehundategh
* Update:2023/10/4
* Title:P7834.cpp
* You steal,I kill
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 100010
#define MAXM 500010
#define LSon Node[Now].LeftS
#define RSon Node[Now].RightS
using namespace std;
int DS_Fa[MAXN<<1],n,m,Q,cnt,Fa[MAXN<<1][23],Height[MAXN];
int LastAns=0;
int Line[MAXN],CopyL[MAXN],Count=0,Roots[MAXN],Look[MAXN],cnl=0;
struct edge{
int St,Ed;
int Value;
}Edge[MAXM];
bool cmp(edge a,edge b){
return a.Value<b.Value;
}
int Find(int a){return DS_Fa[a]==a?DS_Fa[a]:DS_Fa[a]=Find(DS_Fa[a]);}
struct node{
int LeftS,RightS;
int Value,Left,Right,Father;
}Node[MAXN<<1];
void Merge(int a,int b,int c){
Node[Find(a)].Father=c;
Node[Find(b)].Father=c;
Node[c].LeftS=Find(a);
Node[c].RightS=Find(b);
Fa[Find(a)][0]=c;
Fa[Find(b)][0]=c;
DS_Fa[Find(a)]=c;
DS_Fa[Find(b)]=c;
}
void Rebuild(){
sort(Edge+1,Edge+m+1,cmp);
for(int i=1;i<=2*n;i++) DS_Fa[i]=i;
for(int i=1;i<=m;i++){
if(Find(Edge[i].St)==Find(Edge[i].Ed)) continue;
Merge(Edge[i].St,Edge[i].Ed,++cnt);
Node[cnt].Value=Edge[i].Value;
}
}
void Init(){
for(int i=1;i<=21;i++){
for(int j=1;j<=cnt;j++){
Fa[j][i]=Fa[Fa[j][i-1]][i-1];
}
}
}
void ReMark(int Now){
if(Now<=n){
Line[++Count]=Height[Now];
CopyL[Count]=Height[Now];
Node[Now].Left=Node[Now].Right=Count;
return;
}
ReMark(LSon); ReMark(RSon);
Node[Now].Left=min(Node[LSon].Left,Node[RSon].Left);
Node[Now].Right=max(Node[LSon].Right,Node[RSon].Right);
}
void Ans(int St,int Top,int &Left,int &Right){
for(int i=21;i>=0;i--){
if(Node[Fa[St][i]].Value<=Top) St=Fa[St][i];
}
Left=Node[St].Left;
Right=Node[St].Right;
return;
}
void Discrete(){
sort(CopyL+1,CopyL+n+1);
for(int i=1;i<=n;i++){
if(i==1||CopyL[i]!=CopyL[i-1]){
Look[++cnl]=CopyL[i];
}
}
}
int DFind(int x){
return lower_bound(Look+1,Look+cnl+1,x)-Look;
}
class President_Tree{
private:
struct n{
int Left,Right;
int Sum;
}T[MAXN<<5];
public:
int New_Tree(int Last,int Left,int Right,int Value){
int Root=++cnt;
T[Root].Left=T[Last].Left;
T[Root].Right=T[Last].Right;
T[Root].Sum=T[Last].Sum+1;
int Mid=(Left+Right)/2;
if(Left!=Right){
if(Value<=Mid){T[Root].Left=New_Tree(T[Last].Left,Left,Mid,Value);}
else{T[Root].Right=New_Tree(T[Last].Right,Mid+1,Right,Value);}
}
return Root;
}
int Query(int Rank,int PeriodLeft,int PeriodRight,int Left,int Right){
if(Left==Right) return Left;
int Now=T[T[PeriodRight].Left].Sum-T[T[PeriodLeft].Left].Sum;
int Mid=(Left+Right)/2;
if(Now>=Rank){
return Query(Rank,T[PeriodLeft].Left,T[PeriodRight].Left,Left,Mid);
}
else{
return Query(Rank-Now,T[PeriodLeft].Right,T[PeriodRight].Right,Mid+1,Right);
}
}
}Tree;
int main(){
scanf("%d%d%d",&n,&m,&Q);
for(int i=1;i<=n;i++){
scanf("%d",&Height[i]);
}
for(int i=1;i<=m;i++){
scanf("%d%d%d",&Edge[i].St,&Edge[i].Ed,&Edge[i].Value);
}
cnt=n;
Rebuild();
ReMark(cnt);
Fa[cnt][0]=cnt;
Init();
Discrete();
for(int i=1;i<=Count;i++){
Roots[i]=Tree.New_Tree(Roots[i-1],1,cnl,DFind(Line[i]));
}
while(Q-->0){
int In1,In2,In3,L,R;
scanf("%d%d%d",&In1,&In2,&In3);
In1=((In1^LastAns)%n)+1;
In3=((In3^LastAns)%n)+1;
In2=In2^LastAns;
Ans(In1,In2,L,R);
if(R-L+1<In3) {LastAns=0; printf("-1\n"); }
else {
LastAns=Look[Tree.Query(R-L+2-In3,Roots[L-1],Roots[R],1,cnl)];
printf("%d\n",LastAns);
}
}
return 0;
}