#P3551. [ONTAK2010]Peaks加强版

    ID: 2761 传统题 2000ms 128MiB 尝试: 4407 已通过: 785 难度: 7 上传者: 标签>难度分类提高+/省选-图论Kruskal 重构树数据结构普通并查集树算法树上倍增子树转区间排序与序列处理离散化可持久化线段树前缀版本作差线段树上二分CF2300

[ONTAK2010]Peaks加强版

[ONTAK2010] Peaks 加强版

题目描述

山地中有编号为 11 到 nn 的山峰,第 ii 座山峰的高度为 hih_i。山峰间有 mm 条双向道路,每条道路有一个困难值。

每次询问给出 v,x,kv,x,k。从 vv 出发,仅能走困难值不超过 xx 的道路。把所有可到达的山峰(包括 vv)按高度从高到低排列,问第 kk 座山峰的高度。高度相同的山峰分别占用一个名次。若可到达的山峰少于 kk 座,答案为 −1-1。

输入格式

第一行三个整数 n,m,qn,m,q,分别表示山峰数、道路数、询问数。第二行给出 nn 个整数 h1,…,hnh_1,\ldots,h_n。

接下来 mm 行,每行三个整数 a,b,ca,b,c,表示山峰 a,ba,b 之间有一条困难值为 cc 的双向道路。

最后 qq 行,每行三个整数 v′,x′,k′v',x',k'。记上一次询问的答案为 lastans\mathrm{lastans},初始为 00。如果 lastans=−1\mathrm{lastans}=-1,直接使用读入的三项数据;否则分别解码为

$$v=v'\oplus\mathrm{lastans},\qquad x=x'\oplus\mathrm{lastans},\qquad k=k'\oplus\mathrm{lastans},$$

其中 ⊕\oplus 表示按位异或。

输出格式

按询问顺序输出 qq 行,每行一个整数,表示第 kk 高的可达山峰的高度,或无解时的 −1-1。

数据范围

1≤n≤1051\le n\le10^5,0≤m,q≤5×1050\le m,q\le5\times10^5,0≤hi,c,x≤1090\le h_i,c,x\le10^9。道路端点和解码后的起点 vv 是有效山峰编号,解码后的 kk 为正整数。