[BZOJ3123][Sdoi2013]森林(主席树+启发式合并)

news/2024/4/15 13:33:50

首先介绍下树上主席树:
在序列上的主席树,是对序列的每一个前缀都建立一个线段树版本。
而树上主席树,是对树上的每一个节点到根的路径都建立一个线段树版本。
而如果 query(u) 是查询节点 u 到根的路径上的信息,则查询u v 的路径上的信息,就是:
query(u)+query(v)query(lca(u,v))query(fa[lca(u,v)])
这样,就可以在权值线段树上二分,查询路径第 k 小值了。
而最后的问题就是加边。可以考虑启发式合并,也就是把节点数少的树合并到节点数多的树上面去,这样每个节点被合并的次数不超过O(logn)
在合并之后,也必须初始化节点数少的树的倍增LCA数组,以及节点数少的树的线段树版本。所以,一次合并的操作为 O(log2n)
代码:

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
inline int read() {int res = 0; bool bo = 0; char c;while (((c = getchar()) < '0' || c > '9') && c != '-');if (c == '-') bo = 1; else res = c - 48;while ((c = getchar()) >= '0' && c <= '9')res = (res << 3) + (res << 1) + (c - 48);return bo ? ~res + 1 : res;
}
inline char get() {char c; while ((c = getchar()) != 'L' && c != 'Q');return c;
}
const int N = 7e5 + 5, Orz = 2e7 + 5, LogN = 20;
struct cyx {int lc, rc, cnt;
} T[Orz];
int n, m, QAQ, rt[N], sze[N], ecnt, nxt[N], adj[N], go[N], fa[N][LogN],
val[N], RT[N], dep[N], lst;
bool vis[N];
void add_edge(int u, int v) {nxt[++ecnt] = adj[u]; adj[u] = ecnt; go[ecnt] = v;nxt[++ecnt] = adj[v]; adj[v] = ecnt; go[ecnt] = u;
}
void build(int y, int &x, int l, int r, int p) {T[x = ++QAQ] = T[y]; T[x].cnt++;int mid = l + r >> 1; if (l == r) return;if (p <= mid) build(T[y].lc, T[x].lc, l, mid, p);else build(T[y].rc, T[x].rc, mid + 1, r, p);
}
void dfs(int u, int fu, int r) {int i; build(rt[fu], rt[u], 0, 1e9, val[u]); sze[u] = 1; RT[u] = r;dep[u] = dep[fa[u][0] = fu] + 1;for (i = 0; i <= 17; i++) fa[u][i + 1] = fa[fa[u][i]][i];for (int e = adj[u], v; e; e = nxt[e]) {if ((v = go[e]) == fu) continue;dfs(v, u, r); sze[u] += sze[v];}vis[u] = 1;
}
void link(int x, int y) {if (sze[RT[x]] < sze[RT[y]]) swap(x, y);sze[RT[x]] += sze[RT[y]]; dfs(y, x, RT[x]);add_edge(x, y);
}
int lca(int u, int v) {int i; if (dep[u] < dep[v]) swap(u, v);for (i = 18; i >= 0; i--) {if (dep[fa[u][i]] >= dep[v]) u = fa[u][i];if (u == v) return u;}for (i = 18; i >= 0; i--)if (fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];return fa[u][0];
}
int query(int p1, int p2, int p3, int p4, int l, int r, int k) {if (l == r) return l; int mid = l + r >> 1;int delta = T[T[p1].lc].cnt + T[T[p2].lc].cnt- T[T[p3].lc].cnt - T[T[p4].lc].cnt;if (delta >= k)return query(T[p1].lc, T[p2].lc, T[p3].lc, T[p4].lc, l, mid, k);elsereturn query(T[p1].rc, T[p2].rc, T[p3].rc, T[p4].rc, mid + 1, r, k - delta);
}
int ask(int x, int y, int k) {int z = lca(x, y);return query(rt[x], rt[y], rt[z], rt[fa[z][0]], 0, 1e9, k);
}
int main() {int i, x, y, k; read(); n = read(); m = read(); int Q = read();for (i = 1; i <= n; i++) val[i] = read();for (i = 1; i <= m; i++) x = read(), y = read(), add_edge(x, y);for (i = 1; i <= n; i++) if (!vis[i]) dfs(i, 0, i);while (Q--) {char op = get(); x = read() ^ lst; y = read() ^ lst;if (op == 'L') link(x, y);else k = read() ^ lst, printf("%d\n", lst = ask(x, y, k));}return 0;
}

http://www.ppmy.cn/news/846265.html

相关文章

zoj 3123 尺取法

这个也是训练赛上的一个题&#xff0c;当时一看1e9就没有直接爆&#xff0c;记得做过这个题&#xff0c;的确是白书的上一个原题&#xff0c; 这个题需要注意的就是题目的理解&#xff0c;暴力的时候&#xff0c;左右一个标尺&#xff0c;先从右开始&#xff0c;然后逐渐减左标…

bzoj 3123[Sdoi2013]森林 - 树上主席树 + 启发式合并

3123: [Sdoi2013]森林 Time Limit: 20 Sec Memory Limit: 512 MB Description Input 第一行包含一个正整数testcase&#xff0c;表示当前测试数据的测试点编号。保证1≤testcase≤20。 第二行包含三个整数N&#xff0c;M&#xff0c;T&#xff0c;分别表示节点数、初始边数、操…

ZOJ - 3123 Subsequence (滑动窗口)

题意&#xff1a;给定N个数&#xff0c;求和大于等于S的最短连续子序列的长度。 分析&#xff1a;滑动窗口即可。两种写法。 1、 #include<cstdio> #include<cstring> #include<cstdlib> #include<cctype> #include<cmath> #include<iostream…

杭电3123

这是一道数论题目&#xff01;利用公式同余取模&#xff01;思路&#xff1a;n可以达到10^100&#xff0c;很明显不能直接处理。但是发现只要n>m&#xff0c;那么m!(m1)!...n!这些项都是可以被m整除的&#xff0c;要对m求余&#xff0c;只需要找比m小的阶乘即可&#xff0c;…

[bzoj3123][SDOI2013]森林

3123: [Sdoi2013]森林 Time Limit: 20 Sec Memory Limit: 512 MB Submit: 1654 Solved: 520 [Submit][Status][Discuss] Description Input 第一行包含一个正整数testcase&#xff0c;表示当前测试数据的测试点编号。保证1≤testcase≤20。 第二行包含三个整数N&#xff…

bzoj 3123 [Sdoi2013]森林

http://www.elijahqi.win/archives/3755 Description Input 第一行包含一个正整数testcase&#xff0c;表示当前测试数据的测试点编号。保证1≤testcase≤20。 第二行包含三个整数N&#xff0c;M&#xff0c;T&#xff0c;分别表示节点数、初始边数、操作数。第三行包含N个…

hdu_3123_GCC

The GNU Compiler Collection (usually shortened to GCC) is a compiler system produced by the GNU Project supporting various programming languages. But it doesn’t contains the math operator “!”. In mathematics the symbol represents the factorial operation…

【loj3123】【CTS2019】重复

题目 给出一个长度为\(n\)的串\(s\)&#xff0c;询问有多少个长度为\(m\)的串\(t\)  满足 \(t\) 的无限循环串存在一个长度为\(n\)且比\(s\)字典序严格小的子串 $ n , m \le 2000 $ 题解 自从CTS打铁之后就非常自闭&#xff0c;智商一天不如一天&#xff0c;所以感觉这题异常抽…

bzoj3123: [Sdoi2013]森林

题面在这里 题意&#xff1a; 给一个森林&#xff0c;森林有n个节点m条边。 现在有两种操作&#xff1a; 1.Q x y k 表示询问x-y这条链上点权的第k小。保证x&#xff0c;y在同一个连通块里。 2.L x y 表示链接x,y两点。保证x,y在不同的连通块里。 要求强制在线&#xff0…

bzoj3123

3123: [Sdoi2013]森林 Time Limit: 20 Sec Memory Limit: 512 MBSubmit: 1846 Solved: 574[Submit][Status][Discuss] Description Input 第一行包含一个正整数testcase&#xff0c;表示当前测试数据的测试点编号。保证1≤testcase≤20。 第二行包含三个整数N&#xff0c;M…

POJ 3123

https://cn.vjudge.net/problem/POJ-3123 题意&#xff1a; n 个城市&#xff0c;m 条路&#xff0c;给定八个点&#xff08;也就是四对&#xff09;&#xff0c;使每队点连通且总权和最小。 分析&#xff1a; dp[i][j] 表示 i 状态下以 j 为起点的最小总权和。 #include …

Flutter:第三方常用库整理

前言 随着Flutter的不断学习&#xff0c;接触了不少第三方的库。因此打算进行简单的整理。 dio 简介 一个强大的Dart/FlutterHTTP客户端&#xff0c;支持全局配置&#xff0c; 拦截器、表单数据、请求取消、文件上传/下载、 超时和自定义适配器等。 官方地址 https://pub-w…

Redis_客户端命令和数据操作(3)

目录 切换数据库 键命令 数据结构 string类型 hash类型 list类型 set类型 zset类型 查看中文value 源码等资料获取方法 切换数据库 redis数据库没有名称&#xff0c;默认有16个&#xff0c;通过0-15来标识&#xff0c;连接redis默认选择第一个数据库&#xff0c;可以…

青龙傻妞onebot不能用,改用cqhttp+傻妞/qqbot

不知为何我的onebot突然用不了了&#xff0c;傻妞还正常&#xff0c;这就需要改用cqhttp了 下面介绍cqhttp登录不上的问题 一般来说cqhttp还是很好安装的随便一搜就很多&#xff0c;这里先讲一下QQ扫码登录不成功问题 原因是&#xff0c;tx检测qq登录有风险&#xff0c;网络…

ONEBOT开发板

ONEBOT开发板 制作传感器的新方式—搭积木式制作传感器 介绍 ONEBOT是小米生态链爱其科技推出的开源传感器创作平台&#xff0c;提供了机器人、物联网应用创作原型&#xff0c;让每个人都享受创造科技的乐趣。 为电子爱好者、DIY、创客、教育等提供了制作传感器的 新方式&a…

『Nonebot 插件编写教程』nonebot2处理消息的完整过程

文章目录 前言捕获消息处理消息Bot机器人参数Event事件参数 回复消息字符串与Message调用MessageSegment接口 前言 前面已经有不止一篇博客教大家如何搭建nonebot2环境了大家可以去专栏查看&#xff0c;这篇博客并不会再次带大家来搭建nonebot2环境&#xff0c;而是着手与插件的…

Ubuntu搭建zhenxunbot聊天机器人

GitHub - HibiKier/zhenxun_bot: 基于 Nonebot2 和 go-cqhttp 开发&#xff0c;以 postgresql 作为数据库&#xff0c;非常可爱的绪山真寻bot 1.安装python3.9 apt和手动编译源码选一个&#xff0c;记得装pip pip改清华源&#xff0c;apt改国内随便哪个源 2.apt安装下面这一…

[Nonebot2]chatgpt

前言 今天我要教大家的是 如何实现nonebot之Gpt接入 准备 1.获取开发者key 获取key的地址&#xff1a;这里你们自行了解&#xff0c;有些原因不能展示 如图所示&#xff0c;我已经创建好一个key了&#xff0c;大家也可以点击Create new secret key按钮来创建一个新的key&am…

青龙面板node-onebot 教程

青龙安装部署教程-------点击跳转 没服务器的先自行购买&#xff0c;腾讯云2H4G8M首年70–点击购买 QQ交流&#xff1a;1014549449 --------------点击跳转 node-onebot 使用教程 注、 先去安全中心把端口开下 1.不管你用什么端口你都要在安全组开放一下 lsof -i :80|grep -…

使用nonebot+go-cqhttp搭建qq机器人

目录 缘由准备工作nonebotgo-cqhttp 开始吧下载go-cqhttp配置使用 go-cqhttp安装nonebotnonebot配置 看看成果吧 缘由 最近ChatGPT各种破圈大火&#xff0c;作为一名NLPer小学生&#xff0c;也来玩玩这个东西。那究竟怎么用呢&#xff1f; 想来想去&#xff0c;以往就想搞一个…
最新文章