当前位置:网站首页>【luogu CF487E】Tourists(圆方树)(树链剖分)(线段树)
【luogu CF487E】Tourists(圆方树)(树链剖分)(线段树)
2022-07-05 23:34:00 【SSL_TJH】
Tourists
题目链接:luogu CF487E
题目大意
给你一个无向图,然后点有点权。
然后每次可能会单点修改点权,或者询问两个点之间所有的路径中点权最小的点。
思路
看到这种所有路径不难想到圆方树。
然后我们考虑方点就是它连着的原点的最小值。
然后会发现如果有修改会每次被卡到 O ( n ) O(n) O(n)(大菊花)
然后考虑一个奇妙的方法,就是考虑这个图特殊的地方,它是一棵树。
那你被卡的原因是因为你要全部都更新,那更新是肯定要更新的,那问题是我们可不可以先只更新一部分,然后询问的时候把没有的部分弄上。
那树的结构的话我们是不是可以只弄儿子的,然后每次更新就只用更新父亲那个。
然后你想一下树链剖分的部分,那不就是除了 LCA 是方点要把它父亲弄上之外别的都没问题吗。
然后剩下的就简单了,就普通圆方树,普通树链剖分加线段树维护最小值。
代码
#include<set>
#include<cstdio>
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 100;
int n, m, q, w[N << 1], tot;
vector <int> G[N], GG[N << 1];
multiset <int> sum[N];
struct SLPF {
int dfn[N << 1], son[N << 1], sz[N << 1], fa[N << 1], top[N << 1], a[N << 3], deg[N << 1], dy[N << 1];
void dfs1(int now, int father) {
sz[now] = 1; fa[now] = father; deg[now] = deg[father] + 1;
for (int i = 0; i < GG[now].size(); i++) {
int x = GG[now][i]; if (x == father) continue;
dfs1(x, now); sz[now] += sz[x]; if (sz[x] > sz[son[now]]) son[now] = x;
}
if (now > n) {
for (int i = 0; i < GG[now].size(); i++) {
int x = GG[now][i]; if (x == father) continue;
sum[now - n].insert(w[x]);
}
w[now] = *sum[now - n].begin();
}
}
void dfs2(int now, int father) {
dfn[now] = ++dfn[0]; dy[dfn[0]] = now;
if (son[now]) {
top[son[now]] = top[now]; dfs2(son[now], now);
}
for (int i = 0; i < GG[now].size(); i++) {
int x = GG[now][i]; if (x == father || x == son[now]) continue;
top[x] = x; dfs2(x, now);
}
}
void up(int now) {
a[now] = min(a[now << 1], a[now << 1 | 1]);
}
void build(int now, int l, int r) {
if (l == r) {
a[now] = w[dy[l]]; return ;
}
int mid = (l + r) >> 1;
build(now << 1, l, mid); build(now << 1 | 1, mid + 1, r);
up(now);
}
void change(int now, int l, int r, int pl) {
if (l == r) {
a[now] = w[dy[pl]]; return ;
}
int mid = (l + r) >> 1;
if (pl <= mid) change(now << 1, l, mid, pl); else change(now << 1 | 1, mid + 1, r, pl);
up(now);
}
int query(int now, int l, int r, int L, int R) {
if (L <= l && r <= R) {
return a[now];
}
int mid = (l + r) >> 1, re = 2e9;
if (L <= mid) re = min(re, query(now << 1, l, mid, L, R));
if (mid < R) re = min(re, query(now << 1 | 1, mid + 1, r, L, R));
return re;
}
int ask(int x, int y) {
int re = 2e9;
while (top[x] != top[y]) {
if (deg[top[x]] < deg[top[y]]) swap(x, y);
re = min(re, query(1, 1, tot, dfn[top[x]], dfn[x]));
x = fa[top[x]];
}
if (deg[x] > deg[y]) swap(x, y);
re = min(re, query(1, 1, tot, dfn[x], dfn[y]));
if (x > n) re = min(re, w[fa[x]]);
return re;
}
}T;
struct YF_tree {
int dfn[N], low[N], sta[N];
void link(int x, int y) {
GG[x].push_back(y); GG[y].push_back(x);}
void tarjan(int now) {
dfn[now] = low[now] = ++dfn[0]; sta[++sta[0]] = now;
for (int i = 0; i < G[now].size(); i++) {
int x = G[now][i];
if (!dfn[x]) {
tarjan(x); low[now] = min(low[now], low[x]);
if (dfn[now] == low[x]) {
tot++;
while (sta[sta[0]] != x) {
link(sta[sta[0]], tot); sta[0]--;
}
link(sta[sta[0]], tot); sta[0]--;
link(now, tot);
}
}
else low[now] = min(low[now], dfn[x]);
}
}
void Init() {
tot = n;
for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i);
T.dfs1(1, 0); T.dfs2(1, 0);
}
}H;
int main() {
scanf("%d %d %d", &n, &m, &q);
for (int i = 1; i <= n; i++)
scanf("%d", &w[i]);
for (int i = 1; i <= m; i++) {
int x, y; scanf("%d %d", &x, &y);
G[x].push_back(y); G[y].push_back(x);
}
H.Init();
T.build(1, 1, tot);
while (q--) {
char c = getchar(); while (c != 'C' && c != 'A') c = getchar();
if (c == 'A') {
int x, y; scanf("%d %d", &x, &y);
printf("%d\n", T.ask(x, y));
}
else {
int x, y; scanf("%d %d", &x, &y);
if (T.fa[x]) {
sum[T.fa[x] - n].erase(w[x]); sum[T.fa[x] - n].insert(y);
w[T.fa[x]] = *sum[T.fa[x] - n].begin(); T.change(1, 1, tot, T.dfn[T.fa[x]]);
}
w[x] = y; T.change(1, 1, tot, T.dfn[x]);
}
}
return 0;
}
边栏推荐
- Laser slam learning record
- It is proved that POJ 1014 module is optimized and pruned, and some recursion is wrong
- Code farmers to improve productivity
- Neural structured learning - Part 3: training with synthesized graphs
- Bao Yan notebook IV software engineering and calculation volume II (Chapter 8-12)
- How to improve eloquence
- In C#, why can't I modify the member of a value type instance in a foreach loop?
- GFS distributed file system
- 有什么不起眼却挣钱的副业?
- 98. 验证二叉搜索树 ●●
猜你喜欢
STM32__06—单通道ADC
Brushless drive design -- on MOS drive circuit
Biased sample variance, unbiased sample variance
TVS管和ESD管的技術指標和選型指南-嘉立創推薦
总结了 800多个 Kubectl 别名,再也不怕记不住命令了!
98. Verify the binary search tree ●●
CIS基准测试工具kube-bench使用
21.PWM应用编程
Hcip course notes-16 VLAN, three-tier architecture, MPLS virtual private line configuration
Spire.PDF for NET 8.7.2
随机推荐
424. 替换后的最长重复字符 ●●
同事悄悄告诉我,飞书通知还能这样玩
14 MySQL view
[SQL] SQL expansion languages of mainstream databases (T-SQL, pl/sql, pl/pgsql)
Which side projects can be achieved? Is it difficult for we media to earn more than 10000 a month?
[original] what is the core of programmer team management?
Zero rhino technology joined hands with the intelligence Club: the "causal faction" forum was successfully held, and the "causal revolution" brought the next generation of trusted AI
做自媒体影视短视频剪辑号,在哪儿下载素材?
保研笔记四 软件工程与计算卷二(8-12章)
C file and folder operation
保研笔记一 软件工程与计算卷二(1-7章)
Spire Office 7.5.4 for NET
GFS distributed file system
Hcip course notes-16 VLAN, three-tier architecture, MPLS virtual private line configuration
My colleagues quietly told me that flying Book notification can still play like this
【LeetCode】5. Valid palindrome
Open source CRM customer relationship system management system source code, free sharing
Live tiktok shop 2022 latest gameplay card slot overseas live e-commerce new traffic
TVS管和ESD管的技术指标和选型指南-嘉立创推荐
保研笔记二 软件工程与计算卷二(13-16章)