网站忧化工作怎么样,手机怎么制作网址链接,凯里市建设局网站,2022网页游戏大全P3250 [HNOI2016]网络
做法有点神奇#xff01;#xff01;#xff01;利用堆作为节点建立一颗线段树#xff0c;用堆维护线段树上点的信息。
说说查询操作#xff0c;我们的目的是要查询#xff0c;没有经过这个点的事件最大值#xff0c;考虑如何维护。
我们定义线…P3250 [HNOI2016]网络
做法有点神奇利用堆作为节点建立一颗线段树用堆维护线段树上点的信息。
说说查询操作我们的目的是要查询没有经过这个点的事件最大值考虑如何维护。
我们定义线段树上的信息每个点记录的是没有经过这个区间的事件值。
事件插入我们可以利用树剖得到从x−yx-yx−y的路径形成的logn\log nlogn个连续的段
我们先把这些段给存下来然后再按照lll排个序在这些段之外插入事件值。
同样的事件删除我们只要在这些段之外删除事件值即可这里好像有(logn)3(\log n) ^ 3(logn)3。
对于查询操作我们只要去查找这个点所在的区间的最大值即可因为我们记录的是不在这个区间里的值。
#include bits/stdc.h
#define mid (l r 1)
#define lson rt 1, l, mid
#define rson rt 1 | 1, mid 1, r
#define ls rt 1
#define rs rt 1 | 1using namespace std;const int N 1e5 10;struct Heap {priority_queueint a, b;void push(int x) {a.push(x);}void erase(int x) {b.push(x);}int top() {while (b.size() a.top() b.top()) {a.pop(), b.pop();}return a.top();}
}tree[N 2];void build(int rt, int l, int r) {tree[rt].push(-1);if (l r) {return ;}build(lson);build(rson);
}void update(int rt, int l, int r, int L, int R, int value, int op) {if (l L r R) {if (op) {tree[rt].push(value);}else {tree[rt].erase(value);}return ;}if (L mid) {update(lson, L, R, value, op);}if (R mid) {update(rson, L, R, value, op);}
}int query(int rt, int l, int r, int L, int R) {if (l L r R) {return tree[rt].top();}int ans tree[rt].top();if (L mid) {ans max(ans, query(lson, L, R));}if (R mid) {ans max(ans, query(rson, L, R));}return ans;
}int head[N], to[N 1], nex[N 1], cnt 1;int fa[N], son[N], sz[N], top[N], dep[N], rk[N], id[N], tot;int a[N 1], b[N 1], v[N 1], n, m;void add(int x, int y) {to[cnt] y;nex[cnt] head[x];head[x] cnt;
}void dfs1(int rt, int f) {fa[rt] f, dep[rt] dep[f] 1, sz[rt] 1;for (int i head[rt]; i; i nex[i]) {if (to[i] f) {continue;}dfs1(to[i], rt);sz[rt] sz[to[i]];if (!son[rt] || sz[son[rt]] sz[to[i]]) {son[rt] to[i];}}
}void dfs2(int rt, int tp) {top[rt] tp, rk[tot] rt, id[rt] tot;if (!son[rt]) {return ;}dfs2(son[rt], tp);for (int i head[rt]; i; i nex[i]) {if (to[i] fa[rt] || to[i] son[rt]) {continue;}dfs2(to[i], to[i]);}
}typedef pairint, int pii;pii sec[N];void update(int x, int y, int v, int op) {int cnt 0;while (top[x] ! top[y]) {if (dep[top[x]] dep[top[y]]) {swap(x, y);}sec[cnt] make_pair(id[top[x]], id[x]);x fa[top[x]];}if (dep[x] dep[y]) {swap(x, y);}sec[cnt] make_pair(id[x], id[y]);sort(sec 1, sec 1 cnt);int l 0;for (int i 1; i cnt; i) {if (l 1 sec[i].first) {update(1, 1, n, l 1, sec[i].first - 1, v, op);}l sec[i].second;}if (l n) {update(1, 1, n, l 1, n, v, op);}
}int main() {// freopen(in.txt, r, stdin);// freopen(out.txt, w, stdout);// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);scanf(%d %d, n, m);for (int i 1; i n; i) {int x, y;scanf(%d %d, x, y);add(x, y);add(y, x);}dfs1(1, 0);dfs2(1, 1);build(1, 1, n);for (int i 1; i m; i) {int op, x;scanf(%d, op);if (op 0) {scanf(%d %d %d, a[i], b[i], v[i]);update(a[i], b[i], v[i], 1);}else if (op 1) {scanf(%d, x);update(a[x], b[x], v[x], 0);}else {scanf(%d, x);printf(%d\n, query(1, 1, n, id[x], id[x]));}}return 0;
}
