洛谷P4197 Peaks(Kruskal重构树 主席树)-程序员宅基地

题意

题目链接

往后中文题就不翻译了qwq

Sol

又是码农题。。出题人这是强行把Kruskal重构树和主席树拼一块了啊。。

首先由于给出的限制条件是<=x,因此我们在最小生成树上走一定是最优的。

考虑把Kruskal重构树建出来,重构树上每个新的节点代表的是边权,同时用倍增数组维护出跳2^i步后能走到的值最大的节点

这样,该节点的整个子树内的节点都是可以走到的。

用dfs序+主席树维护出每个节点内H的值,直接查第K大即可

需要注意的是,对于不在原树内的节点,H要设的非常小,或者不插入,以免对答案产生影响

同时H需要离散化

写+调用了整两个小时,,自己的码力还是太弱了qwq

#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;
inline int read() {
    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);
    tot = N = read(); M = read(); Q = read();
    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++) {
        int x = read(), y = read(), z = read();
        // v[x].push_back(MP(y, z));
        // v[y].push_back(MP(x, z));
        AddEdge(x, y, z); AddEdge(y, x, z);
    }
    Build();
    dfs(tot, 0);
    MakeTree();
    Jump();
    while(Q--) {
        int v = read(), x = read(), k = read();
        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;
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_33857230/article/details/86016056

智能推荐

PTA 7-5 成绩排序_把成绩单按分数从高到低的顺序进行排序并输出,成绩之间有一个空格,最后的成绩后没-程序员宅基地

该文章是关于对班里学生某门课程成绩进行排序的问题。要求对班里的学生按照成绩从高到低排序输出。输入包括学生数目和每个学生的成绩,输出为按成绩从高到低的排序结果。

Elasticsearch 解决集群 Yellow 与 Red 的问题_es yellow删除索引-程序员宅基地

文章浏览阅读963次。集群健康度分片健康红:至少有一个主分片没有分配黄:至少有一个副本没有分配绿:主副本分片全部正常分配索引健康:最差的分片的状态集群健康:最差的索引的状态Health 相关的 APIGET _cluster/health集群的状态(检查 节点数量)GET _cluster/health?level=indices所有索引的健康状态 (查看有问题的索引GET _cluster/health/my_index单个索引的健康状态(查看具体的索引)GET _cl_es yellow删除索引

关于图片大小的理解_图片数据像素点占比多少-程序员宅基地

文章浏览阅读559次。A:透明度R:红色G:绿B:蓝Bitmap.Config ARGB_4444:每个像素占四位,即A=4,R=4,G=4,B=4,那么一个像素点占4+4+4+4=16位 Bitmap.Config ARGB_8888:每个像素占四位,即A=8,R=8,G=8,B=8,那么一个像素点占8+8+8+8=32位Bitmap.Config RGB_565:每个像素占四位,即R=5,G_图片数据像素点占比多少

Ueditor自定义上传文件通过SpringMVC上传图片到FTP_ueditor 上传图片 spring-程序员宅基地

文章浏览阅读512次。一、修改Ueditor的config.json的文档图片访问路径前缀改成FTP对外暴露的访问地址"imageUrlPrefix": "http://192.168.85.98:8280/up/"二、初始化Ueditor时绑定自定义文件上传方法<!-- 富文本编辑器 --><div id="content"> <script id="edit..._ueditor 上传图片 spring

STM32芯片的DFU编程及相关话题_syscfg_memoryremapconfig( syscfg_memoryremap_sram -程序员宅基地

文章浏览阅读2.2k次。相当部分的 STM32芯片都带USB模块,有时我们会考虑利用STM32芯片的USB模块进行程序代码的下载或升级。USB协议中有专门针对设备固件升级的类协议,即可以通过DFU类协议进行产品固件的加载或更新。 关于STM32产品的DFU程序下载和升级,ST官方有相关的资料文档。可以去www.stmcu.com.cn 或者去www.st.com 搜索DFUse下载相关资料。_syscfg_memoryremapconfig( syscfg_memoryremap_sram )作用是什么;

关于利用shell实现ftp_shell标本实现ftp-程序员宅基地

文章浏览阅读904次。过去,我是在写expect脚本来实现自动登陆并上传下载文件。不过略感不顺。参考文档:http://blog.chinaunix.net/uid-20526681-id-3549245.html现在有一个好的方法cd 到本地你要上传或下载的目录中ftp -niv &lt;&lt; EOFopen ip_addressuser username passwordasciiput filen..._shell标本实现ftp

随便推点

BERT跨模态之后:占领了视觉常识推理任务榜单TOP 2!-程序员宅基地

文章浏览阅读388次。星标/置顶小屋,带你解锁最萌最前沿的NLP、搜索与推荐技术文 | 小鹿鹿lulu编 | YY前言由于 BERT-like 模型在 NLP 领域上的成功,研究者们开始尝试将其应用到更为复杂..._bert进行知识推理

Java微笔记(7)-程序员宅基地

文章浏览阅读45次。String 类常用方法注意点:字符串 str 中字符的索引从0开始,范围为 0 到 str.length()-1使用 indexOf 进行字符或字符串查找时,如果匹配返回位置索引;如果没有匹配结果,返回 -1使用 substring(beginIndex , endIndex) 进行字符串截取时,包括 beginIndex 位置的字符,不包括 endIndex 位置的字符“==” ...

AMA回顾|ENVELOP 将在本周首次部署,十月将有大动作_envelop上了几个平台-程序员宅基地

文章浏览阅读334次。9月29日,ENVELOP项目在Crypto Horses社区举办了AMA活动,与5万多位社群成员分享了项目进展。项目CEOAlex Shedogubov与大家积极互动交流,一起探讨项目发展与治理。嘉宾及项目介绍Hi there! I am Alex Shedogubov and I am a CEO in ENVELOP. I manage the project and the product development. I have more than 8 years of mana..._envelop上了几个平台

Python中的f字符串的用法_python f-程序员宅基地

文章浏览阅读3.4w次,点赞26次,收藏131次。Python中的f字符串的用法:要在字符串中插入变量的值,可在前引号前加上字母f,再将要插入的变量放在花括号内。举例子如下:first_name="ada"last_name="lovelace"full_name=f"{first_name}{last_name}"print(f"Hello,{full_name.title()}!")打印结果为:Hello,Ada Lovelace!还可以使用f字符串来创建消息,再把整条消息赋给变量:举例子:first_name=_python f

如何在react-native实现自定义的垂直方向跑马灯_react-native-anchor-carousel 竖向-程序员宅基地

文章浏览阅读2.9k次。项目需求是需要实现一个垂直方向的跑马灯轮播,早期采用react-native-swiper解决方案,此方案在ios端正常使用,在android端不能使用,所有果断放弃。第二方案打算使用ant-mobile的Carousel组件,import { Carousel, WingBlank } from 'antd-mobile';import { Text } from 'react-nat..._react-native-anchor-carousel 竖向

无线电A类考试试题_a类无线电考试卷-程序员宅基地

文章浏览阅读2k次,点赞2次,收藏2次。[I]LK0001[Q]我国现行法律体系中专门针对无线电管理的最高法律文件及其立法机关是:[A]中华人民共和国无线电管理条例,国务院和中央军委[B]中华人民共和国无线电管理办法,工业和信息化部[C]中华人民共和国电信条例,国务院[D]中华人民共和国业余无线电台管理办法,工业和信息化部[P][I]LK0002[Q]我国现行法律体系中专门针对业余无线电台管理的最高法律文件及其立法机关是:[A]业余无线电台管理办法,工业和信息化部[B]个人业余无线电台管理暂行办法,国家体委和国家无委[C]业_a类无线电考试卷