「SDOI2013」森林
2024-09-06 15:24:58
「SDOI2013」森林
传送门
树上主席树 + 启发式合并
锻炼码力,没什么好说的。
细节见代码。
参考代码:
#include <algorithm>
#include <cstdio>
#define rg register
#define file(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout)
using std ::sort; using std ::swap; using std ::unique; using std ::lower_bound;
inline char _getchar() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
template < class T > inline void read(T& s) {
s = 0; rg int f = 0; rg char c = _getchar();
while ('0' > c || c > '9') f |= c == '-', c = _getchar();
while ('0' <= c && c <= '9') s = s * 10 + c - 48, c = _getchar();
s = f ? -s : s;
}
const int _ = 8e4 + 5;
int tot, head[_]; struct Edge { int ver, nxt; } edge[_ << 1];
inline void Add_edge(int u, int v)
{ edge[++tot] = (Edge) { v, head[u] }, head[u] = tot; }
int n, m, q, vis[_], a[_], X0, X[_], top[_], Siz[_], fa[18][_], dep[_];
int tt, rt[_]; struct node { int lc, rc, cnt; } t[_ * 266];
inline void build(int& p, int l = 1, int r = X0) {
p = ++tt, t[p].cnt = 0;
if (l == r) return ;
int mid = (l + r) >> 1;
build(t[p].lc, l, mid), build(t[p].rc, mid + 1, r);
}
inline void update(int& p, int q, int x, int l = 1, int r = X0) {
p = ++tt, t[p] = t[q], ++t[p].cnt;
if (l == r) return ;
rg int mid = (l + r) >> 1;
if (x <= mid) update(t[p].lc, t[q].lc, x, l, mid);
else update(t[p].rc, t[q].rc, x, mid + 1, r);
}
inline int query(int u, int v, int lca, int flca, int k, int l = 1, int r = X0) {
if (l == r) return l;
rg int mid = (l + r) >> 1;
rg int num = t[t[u].lc].cnt + t[t[v].lc].cnt - t[t[lca].lc].cnt - t[t[flca].lc].cnt;
if (num >= k) return query(t[u].lc, t[v].lc, t[lca].lc, t[flca].lc, k, l, mid);
else return query(t[u].rc, t[v].rc, t[lca].rc, t[flca].rc, k - num, mid + 1, r);
}
inline void dfs(int u, int f, int topf, int d) {
vis[u] = 1;
dep[u] = d, fa[0][u] = f, top[u] = topf, ++Siz[topf];
rt[u] = 0, update(rt[u], rt[f], a[u]);
for (rg int i = 1; i <= 16; ++i)
fa[i][u] = fa[i - 1][fa[i - 1][u]];
for (rg int i = head[u]; i; i = edge[i].nxt)
if (edge[i].ver != f) dfs(edge[i].ver, u, topf, d + 1);
}
inline int LCA(int x, int y) {
if (dep[x] < dep[y]) swap(x, y);
for (rg int i = 16; ~i; --i)
if (dep[fa[i][x]] >= dep[y]) x = fa[i][x];
if (x == y) return x;
for (rg int i = 16; ~i; --i)
if (fa[i][x] != fa[i][y]) x = fa[i][x], y = fa[i][y];
return fa[0][x];
}
int main() {
int T; read(T);
read(n), read(m), read(q);
for (rg int i = 1; i <= n; ++i) read(a[i]), X[i] = a[i];
sort(X + 1, X + n + 1);
X0 = unique(X + 1, X + n + 1) - X - 1;
for (rg int i = 1; i <= n; ++i) a[i] = lower_bound(X + 1, X + X0 + 1, a[i]) - X;
build(rt[0]);
for (rg int x, y, o = 1; o <= m; ++o)
read(x), read(y), Add_edge(x, y), Add_edge(y, x);
for (rg int i = 1; i <= n; ++i) if (!vis[i]) dfs(i, 0, i, 1);
for (rg int ans = 0, x, y, k, lca, o = 1; o <= q; ++o) {
rg char C = _getchar();
while (C != 'Q' && C != 'L') C = _getchar();
read(x), x ^= ans;
read(y), y ^= ans;
if (C == 'Q') {
read(k), k ^= ans, lca = LCA(x, y);
ans = X[query(rt[x], rt[y], rt[lca], rt[fa[0][lca]], k)];
printf("%d\n", ans);
} else {
Add_edge(x, y), Add_edge(y, x);
if (Siz[top[x]] < Siz[top[y]]) swap(x, y);
dfs(y, x, top[x], dep[x] + 1);
}
}
return 0;
}
最新文章
- 【转】40条常见的移动端Web页面问题解决方案
- VS2015 打开html 提示 未能完成操作 解决办法
- oracle自定义判断数据是否为数值函数
- http://love3400wind.blog.163.com/blog/static/7963080120132794359703/
- 用U盘作为启动盘,安装Yosemite
- Java Script基础(七) HTML DOM模型
- springMvc中406错误解决,springMvc使用json出现406 (Not Acceptable)
- 【转】Grub Rescue修复方法
- 数据结构录 之 单调队列&;单调栈。
- poj 1321 棋盘问题 简单DFS
- Jenkins 远程构建任务
- ssh: connect to host master port 22: Connection refused
- Android 音视频编解码——RGB与YUV格式转换
- CSV的简单用法
- bzoj 3673 可持久化并查集 by zky
- 【cf842D】Vitya and Strange Lesson(01字典树)
- OpenCV中RGB和HSV转换的问题
- Linux下 XordDos(BillGates)木马查杀记录
- windows 注册表讲解
- Eclipse开发Web常见异常
热门文章
- spring中@Component注解
- 计算机二级-C语言-程序填空题-190110记录-文件写入与文件读出显示
- 【STM32H7教程】第57章 STM32H7硬件JPEG编解码基础知识和HAL库API
- 带你了解MyBatis一二级缓存
- ASP.NET Core搭建多层网站架构【8.3-编写角色业务的增删改】
- 「WC2013」糖果公园
- C# worksheet设置Excel样式(转载)
- BeautifulReport底层框架的解析以及html报告页面元素的更改
- 使用Vue时localhost:8080中localhost换成ip地址后无法显示页面的问题
- Python学习第二十一课——Mysql 对数据库的基本操作