首页 > 其他分享 >[luoguP1456] Monkey King

[luoguP1456] Monkey King

时间:2024-11-07 21:46:04浏览次数:1  
标签:King dist Monkey fa int tr 集合 luoguP1456 return

题意

给出 \(n\) 个集合 \(S_1 \cdots S_n\),\(S_i = \{a_i\}\),每次给出 \(x,y\),将第 \(x\) 和第 \(y\) 个元素所在的集合的最大值 \(\div 2\),合并两个集合,然后输出新集合的最大值。

sol

每次求出两个集合,记录两个集合的最大值并删除,将两个集合与两个最大值除以 \(2\) 后合并即可。考虑左偏树(可并堆),思路参见 [luoguP3377] 左偏树/可并堆
注意多测要清空

代码

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 100005;

struct Node {
    int l, r;
    int val;
    int dist;
}tr[N];

int n, m;
int fa[N];

int find(int x){
    if (x == fa[x]) return x;
    return fa[x] = find(fa[x]);
}

int merge(int x, int y){
    if (!x || !y) return x | y;
    if (tr[x].val < tr[y].val) swap(x, y);
    tr[x].r = merge(tr[x].r, y);
    if (tr[tr[x].l].dist < tr[tr[x].r].dist) swap(tr[x].l, tr[x].r);
    tr[x].dist = tr[tr[x].r].dist + 1;
    return x;
}

int main(){
    while (scanf("%d", &n) != EOF){
        for (int i = 1; i <= n; i ++ ) scanf("%d", &tr[i].val), tr[i].l = tr[i].r = tr[i].dist = 0, fa[i] = i;

        scanf("%d", &m);
        while (m -- ){
            int x, y;
            scanf("%d%d", &x, &y);

            int fx = find(x), fy = find(y);
            if (fx == fy) puts("-1");
            else {
                int rtx = merge(tr[fx].l, tr[fx].r), rty = merge(tr[fy].l, tr[fy].r);
                tr[fx].val /= 2, tr[fy].val /= 2;
                tr[fx].dist = tr[fy].dist = 0;
                int xl = tr[fx].l, xr = tr[fx].r, yl = tr[fy].l, yr = tr[fy].r;
                tr[fx].l = tr[fx].r = tr[fy].l = tr[fy].r = 0;
                fa[fx] = fa[fy] = fa[xl] = fa[xr] = fa[yl] = fa[yr] = merge(merge(rtx, fx), merge(rty, fy));
                printf("%d\n", tr[fa[fx]].val);
            }
        }
    }
}

标签:King,dist,Monkey,fa,int,tr,集合,luoguP1456,return
From: https://www.cnblogs.com/XiaoJuRuoUP/p/-/luoguP1456

相关文章

  • SCC.369 Working with GPIO Moodle
    SCC.369Coursework1:WorkingwithGPIO Moodlesubmission16:00Fridayweek4;weighting33%ofmodule.AimHavingfamiliarizedyourselfwiththeCdevelopmentenvironmentandthebasicprocessofwritingtoregisterstocontroltheGPIOpins,inthiscour......
  • 49_api_intro_stock_fund_fundopenrankinglist
    开放式基金实时排行API数据接口多维度参数返回,实时数据,类型参数筛选。1.产品功能返回实时开放式基金排行数据可定义查询基金类型参数;多个基金属性值返回多维指标,一次查询毫秒级返回;数据持续更新与维护;全接口支持HTTPS(TLSv1.0/v1.1/v1.2/v1.3);全面兼容Apple......
  • 46_api_intro_stock_fund_fundetfopenrankinglist
    开放式场内交易基金排行API数据接口多维度参数返回,实时数据,返回多维度指数。1.产品功能返回实时开放式ETF基金排行数据多个基金属性值返回多维指标,一次查询毫秒级返回;数据持续更新与维护;全接口支持HTTPS(TLSv1.0/v1.1/v1.2/v1.3);全面兼容AppleATS;全国多节......
  • yolov8目标跟踪与行人车辆计数+YOLOv8 Object Detection with DeepSORT Tracking(ID +
    YOLOv8目标检测与DeepSORT跟踪技术简介在计算机视觉领域,目标检测和跟踪是两个至关重要的任务。目标检测旨在识别图像或视频中的特定对象,并确定它们的位置;而目标跟踪则是在连续的帧之间保持对这些对象的身份和位置的一致性跟踪。本文将详细介绍YOLOv8作为先进的目标检测算法......
  • Centos安装KingBase
    文章目录1远程下载KingBase的授权文件、iso包2添加用户,创建目录3解压KingBase的授权文件,挂载iso包4授权目录5控制台安装6注册服务7修改配置文件8重启服务附录-bash:wget:未找到命令查看Linux系统的架构参考文档1远程下载KingBase的授权文件、iso包[root......
  • IMSE7140 Cracking CAPTCHAs
    IMSE7140Assignment2CrackingCAPTCHAs(20points)2.1BriefIntroductionCAPTCHAorcaptchaistheacronymfor“CompletelyAutomatedPublicTuringtesttotellComputersandHumansApart.”Youmusthavebeenalreadyfamiliarwithitbecauseofitspopu......
  • KingbaseES V8R6集群备份恢复案例之---主库single-pro备份恢复
    案例说明:KingbaseESV8R6集群物理备份支持single-pro方式,本案例在集群执行single-pro方式备份并多次切换集群后,对集群执行了恢复测试,文档记录了恢复的详细过程。适用版本:KingbaseESV8R6集群架构:ID|Name|Role|Status|Upstream|repmgrd|PID|Paused?|......
  • C语言的一些Hacking写法
    很显然,这些写法大多并不规范,也不被提倡。很显然,咱并没有在windows下试过这些代码,而且实测大部分在线编程网站用的是Linux,可以接受GNUC扩展支持。如果有人问我为什么折腾,为什么以折腾这些无聊的东西作为目标,那他们完全可以问,为什么要登上最高峰?为什么人类要登月?………我选择去折......
  • 【红队】利用 PsycheShell 进行 Paste Jacking 以获取隐秘的反向 Shell
    原创Ots安全介绍在网络安全领域,粘贴劫持(PasteJacking)等技术代表着社会工程攻击日益复杂的趋势。当用户从网页上复制看似无害的内容,但粘贴的内容却遭到恶意篡改时,就会发生粘贴劫持。攻击者可以使用此技术在目标机器上执行命令,尤其是当用户粘贴到终端等敏感环境中时。在本......
  • Meta-Chunking:一种用于提高RAG性能的文本分割技术
    尽管RAG技术在LLMs中具有潜力,但在文本分块方面常常被忽视。文本分块的质量直接影响知识密集型任务的表现。本文提出Meta-Chunking概念,这是一种介于句子和段落之间的文本分割技术,旨在通过逻辑感知来提高文本分割的效率;设计了两种基于LLMs的分块策略:边际采样分块(MarginSam......