BZOJ 3551: [ONTAK 2010] Peaks 강화 판 [kruskal 트 리 + 선분 트 리 통합]

제목 설명:
Bytemountains 에는 N 개의 산봉우리 가 있 고 모든 산봉우리 에는 그의 높이 가 있다 hi。일부 산봉우리 사이 에는 양 방향 도로 가 연결 되 어 있 고 모두 M 개의 경로 가 있 으 며 모든 경 로 는 어려움 치 c 가 있다. 이 수 치 는 클 수록 걷 기 어렵 다 는 것 을 나타 낸다. 지금 은 Q 조 가 물 었 다. 각 조 는 점 v 부터 어려움 치가 x 와 같은 경 로 를 통 해 도달 할 수 있 는 산봉우리 중 k 번 째 로 높 은 산봉우리 의 높이 만 물 었 다. 만약 에 수출 - 1 이 없 으 면.N < = 1 0 5 , M , Q < = 5 ∗ 1 0 5 ， h i , c , x < = 1 0 9 。 N<=10^5, M,Q<=5*10^5，h_i,c,x<=10^9。 N<=105,M,Q<=5∗105，hi​,c,x<=109。
제목 분석:
원제 면 이 틀 렸 습 니 다. 제 가 위 에서 수 정 했 습 니 다. 원제 면 에 '높이' 가 없 었 습 니 다. 그리고 저 는 WA 자 폐 했 습 니 다.
강화 판 은 온라인 입 니 다. 먼저 사 이 드 를 정렬 하고 kruskal 트 리 의 점 을 각각 동적 으로 열 리 는 선분 수 를 열 고 아버 지 는 두 아들 이 합 쳐 왔 습 니 다.물 어 볼 때 그 점 에서 위로 배가 되 어 병목 점 을 찾 고 그 선분 나무 에서 k 번 째 로 크 면 된다.(k 가 높 은 것 은 k - 1 개가 그것 보다 높 기 때문에 찾 을 때 오른쪽 나무의 siz 를 판정 하거나 밖에서 k 를 거꾸로 하 는 것 을 말한다)
선분 트 리 의 공간 은 처음에 maxn * 20 을 열 었 는데 그 결과 RE 와 WA 가 되 어 * 30 이 되면 지나 갑 니 다................................................
Code：

#include
#include
#include
#include
#define LL long long
#define maxn 200005
#define maxm 500005
#define maxp maxn*30
using namespace std;
char cb[1<<18],*cs,*ct;
#define getc() (cs==ct&&(ct=(cs=cb)+fread(cb,1,1<<18,stdin),cs==ct)?0:*cs++)
inline void read(int &a){
	char c;while(!isdigit(c=getc()));
	for(a=c-'0';isdigit(c=getc());a=a*10+c-'0');
}
int n,m,Q,ans,h[maxn],f[maxn][20],F[maxn];
struct node{
	int x,y,z;
	bool operator < (const node &p)const{return z<p.z;}
}e[maxm];
int find(int x){return x==F[x]?x:F[x]=find(F[x]);}
int search(int x,int v){
	for(int i=17;i>=0;i--) if(h[f[x][i]]<=v) x=f[x][i];
	return x;
}
int rt[maxn],lc[maxp],rc[maxp],s[maxp],id[maxp],tot;
void insert(int &now,int l,int r,int x){
	s[++tot]=s[now]+1,lc[tot]=lc[now],rc[tot]=rc[now];
	now=tot;
	if(l==r) return;
	int mid=(l+r)>>1;
	if(x<=mid) insert(lc[now],l,mid,x);
	else insert(rc[now],mid+1,r,x);
}
void merge(int &now,int x,int y){
	if(!x||!y) now=x+y;
	else{
		s[now=++tot]=s[x]+s[y];
		merge(lc[now],lc[x],lc[y]);
		merge(rc[now],rc[x],rc[y]);
	}
}
int query(int now,int l,int r,int k){
	if(l==r) return l;
	int mid=(l+r)>>1;
	if(k<=s[lc[now]]) return query(lc[now],l,mid,k);
	else return query(rc[now],mid+1,r,k-s[lc[now]]);
}
int main()
{
	#ifndef ONLINE_JUDGE
		freopen("H.in","r",stdin);
	#endif
	int x,y,k;
	read(n),read(m),read(Q);
	for(int i=1;i<=n;i++) read(h[i]),insert(rt[i],1,1e9,h[i]);
	for(int i=1;i<=m;i++) read(e[i].x),read(e[i].y),read(e[i].z);
	sort(e+1,e+1+m);
	for(int i=1;i<=n;i++) F[i]=i;
	for(int i=1;i<=m;i++){
		x=find(e[i].x),y=find(e[i].y);
		if(x!=y){
			++n,F[n]=F[x]=F[y]=f[x][0]=f[y][0]=n;
			h[n]=e[i].z,merge(rt[n],rt[x],rt[y]);
		}
	}
	h[0]=1<<30;
	for(int j=1;j<=17;j++)
		for(int i=1;i<=n;i++)
			f[i][j]=f[f[i][j-1]][j-1];
	while(Q--){
		read(x),read(y),read(k);
		if(ans>0) x^=ans,y^=ans,k^=ans;
		x=search(x,y);
		if(s[rt[x]]<k) printf("%d
",ans=-1);
		else printf("%d
",ans=query(rt[x],1,1e9,s[rt[x]]-k+1));
	}
}