当前位置:网站首页>[Luogu cf487e] tours (square tree) (tree chain dissection) (line segment tree)
[Luogu cf487e] tours (square tree) (tree chain dissection) (line segment tree)
2022-07-05 23:49:00 【SSL_ TJH】
Tourists
Topic link :luogu CF487E
The main idea of the topic
Here's an undirected graph , Then a little bit of power .
Then you may modify the point weight at a single point every time , Or ask the point with the least weight in all paths between two points .
Ideas
It's not difficult to think of a round square tree when you see all these paths .
Then we consider that the square point is the minimum value of the origin to which it is connected .
Then you will find that if there is any modification, you will get stuck every time O ( n ) O(n) O(n)( Meganium )
Then consider a wonderful way , Is to consider the special place of this figure , It's a tree .
The reason why you get stuck is that you have to update everything , That update must be updated , The question is whether we can update only a part first , Then when you ask, get the missing part .
If the structure of the tree, can we only get our son , Then every time I update, I only update my father .
Then you think about the part of tree chain dissection , That's except LCA Is it OK for Fang Dian to get his father to do anything else .
Then the rest is simple , Just ordinary round square tree , Ordinary tree chain segmentation plus segment tree maintenance minimum .
Code
#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
- Scala concurrent programming (II) akka
- 转:未来,这样的组织才能扛住风险
- 15 MySQL stored procedures and functions
- 【luogu CF487E】Tourists(圆方树)(树链剖分)(线段树)
- 开源crm客户关系统管理系统源码,免费分享
- Brushless drive design -- on MOS drive circuit
- Xinyuan & Lichuang EDA training camp - brushless motor drive
- Huawei simulator ENSP - hcip - MPLS experiment
- rsync远程同步
猜你喜欢
openssl-1.0.2k版本升级openssl-1.1.1p
CIS基准测试工具kube-bench使用
Rasa 3. X learning series -rasa 3.2.1 new release
开关电源Buck电路CCM及DCM工作模式
My colleagues quietly told me that flying Book notification can still play like this
XML配置文件(DTD详细讲解)
Spreadjs 15.1 CN and spreadjs 15.1 en
MySQL delete uniqueness constraint unique
Neural structured learning 4 antagonistic learning for image classification
How to get all the values stored in localstorage
随机推荐
Laser slam learning record
Use mapper: --- tkmapper
el-cascader的使用以及报错解决
Use CAS instead of synchronized
激光slam学习记录
用列錶初始化你的vector&&initializer_list簡介
The PostgreSQL column reference 'ID' is ambiguous - PostgreSQL column reference'id'is ambiguous
【LeetCode】5. Valid palindrome
【EF Core】EF Core与C# 数据类型映射关系
Technical specifications and model selection guidelines for TVs tubes and ESD tubes - recommended by jialichuang
Breadth first search open turntable lock
Golang code checking tool
C# 反射与Type
Redis高可用——主从复制、哨兵模式、集群
Biased sample variance, unbiased sample variance
PADS ROUTER 使用技巧小记
What is a humble but profitable sideline?
Comparison of parameters between TVs tube and zener diode
MySQL delete uniqueness constraint unique
When to use useImperativeHandle, useLayoutEffect, and useDebugValue