[BZOJ3545][ONTAK2010]Peaks

[BZOJ3545][ONTAK2010]Peaks

試題描述

在Bytemountains有N座山峰，每座山峰有他的高度h_i。有些山峰之間有雙向道路相連，共M條路徑，每條路徑有一個困難值，這個值越大表示越難走，現在有Q組詢問，每組詢問詢問從點v開始只經過困難值小于等于x的路徑所能到達的山峰中第k高的山峰，如果無解輸出-1。

輸入

第一行三個數N，M，Q。
第二行N個數，第i個數為h_i
接下來M行，每行3個數a b c，表示從a到b有一條困難值為c的雙向路徑。
接下來Q行，每行三個數v x k，表示一組詢問。

輸出

對于每組詢問，輸出一個整數表示答案。

輸入示例

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

輸出示例

6
1
-1
8

數據規模及約定

N<=10^5, M,Q<=5*10^5，h_i,c,x<=10^9。

題解

考慮離線做法，我們把邊和詢問按權值排一遍序，然后依次處理每個詢問。那么就是從小到大依次加入那些邊，對于連通性，我們可以用并查集維護；對于第 k 大值，我們可以并查集里面套一個 treap；啊 treap 怎么合并？只好加一個 log 啟發式合并了。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <stack>
#include <vector>
#include <queue>
#include <cstring>
#include <string>
#include <map>
#include <set>
using namespace std;const int BufferSize = 1 << 16;
char buffer[BufferSize], *Head, *Tail;
inline char Getchar() {if(Head == Tail) {int l = fread(buffer, 1, BufferSize, stdin);Tail = (Head = buffer) + l;}return *Head++;
}
int read() {int x = 0, f = 1; char c = Getchar();while(!isdigit(c)){ if(c == '-') f = -1; c = Getchar(); }while(isdigit(c)){ x = x * 10 + c - '0'; c = Getchar(); }return x * f;
}#define maxn 100010
#define maxm 500010
struct Node {int v, r, siz;Node() {}Node(int _, int __): v(_), r(__) {}
} ns[maxn];
int ToT, fa[maxn], ch[maxn][2], rec[maxn], rcnt;
int getnode() {if(rcnt) {int o = rec[rcnt--];fa[o] = ch[o][0] = ch[o][1] = 0;return o;}return ++ToT;
}
void maintain(int o) {ns[o].siz = 1;for(int i = 0; i < 2; i++) if(ch[o][i])ns[o].siz += ns[ch[o][i]].siz;return ;
}
void rotate(int u) {int y = fa[u], z = fa[y], l = 0, r = 1;if(z) ch[z][ch[z][1]==y] = u;if(ch[y][1] == u) swap(l, r);fa[u] = z; fa[y] = u; fa[ch[u][r]] = y;ch[y][l] = ch[u][r]; ch[u][r] = y;maintain(y); maintain(u);return ;
}
void insert(int& o, int v) {if(!o) {ns[o = getnode()] = Node(v, rand());return maintain(o);}bool d = v > ns[o].v;insert(ch[o][d], v); fa[ch[o][d]] = o;if(ns[ch[o][d]].r > ns[o].r) {int t = ch[o][d];rotate(t); o = t;}return maintain(o);
}
int val[maxn], cntv;
void recycle(int& o) {if(!o) return ;recycle(ch[o][0]); recycle(ch[o][1]);rec[++rcnt] = o; val[++cntv] = ns[o].v; fa[o] = 0; o = 0;return ;
}
void merge(int& u, int& v) {
//	printf("merge(%d, %d)\n", u, v);cntv = 0; recycle(v);
//	printf("vals: "); for(int i = 1; i <= cntv; i++) printf("%d%c", val[i], i < cntv ? ' ' : '\n');for(int i = 1; i <= cntv; i++) insert(u, val[i]);return ;
}
int Find(int o, int k) {if(!o) return -1;int rs = ch[o][1] ? ns[ch[o][1]].siz : 0;if(k == rs + 1) return ns[o].v;if(k < rs + 1) return Find(ch[o][1], k);return Find(ch[o][0], k - rs - 1);
}int pa[maxn], rt[maxn];
int findset(int x) { return x == pa[x] ? x : pa[x] = findset(pa[x]); }struct Edge {int a, b, c;Edge() {}Edge(int _1, int _2, int _3): a(_1), b(_2), c(_3) {}bool operator < (const Edge& t) const { return c < t.c; }
} es[maxm];
struct Que {int u, x, k, id;Que() {}Que(int _1, int _2, int _3, int _4): u(_1), x(_2), k(_3), id(_4) {}bool operator < (const Que& t) const { return x < t.x; }
} qs[maxm];
int ans[maxm];int main() {int n = read(), m = read(), q = read();for(int i = 1; i <= n; i++) {int v = read();pa[i] = i; insert(rt[i], v);}for(int i = 1; i <= m; i++) {int a = read(), b = read(), c = read();es[i] = Edge(a, b, c);}sort(es + 1, es + m + 1);for(int i = 1; i <= q; i++) {int u = read(), x = read(), k = read();qs[i] = Que(u, x, k, i);}sort(qs + 1, qs + q + 1);//	for(int i = 1; i <= m; i++) printf("Edge: %d %d %d\n", es[i].a, es[i].b, es[i].c);
//	for(int i = 1; i <= q; i++) printf("Que: %d %d %d\n", qs[i].u, qs[i].x, qs[i].k);for(int i = 1, e = 1; i <= q; i++) {while(e <= m && es[e].c <= qs[i].x) {int u = findset(es[e].a), v = findset(es[e].b);
//			printf("%d: %d(%d) %d(%d) %d\n", e, u, es[e].a, v, es[e].b, findset(8));if(u != v) {if(ns[rt[u]].siz < ns[rt[v]].siz) swap(u, v);merge(rt[u], rt[v]);pa[v] = u;}e++;}ans[qs[i].id] = Find(rt[findset(qs[i].u)], qs[i].k);}for(int i = 1; i <= q; i++) printf("%d\n", ans[i]);return 0;
}

在線做法，詳見這里。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <stack>
#include <vector>
#include <queue>
#include <cstring>
#include <string>
#include <map>
#include <set>
using namespace std;const int BufferSize = 1 << 16;
char buffer[BufferSize], *Head, *Tail;
inline char Getchar() {if(Head == Tail) {int l = fread(buffer, 1, BufferSize, stdin);Tail = (Head = buffer) + l;}return *Head++;
}
int read() {int x = 0, f = 1; char c = Getchar();while(!isdigit(c)){ if(c == '-') f = -1; c = Getchar(); }while(isdigit(c)){ x = x * 10 + c - '0'; c = Getchar(); }return x * f;
}#define maxn 200010
#define maxm 500010
#define maxlog 18
#define maxnode 6666666
int n;int ToT, sumv[maxnode], lc[maxnode], rc[maxnode], rt[maxn];
void update(int& y, int x, int l, int r, int p) {sumv[y = ++ToT] = sumv[x] + 1;if(l == r) return ;int mid = l + r >> 1; lc[y] = lc[x]; rc[y] = rc[x];if(p <= mid) update(lc[y], lc[x], l, mid, p);else update(rc[y], rc[x], mid + 1, r, p);return ;
}struct Edge {int a, b, c;Edge() {}Edge(int _1, int _2, int _3): a(_1), b(_2), c(_3) {}bool operator < (const Edge& t) const { return c < t.c; }
} es[maxm];
int p_ToT, fa[maxlog][maxn], ch[maxn][2], p_val[maxn], e_val[maxn], dl[maxn], dr[maxn], clo, pid[maxn];
void build(int u) {if(!u) return ;
//	printf("%d u: %d %d %d\n", e_val[u], u, ch[u][0], ch[u][1]);dl[u] = ++clo; pid[clo] = u;for(int i = 1; i < maxlog; i++) fa[i][u] = fa[i-1][fa[i-1][u]];for(int i = 0; i < 2; i++) build(ch[u][i]);dr[u] = clo;return ;
}int pa[maxn], id[maxn];
int findset(int x) { return x == pa[x] ? x : pa[x] = findset(pa[x]); }int num[maxn];
int query(int u, int mx, int k, int id) {for(int i = maxlog - 1; i >= 0; i--) if(fa[i][u] && e_val[fa[i][u]] <= mx) u = fa[i][u];
//	printf("%d %d\n", u, e_val[u]);int lrt = rt[dl[u]-1], rrt = rt[dr[u]];int l = 1, r = n;while(l < r) {int mid = l + r >> 1;
//		printf("[%d, %d]: %d %d\n", mid + 1, r, sumv[rc[rrt]] - sumv[rc[lrt]], k);if((rrt && rc[rrt] ? sumv[rc[rrt]] : 0) - (lrt && rc[lrt] ? sumv[rc[lrt]] : 0) < k) {k -= sumv[rc[rrt]] - sumv[rc[lrt]]; r = mid;if(lrt) lrt = lc[lrt]; if(rrt) rrt = lc[rrt];}else {l = mid + 1;if(lrt) lrt = rc[lrt]; if(rrt) rrt = rc[rrt];}}int ans = sumv[rrt] - sumv[lrt] >= k ? l : -1;return ans < 0 ? ans : num[ans];
}int main() {freopen("data.in", "r", stdin);freopen("data.out", "w", stdout);n = read(); int m = read(), q = read();for(int i = 1; i <= n; i++) num[i] = p_val[i] = read(), pa[i] = id[i] = i;sort(num + 1, num + n + 1);for(int i = 1; i <= n; i++) p_val[i] = lower_bound(num + 1, num + n + 1, p_val[i]) - num;for(int i = 1; i <= m; i++) {int a = read(), b = read(), c = read();es[i] = Edge(a, b, c);}sort(es + 1, es + m + 1);p_ToT = n;for(int i = 1; i <= m; i++) {int u = findset(es[i].a), v = findset(es[i].b);if(u != v) {ch[++p_ToT][0] = id[u];ch[p_ToT][1] = id[v];fa[0][id[v]] = fa[0][id[u]] = p_ToT;e_val[p_ToT] = es[i].c;pa[v] = u; id[u] = p_ToT;}}build(id[findset(1)]);for(int i = 1; i <= clo; i++)if(p_val[pid[i]]) update(rt[i], rt[i-1], 1, n, p_val[pid[i]]);else rt[i] = rt[i-1];int lst = 0;for(int i = 1; i <= q; i++) {int v = read() ^ lst, x = read() ^ lst, k = read() ^ lst;lst = query(v, x, k, i);printf("%d\n", lst); if(lst < 0) lst = 0;lst = 0;}return 0;
}

?