Problem

一个简单的网络系统可以被描述成一棵无根树。每个节点为一个服务器。连接服务器与服务器的数据线则看做一条树边。两个服务器进行数据的交互时，数据会经过连接这两个服务器的路径上的所有服务器（包括这两个服务器自身）。

由于这条路径是唯一的，当路径上的某个服务器出现故障，无法正常运行时，数据便无法交互。此外，每个数据交互请求都有一个重要度，越重要的请求显然需要得到越高的优先处理权。现在，你作为一个网络系统的管理员，要监控整个系统的运行状态。系统的运行也是很简单的，在每一个时刻，只有可能出现下列三种事件中的一种：

在某两个服务器之间出现一条新的数据交互请求；

某个数据交互结束请求；

某个服务器出现故障。系统会在任何故障发生后立即修复。也就是在出现故障的时刻之后，这个服务器依然是正常的。但在服务器产生故障时依然会对需要经过该服务器的数据交互请求造成影响。

你的任务是在每次出现故障时，维护未被影响的请求中重要度的最大值。注意，如果一个数据交互请求已经结束，则不将其纳入未被影响的请求范围。

Solution

线段树维护堆，堆支持删除。
那么每次给全局堆加上某个值，再给某条路径删去某个值，之后直接对点查询即可。
一开始是这么想的，然而如果要写线段树的话会很爆炸。

那么维护一个不下放的线段树，即某个区间被全部覆盖就对它的区间进行修改，这样子的话只需要对线段树查询经过的点取最小值即可。
这样子的话一开始先加再减的思路行不通，得一开始把所有需要加的区间计算出来才行。
其次堆支持删除，本来写的是 set，发现很爆炸，于是改成 pbds 里的 paring heap，又很 MLE。跟 yyb 的代码比对了一下后，我把 paring heap 改成了 stl 的 priority_queue，emm 就过了。
所以 priority_queue 是最好用的喵喵喵？

然而我以为这就结束了，又去 BZOJ 上交了，M 爆。

翻了下讨论，卡邻接链表 + 树剖条件？
更新重儿子时，必须要 >= 才行。第二个优化是随机选点。我以前打的大概是假树剖...

其实加上了第一个优化 BZOJ 就可以过了，为了好看一点又加了第二个优化。不过即使是这样单点时限两秒我还是过不去呜呜呜

以及我对读入也进行了一下优化。简单来讲，一般都是选择读入优化手写，输出就 printf。于是我加上关闭流同步和 cin.tie(0)，据说是输入和输出互不干涉，且这么做了以后 printf 和 cout 速度一样，读入优化手打 getchar。但是事实上这么干的话 printf 比 cout 快很多。这确实是很奇怪了...

所以只能用整体二分了么 qwq

Code

// Code by ajcxsu
// Problem: network

#include<bits/stdc++.h>
using namespace std;

char ch;
template<typename T> void gn(T &x) {
    ch=getchar(), x=0;
    while(ch<'0' || ch>'9') ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
}

const int N=1e5+10, M=2e5+10;
int h[N], to[M], nexp[M], p=1;
inline void ins(int a, int b) { nexp[p]=h[a], h[a]=p, to[p]=b, p++; }
struct PQ {
    priority_queue<int> P1, P2;
    int top() {
        while(!P1.empty() && !P2.empty() && P1.top()==P2.top()) P1.pop(), P2.pop();
        return P1.top();
    }
    void del(int x) { P2.push(x); }
    void push(int x) { P1.push(x); }
} s[N*4];

#define ls x<<1
#define rs x<<1|1
void build(int x, int l, int r) {
    s[x].push(-1);
    if(l==r) return;
    int mid=(l+r)>>1;
    build(ls, l, mid), build(rs, mid+1, r);
}
void updata(int x, int l, int r, int xl, int xr, int w) {
    if(xl<=l && r<=xr) {
        if(w<0) s[x].del(-w);
        else s[x].push(w);
        return;
    }
    int mid=(l+r)>>1;
    if(xl<=mid) updata(ls, l, mid, xl, xr, w);
    if(xr>mid) updata(rs, mid+1, r, xl, xr, w);
}
int query(int x, int l, int r, int d) {
    if(l==r) return s[x].top();
    int mid=(l+r)>>1;
    if(d<=mid) return max(query(ls, l, mid, d), s[x].top());
    else return max(query(rs, mid+1, r, d), s[x].top());
}

int dep[N], dfn[N], top[N], son[N], siz[N], fa[N], idx;
void dfs1(int x, int k) {
    dep[x]=k, siz[x]=1;
    for(int u=h[x];u;u=nexp[u])
        if(!dep[to[u]]) {
            dfs1(to[u], k+1), siz[x]+=siz[to[u]], fa[to[u]]=x;
            if(siz[to[u]]>=siz[son[x]]) son[x]=to[u];
        }
}
void dfs2(int x, int t) {
    dfn[x]=++idx, top[x]=t;
    if(son[x]) dfs2(son[x], t);
    for(int u=h[x];u;u=nexp[u])
        if(!dfn[to[u]]) dfs2(to[u], to[u]);
}
int n, m, u, v;
struct Link { int l, r; } lin[N];
bool cmp(const Link &a, const Link &b) { return a.l<b.l; }
void modi(int s, int t, int w) {
    int lidx=0;
    while(top[s]!=top[t]) {
        if(dep[top[s]]<dep[top[t]]) swap(s, t);
        lin[lidx++]={dfn[top[s]], dfn[s]};
        s=fa[top[s]];
    }
    if(dfn[s]>dfn[t]) swap(s, t);
    lin[lidx++]={dfn[s], dfn[t]};
    sort(lin, lin+lidx, cmp);
    int L=0;
    for(int i=0;i<lidx;L=max(L, lin[i].r), i++)
        if(L+1<=lin[i].l-1) updata(1, 1, n, L+1, lin[i].l-1, w);
    if(L+1<=n) updata(1, 1, n, L+1, n, w);
}
struct Modi {int b, c, d;} q[M];

int main() {
    gn(n), gn(m);
    build(1, 1, n);
    int rt=rand()%(n-1)+1;
    for(int i=1;i<n;i++) gn(u), gn(v), ins(u, v), ins(v, u);
    dfs1(rt, 1), dfs2(rt, rt);
    int a, b, c, d, qidx=0;
    while(m--) {
        ++qidx;
        gn(a), gn(b);
        if(!a) gn(c), gn(d), modi(b, c, d), q[qidx]={b, c, d};
        else if(a==1) modi(q[b].b, q[b].c, -q[b].d);
        else if(a==2) printf("%d\n", query(1, 1, n, dfn[b]));
    }
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-bzoj-4538.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆