SCUT - 297 - 狂符「幻视调律(Visionary Tuning)」 - 重链剖分
2024-10-07 11:30:19
一般的树剖是关于点权的，但是突发奇想好像边权也是一样的。做一些小改动。
#include<bits/stdc++.h>
#define lc (o<<1)
#define rc (o<<1|1)
typedef long long ll;
using namespace std;
const ll INF = 1e18;
const int MAXN = 125000 + 5;
int dep[MAXN], siz[MAXN], son[MAXN], fa[MAXN], top[MAXN], tid[MAXN], rnk[MAXN], cnt;
int n, m;
int head[MAXN], etop;
struct Edge {
int v, next;
} e[MAXN * 2];
inline void init(int n) {
etop = 0;
memset(head, -1, sizeof(head[0]) * (n + 1));
}
inline void addedge(int u, int v) {
e[++etop].v = v;
e[etop].next = head[u];
head[u] = etop;
e[++etop].v = u;
e[etop].next = head[v];
head[v] = etop;
}
struct SegmentTree {
ll mi[MAXN * 4], ma[MAXN * 4], lz[MAXN * 4];
void pushup(int o) {
mi[o] = min(mi[lc], mi[rc]);
ma[o] = max(ma[lc], ma[rc]);
}
void pushdown(int o, int l, int r) {
if(lz[o]) {
lz[lc] += lz[o];
lz[rc] += lz[o];
mi[lc] += lz[o];
ma[lc] += lz[o];
mi[rc] += lz[o];
ma[rc] += lz[o];
lz[o] = 0;
}
}
void update(int o, int l, int r, int ql, int qr, int v) {
if(ql <= l && r <= qr) {
lz[o] += v, mi[o] += v, ma[o] += v;
} else {
pushdown(o, l, r);
int m = (l + r) >> 1;
if(ql <= m)
update(lc, l, m, ql, qr, v);
if(qr >= m + 1)
update(rc, m + 1, r, ql, qr, v);
pushup(o);
}
}
ll querymin(int o, int l, int r, int ql, int qr) {
if(ql <= l && r <= qr) {
return mi[o];
} else {
pushdown(o, l, r);
int m = (l + r) >> 1;
ll res = INF;
if(ql <= m)
res = min(res, querymin(lc, l, m, ql, qr));
if(qr >= m + 1)
res = min(res, querymin(rc, m + 1, r, ql, qr));
return res;
}
}
ll querymax(int o, int l, int r, int ql, int qr) {
if(ql <= l && r <= qr) {
return ma[o];
} else {
pushdown(o, l, r);
int m = (l + r) >> 1;
ll res = -INF;
if(ql <= m)
res = max(res, querymax(lc, l, m, ql, qr));
if(qr >= m + 1)
res = max(res, querymax(rc, m + 1, r, ql, qr));
return res;
}
}
} st;
void init1() {
dep[1] = 1;
}
void dfs1(int u, int t) {
siz[u] = 1, son[u] = -1, fa[u] = t;
for(int i = head[u]; i != -1; i = e[i].next) {
int v = e[i].v;
if(v == t)
continue;
dep[v] = dep[u] + 1;
dfs1(v, u);
siz[u] += siz[v];
if(son[u] == -1 || siz[v] > siz[son[u]])
son[u] = v;
}
}
void init2() {
cnt = 0;
}
void dfs2(int u, int t) {
top[u] = t;
tid[u] = ++cnt;
rnk[cnt] = u;
if(son[u] == -1)
return;
dfs2(son[u], t);
for(int i = head[u]; i != -1; i = e[i].next) {
int v = e[i].v;
if(v == fa[u] || v == son[u])
continue;
dfs2(v, v);
}
}
ll querymin1(int u, int v) {
ll ret = INF;
int tu = top[u], tv = top[v];
while(tu != tv) {
if(dep[tu] >= dep[tv]) {
ret = min(ret, st.querymin(1, 1, n, tid[tu], tid[u]));
u = fa[tu];
tu = top[u];
} else {
ret = min(ret, st.querymin(1, 1, n, tid[tv], tid[v]));
v = fa[tv];
tv = top[v];
}
}
if(tid[u] == tid[v])
return ret;
if(tid[u] < tid[v])
ret = min(ret, st.querymin(1, 1, n, tid[u], tid[v] - 1));
else
ret = min(ret, st.querymin(1, 1, n, tid[v], tid[u] - 1));
return ret;
}
ll querymax1(int u, int v) {
ll ret = -INF;
int tu = top[u], tv = top[v];
while(tu != tv) {
if(dep[tu] >= dep[tv]) {
ret = max(ret, st.querymax(1, 1, n, tid[tu], tid[u]));
u = fa[tu];
tu = top[u];
} else {
ret = max(ret, st.querymax(1, 1, n, tid[tv], tid[v]));
v = fa[tv];
tv = top[v];
}
}
if(tid[u] == tid[v])
return ret;
if(tid[u] < tid[v])
ret = max(ret, st.querymax(1, 1, n, tid[u], tid[v] - 1));
else
ret = max(ret, st.querymax(1, 1, n, tid[v], tid[u] - 1));
return ret;
}
inline void update1(int u, int v, int val) {
int tu = top[u], tv = top[v];
while(tu != tv) {
if(dep[tu] >= dep[tv]) {
st.update(1, 1, n, tid[tu], tid[u], val);
u = fa[tu];
tu = top[u];
} else {
st.update(1, 1, n, tid[tv], tid[v], val);
v = fa[tv];
tv = top[v];
}
}
if(tid[u] == tid[v])
return;
else if(tid[u] < tid[v])
st.update(1, 1, n, tid[u], tid[v] - 1, val);
else
st.update(1, 1, n, tid[v], tid[u] - 1, val);
}
void op0() {
int u, v, val;
scanf("%d%d%d", &u, &v, &val);
update1(u, v, val);
}
void op1() {
int u, v;
scanf("%d%d", &u, &v);
ll res = querymin1(u, v);
if(res != 0) {
printf("Lunatic\n");
} else {
res = querymax1(u, v);
if(res != 0)
printf("Lunatic\n");
else
printf("Normal\n");
}
}
int main() {
#ifdef Yinku
freopen("Yinku.in", "r", stdin);
#endif // Yinku
scanf("%d", &n);
init(n);
for(int i = 1, u, v; i <= n - 1; ++i) {
scanf("%d%d", &u, &v);
addedge(u, v);
}
init1();
dfs1(1, -1);
init2();
dfs2(1, 1);
scanf("%d", &m);
for(int i = 1, op; i <= m; ++i) {
scanf("%d", &op);
switch(op) {
case 0:
op0();
break;
case 1:
op1();
break;
}
}
return 0;
}
上面的那个代码是有问题的，算法和定义不对应，但是居然能过？数据太弱了笑死我了。
最新文章
- wampserver配置问题
- android studio gradle结构项目引入本地代码
- 快速入门系列--WCF--06并发限流、可靠会话和队列服务
- mysql表名忽略大小写问题记录
- My Game --线段数据
- Okhttp https
- http加速软件使用说明
- 不容易系列之二[HDU2042]
- cocos2d对动画的各种操作
- C++泛型编程原理
- 十个顶级的C语言资源助你成为优秀的程序员
- 源代码安装GIT
- java.lang.NoSuchMethodError: javax.persistence.OneToMany.orphanRemoval()Z
- 自动删除文件脚本（Linux shell脚本）
- CUDA学习，环境配置和简单例子
- leetcode网学习笔记（1）
- eMMC之分区管理、总线协议和工作模式【转】
- RBAC表
- 1、算法介绍，lowB三人组，快速排序
- 从原型模式(Prototype Pattern)到 Clone