[ONTAK2010] Peaks
题目大意：有\(n\)个不同高度的山峰，\(m\)条带权无向边，\(q\)个询问，询问从山峰\(a\)点开始只经过权值小于等于\(b\)的路径所能到达的山峰中第\(k\)高的山峰，如果无解输出\(-1\)。
Solution
算法流程如下：
- 输入山峰高度，从低到高排序，用序号代替具体值来离散。
- 对于每一个山峰建立一颗权值线段树
- 输入\(m\)条边和\(q\)个询问，存在同一个数组中按照边权来排序从小到大排序，因为如果之前的边都满足不了此次询问，那么后面的边权更大，对于这次询问来说是无效的
遍历边和询问,
- 对于边，如果指向的两个点还不在一个线段树里，那么就合并线段树(别忘记合并并查集），如果指向的两个点已经在一个线段树里了，就跳过，因为之前那次合并一定是最短的
- 对于询问，就是查找\(a\)点的权值线段树中的第\(k\)高,因为我们排了序，所以就消去了对于边权的限制
输出询问的答案
注意，询问是要标注\(id\)的.
Attention
- 线段树合并的空间复杂度是\(n\cdot (log_2^n+1)\)
因为合并的过程并没有新开节点，一开始每个元素都是单独的一颗线段树，每个元素开的空间是一条树链 ，树链长度是 \(log_2^n+1\)的,最多把所有树链合并起来，所以空间复杂度是\(n\cdot (log_2^n+1)\)
Code
#include#include #include #include #define sc(x) scanf("%d", &x)#define pf(x) printf("%d\n",x)using std::sort;const int M = 1e6 + 10;const int N = 1e5 + 10;struct Hill{ int hi, id; bool operator < (const Hill &cmp) const { return hi < cmp.hi; }}h[N];struct Aha{ int a, b, c, f, id; bool operator < (const Aha &cmp) const { if(c == cmp.c) return f < cmp.f; else return c < cmp.c; }}a[M];int n, m, q, cnt;int root[N], fa[N], sum[2000005], lson[2000005], rson[2000005], ans[M];int find(int x){ if(x == fa[x]) return x; return fa[x] = find(fa[x]);}void insert(int &cur, int l, int r, int pos){//int cur if(!cur) cur = ++cnt; sum[cur] ++;//说明这个子树上包含的山加一 if(l == r) return;//到了底 int mid = l + ((r - l) >> 1); if(pos <= mid)//说明应该在左子树 insert(lson[cur], l, mid, pos); else insert(rson[cur], mid + 1, r, pos);}int merge(int x, int y){ if(!x) return y; if(!y) return x; sum[x] += sum[y]; lson[x] = merge(lson[x], lson[y]); rson[x] = merge(rson[x], rson[y]); return x;}int query(int cur, int l, int r, int k){ if(l == r) return l; int mid = l + ((r - l) >> 1); if(sum[lson[cur]] >= k) return query(lson[cur], l, mid, k); else return query(rson[cur], mid + 1, r, k - sum[lson[cur]]);}int main(){ scanf("%d %d %d", &n, &m, &q); for(int i = 1; i <= n; ++i) sc(h[i].hi), h[i].id = i, fa[i] = i; sort(h + 1, h + 1 + n); for(int i = 1; i <= n; ++i) insert(root[h[i].id], 1, n, i); for(int i = 1; i <= m; ++i){ sc(a[i].a); sc(a[i].b); sc(a[i].c); a[i].f = 0; } for(int i = m + 1; i <= m + q; ++i){ sc(a[i].a); sc(a[i].c); sc(a[i].b);//和上面不一样，排序的是不能超过的难度值 a[i].f = 1; a[i].id = i; } sort(a + 1, a + m + q + 1); for(int i = 1, fx, fy; i <= m + q; ++i){ if(!a[i].f){//如果是边 fx = find(a[i].a); fy = find(a[i].b); if(fx == fy) continue; root[fx] = merge(root[fx], root[fy]); fa[fy] = fx; } else { fx = find(a[i].a); if(sum[root[fx]] < a[i].b){ ans[a[i].id] = -1; continue;// } ans[a[i].id] = query(root[fx], 1, n, sum[root[fx]] - a[i].b + 1);//root[root[fx]] } } for(int i = m + 1; i <= m + q; ++i){ if(ans[i] == -1){ puts("-1"); continue; }// pf(h[ans[i]].hi);//ans[i]; } return 0;}