3545: [ONTAK2010]Peaks
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 835 Solved: 240
[Submit][Status][Discuss]
Description
在Bytemountains有N座山峰，每座山峰有他的高度h_i。有些山峰之间有双向道路相连，共M条路径，每条路径有一个困难值，这个值越大表示越难走，现在有Q组询问，每组询问询问从点v开始只经过困难值小于等于x的路径所能到达的山峰中第k高的山峰，如果无解输出-1。
Input
第一行三个数N，M，Q。
第二行N个数，第i个数为h_i
接下来M行，每行3个数a b c，表示从a到b有一条困难值为c的双向路径。
接下来Q行，每行三个数v x k，表示一组询问。
Output
对于每组询问，输出一个整数表示答案。
Sample Input
10 11 4
1 2 3 4 5 6 7 8 9 10
1 4 4
2 5 3
9 8 2
7 8 10
7 1 4
6 7 1
6 4 8
2 1 5
10 8 10
3 4 7
3 4 6
1 5 2
1 5 6
1 5 8
8 9 2
1 2 3 4 5 6 7 8 9 10
1 4 4
2 5 3
9 8 2
7 8 10
7 1 4
6 7 1
6 4 8
2 1 5
10 8 10
3 4 7
3 4 6
1 5 2
1 5 6
1 5 8
8 9 2
Sample Output
6
1
-1
8
1
-1
8
HINT
【数据范围】
N<=10^5, M,Q<=5*10^5，h_i,c,x<=10^9。
Source
显然对于求可以到达的所有点我们可以将询问离线后从小到大排序。。然后依次加边用并查集维护联通块。。
对于求第k大的值可以用平衡树维护。。然后加在一起就是离线询问启发式合并平衡树。。。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 500010;
struct data{int x,y,s;} e[N];
struct data1{int v,x,k,id,ans;} q[N];
struct node *null,*rt,*rt1,*rt2;
int n,m,Q,val[N],x,y,s,pos,cnt,f[N];
struct node{
node *L,*R,*Fa;
int S,val;
void Update(){if (this==null) return;S = L->S+R->S+1;}
void Zig(){
node *y = Fa,*z = y->Fa;
if (z->L==y) z->L = this;else z->R = this;Fa = z;
y->L = R;if (R!=null) R->Fa = y;
y->Fa = this;R = y;y->Update();
}
void Zag(){
node *y = Fa,*z = y->Fa;
if (z->L==y) z->L = this;else z->R = this;Fa = z;
y->R = L;if (L!=null) L->Fa =y;
y->Fa = this;L = y;y->Update();
}
} Nd[N];
bool cmpval(data1 a,data1 b){return a.x<b.x;}
bool cmpid(data1 a,data1 b){return a.id<b.id;}
bool cmp(data a,data b){return a.s<b.s;}
int read(){
int x = 0,f = 1,c = getchar();
while (c<'0' || c>'9') {if (c=='-') f = -1;c = getchar();}
while (c>='0' && c<='9') x = x*10+c-'0',c = getchar();
return x*f;
}
void Splay(node *x,node *Aim){
while (x->Fa!=Aim){
node *y = x->Fa,*z = y->Fa;
if (z!=Aim)
if (y->L==x) if (z->L==y) y->Zig(),x->Zig();else x->Zig(),x->Zag();
else if (z->R==y) y->Zag(),x->Zag();else x->Zag(),x->Zig();
else if (y->L==x) x->Zig();else x->Zag();
}
x->Update();
}
void Insert(node *x,node *t){
if (t->val>=x->val){
if (x->L==null) {t->Fa = x;x->L = t;Splay(t,null);rt1 = t;return;}
else Insert(x->L,t);
}
else {
if (x->R==null) {t->Fa = x;x->R = t;Splay(t,null);rt1 = t;return;}
else Insert(x->R,t);
}
}
void print(node *x){
if (x==null) return;
print(x->L);printf("%d ",x->val);print(x->R);
}
node* findkth(node *x,int k){
if (x->L->S+1==k) return x;
return x->L->S+1>k?findkth(x->L,k):findkth(x->R,k-x->L->S-1);
}
void dfs(node *x){
if (x==null) return;
dfs(x->L);dfs(x->R);
x->L = x->R = null;x->S = 1;
Insert(rt1,x);
}
int get(int x){return x==f[x]?x:f[x] = get(f[x]);}
void work(int x,int y){
int fx = get(x),fy = get(y);
if (fx==fy) return;else f[fx] = fy;
rt1 = Nd+x;rt2 = Nd+y;
Splay(rt1,null);Splay(rt2,null);
if (rt1->S<rt2->S) swap(rt1,rt2);
dfs(rt2);
//print(rt1);printf("\n");
}
int Query(int x,int k){
rt = Nd+x;Splay(rt,null);
if (rt->S<k) return -1;
else return findkth(rt,k)->val;
}
int main(){
null = Nd;
n = read();m = read();Q = read();
for (int i=1;i<=n;i++) val[i] = read();
for (int i=1;i<=n;i++) f[i] = i;
for (int i=0;i<=n;i++) Nd[i] = (node){null,null,null,1,val[i]};
null->S = 0;
for (int i=1;i<=m;i++){
x = read();y = read();s = read();
e[++cnt] = (data){x,y,s};
}
sort(e+1,e+1+cnt,cmp);
for (int i=1;i<=Q;i++) q[i].v = read(),q[i].x = read(),q[i].k = read(),q[i].id = i;
sort(q+1,q+1+Q,cmpval);
pos = 1;
for (int i=1;i<=Q;i++){
while (e[pos].s<=q[i].x && pos<=cnt) work(e[pos].x,e[pos].y),pos++;
q[i].ans = Query(q[i].v,q[i].k);
}
sort(q+1,q+1+Q,cmpid);
for (int i=1;i<=Q;i++) printf("%d\n",q[i].ans);
}
评论 (0)
