# 洛谷P4197 Peaks(Kruskal重构树 主席树)

## Sol

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#define Pair pair<int, int>
#define MP(x, y) make_pair(x, y)
#define fi first
#define se second
using namespace std;
const int MAXN = 1e6 + 10;
char c = getchar(); int x = 0, f = 1;
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;
}
int N, M, Q, H[MAXN], date[MAXN], tot, num = 0;
struct Edge {
int u, v, w;
bool operator < (const Edge &rhs) const {
return w < rhs.w;
}
}E[MAXN];
void AddEdge(int x, int y, int z) {E[++num] = (Edge) {x, y, z};}
int fa[MAXN], fd[MAXN][22], dis[MAXN][22];
int find(int x) {
if(fa[x] == x) return fa[x];
else return fa[x] = find(fa[x]);
}
int unionn(int x, int y) {fa[x] = y;}
vector<int> v[MAXN];
void Build() {
for(int i = 1; i <= (N << 1); i++) fa[i] = i;
sort(E + 1, E + num + 1);
for(int i = 1; i <= num; i++) {
int x = E[i].u, y = E[i].v, w = E[i].w;
int fx = find(x), fy = find(y);
if(fx == fy) continue;
tot++;
fa[fx] = tot; fa[fy] = tot;
v[fx].push_back(tot); v[fy].push_back(tot);
v[tot].push_back(fx); v[tot].push_back(fy);
dis[fx][0] = w; dis[fy][0] = w;
fd[fx][0] = tot; fd[fy][0] = tot;
if(tot == 2 * N - 1) break;
}
}
int ls[MAXN * 30], rs[MAXN * 30], Tsiz[MAXN * 30], root[MAXN], cnt, siz[MAXN], dfn[MAXN], tra[MAXN];
void dfs(int x, int fa) {
dfn[x] = ++cnt; tra[dfn[x]] = x; siz[x] = 1;
for(int i = 0; i < v[x].size(); i++) {
int to = v[x][i];
if(to == fa) continue;
dfs(to, x);
siz[x] += siz[to];
}
}
void update(int k) {
Tsiz[k] = Tsiz[ls[k]] + Tsiz[rs[k]];
}
void Insert(int &k, int p, int val, int l, int r) {
k = ++cnt;
ls[k] = ls[p]; rs[k] = rs[p]; Tsiz[k] = Tsiz[p];
if(val == -1) return ;
Tsiz[k]++;
if(l == r) return ;
int mid = l + r >> 1;
if(val <= mid) Insert(ls[k], ls[p], val, l, mid);
else Insert(rs[k], rs[p], val, mid + 1, r);
update(k);
}
void MakeTree() {
cnt = 0;
for(int i = 1; i <= tot; i++)
Insert(root[i], root[i - 1], H[tra[i]], 1, N);
}
void Jump() {
for(int j = 1; j <= 21; j++) {
for(int i = 1; i <= tot; i++) {
fd[i][j] = fd[fd[i][j - 1]][j - 1];
dis[i][j] = max(dis[fd[i][j - 1]][j - 1], dis[i][j - 1]);
}
}
}
int Get(int x, int val) {
for(int i = 21; i >= 0; i--)
if(dis[x][i] <= val && fd[x][i] != 0)
x = fd[x][i];
return x;
}
int Query(int lt, int rt, int k, int l, int r) {
int used = Tsiz[rs[rt]] - Tsiz[rs[lt]];
if(l == r) {
if(Tsiz[rt] - Tsiz[lt] < k) return -1;
else return l;
}
int mid = l + r >> 1;
if(k <= used) return Query(rs[lt], rs[rt], k, mid + 1, r);
else return Query(ls[lt], ls[rt], k - used, l, mid);
}
main() {
//freopen("1.in", "r", stdin);
//freopen("a.out", "w", stdout);
memset(H, -1, sizeof(H));
for(int i = 1; i <= N; i++) H[i] = read(), date[i] = H[i];
sort(date + 1, date + N + 1);
int tmp = unique(date + 1, date + N + 1) - date - 1;
for(int i = 1; i <= N; i++) H[i] = lower_bound(date + 1, date + N + 1, H[i]) - date;
for(int i = 1; i <= M; i++) {
// v[x].push_back(MP(y, z));
// v[y].push_back(MP(x, z));
}
Build();
dfs(tot, 0);
MakeTree();
Jump();
while(Q--) {
int top = Get(v, x);
int l = dfn[top], r = dfn[top] + siz[top] - 1;
int ans = Query(root[l], root[r], k, 1, N);
if(ans == -1) printf("%d\n", -1);
else printf("%d\n", date[ans]);
}
return 0;
}

0 条评论

• ### BZOJ5249: [2018多省省队联测]IIIDX(线段树 贪心)

不难发现题目给出的是一个树，其中$$\frac{i}{K}$$是$$i$$的父亲节点

• ### P1967 货车运输 未完成

1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<c...

• ### loj#6436. 「PKUSC2018」神仙的游戏(生成函数)

我们考虑枚举一个长度len。有一个结论是如果我们按N - len的余数分类，若同一组内的全为0或全为1(?不算)，那么存在一个长度为len的border。

• ### C++ 函数指针的定义方法及使用

第一种，c语言通用。定义一个process_job函数指针类型，返回值为 int ,函数参数为int a,int b。使用用两种方法。

• ### ICPC Asia Shenyang 2019 Dudu's maze

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

• ### 学生时代所学的一些 C 语言知识点回顾（1）

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

• ### Educational Codeforces Round 67 (Rated for Div. 2) A~E 贪心，构造，线段树，树的子树

Educational Codeforces Round 67 (Rated for Div. 2)

• ### LeetCode 164. Maximum Gap (排序)

题解：首先，当然我们可以用快排，排完序之后，遍历一遍数组，就能得到答案了。但是快速排序的效率是O(n* logn)，不是题目要求的线性效率，也就是O(n)的效率...

• ### 位操作运算有什么奇技淫巧?(附源码)

比如说16位二进制数A：1001 1001 1001 1000，如果来你想获A的哪一位的值,就把数字B：0000 0000 0000 0000的那一位设置为1.

• ### 浙大版《C语言程序设计（第3版）》题目集 习题6-2 使用函数求特殊a串数列和

给定两个均不超过9的正整数a和n，要求编写函数求a+aa+aaa++⋯+aa⋯a（n个a）之和。