计蒜客【NOIP2017模拟3】任性的国王 <线段树+MST>

Problem

【NOIP2017模拟3】任性的国王

$\mathrm{Time\;Limit:\;1000\;ms}$
$\mathrm{Memory\;Limit:\;262144\;K}$

Description

X 国的地图可以被看作一个两行 $n$ 列的网格状图。现在 X 国需要修建铁路，然而该国的国王非常小气，他只想保证位于某两列之间的所有城市互相可以到达就行了，在此基础上，他希望所花费的代价最小。
铁路可以建在任何两个相邻的点之间，使他们可以互相到达。可以作为工作人员，你已经整理出了为每一对相邻城市架设铁路所需要的花费。你需要准备好回答国王如下形式的问题。
对于 $(i,j)$：当前情况下，使第 $i$ 列到第 $j$ 列之间的所有城市连通的最小代价是多少（列下标从 $1$ 开始）？注意不能用其他列的城市。
然而你还有更大的困难，随着时间变化，使用某些边作为铁路的代价会发生改变，你必须有效率地处理这些变化。

Input

第一行两个正整数 $n,m$，表示该国有 $2$ 行 $n$ 列以及 $m$ 个询问或者操作。
第二行 $3n-2$ 个数，前 $n-1$ 个数依次表示在第一行的 $n-1$ 条边上修建铁路的代价。
接下来 $n−1$ 个数，依次表示在第二行的 $n-1$ 条边上修建铁路的代价。
最后 $n$ 个数，依次表示在第 $1$ 列到第 $n$ 列的边上修建铁路的代价。
接下来 $m$ 行的输入具有如下形式，$K,S,T$，其中

• 若 $K=1$，则表示询问当前状态下，使所有第 $S$ 列到第 $T$ 列之间的城市连通需要的最小代价。
• 若 $K=2$，则表示位于第 $1$ 行第 $S$ 列的点到第 $1$ 行第 $S+1$ 列的点之间的边上修建铁路的代价变为 $T$。
• 若 $K=3$，则表示位于第 $2$ 行第 $S$ 列的点和第 $2$ 行第 $S+1$ 列的点之间的边上修建铁路的代价变为 $T$。
• 若 $K=4$，则表示第 $S$ 列的边上修建铁路的代价变为 $T$。

Output

依次对每个询问，用一行输出相应的答案。

Sample Input

4 14
2 3 4 3 1 1 1 5 4 7
1 1 2
1 2 3
1 1 3
1 2 4
2 1 5
1 1 4
4 2 1
1 1 3
1 2 3
1 2 4
3 3 100
1 3 4
1 2 4
1 1 4

Sample Output

6
8
10
13
17
9
5
10
15
16
20

Constraint

对于 $30\%$ 的数据：$n,m\le 2000$。
另有 $30\%$ 的数据：所有竖边的代价为 $0$ 且永不改变。
对于全部数据：$n,m \le 10^5$。
所有输入和输出数据保证合法，且不超过 $2^{31}-1$。

Source

2017 NOIP 提高组模拟赛（三）Day1

标签：线段树 MST

Solution

线段树维护特殊的网格图$\mathrm{MST}$。

对于每个区间$[s,t]$，维护四个值$mi[1/0][1/0]$，分别代表第$s$列的竖边选/不选且第$t+1$列竖边选/不选的情况下，将第$s$个网格到第$t$个网格中所有点连起来的最小代价。
用$ru[i],rd[i]$表示第$i$个网格上/下的边，用$c[i]$表示第$i$列的竖边，那么第$i$个网格相邻的两条竖边为$c[i],c[i+1]$。
对于长度为$1$的区间$[i,i]$，直接赋初值：

$$mi[0][0]=\infty\\ mi[1][0]= ru[i]+rd[i]+c[i]\\ mi[0][1]=ru[i]+rd[i]+c[i+1]\\ mi[1][1]=\min(ru[i],rd[i])+c[i]+c[i+1]\\$$

对于其余区间，需要从两个子区间合并而来。设左右区间为$x,y$，则两区间相交处的竖边为$c[x.t+1]$。
那么对于此区间的$mi[i][j]$，一定从$x.mi[i][?]$和$y.mi[?][j]$合并而来。如果用$x.mi[i][0]$和$y.mi[0][j]$合并，其合并出的所有情况的$\mathrm{MST}$权值无法直接算出，但其一定能由其余的三种合并方式得到，于是可以不用管这种合并方式。注意合并时第$x.t+1$列的两条边会在两棵生成树中均联通，所以需要删去其中一棵中连接两点的边，即减去$c[s.t+1]$。
由此，我们用线段树维护这个信息，对于修改，直接到该位置重新赋初值然后维护其祖先的信息即可。
时间复杂度$\mathcal{O}(n\log{n})$。

Code

#include <bits/stdc++.h>
#define MAX_N 100000
#define INF 0x3f3f3f3f
#define mid ((s+t)>>1)
using namespace std;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, ru[MAX_N+5], rd[MAX_N+5], c[MAX_N+5];
struct node {int s, t, mi[2][2];} tr[MAX_N<<2];
node init(int p) {
    node ret; ret.s = ret.t = p;
    ret.mi[0][0] = INF, ret.mi[1][1] = min(ru[p], rd[p])+c[p]+c[p+1];
    ret.mi[1][0] = ru[p]+rd[p]+c[p], ret.mi[0][1] = ru[p]+rd[p]+c[p+1];
    return ret;
}
node operator + (const node &x, const node &y) {
    node ret; ret.s = x.s, ret.t = y.t;
    memset(ret.mi, INF, sizeof ret.mi);
    for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++)
        ret.mi[i][j] = min(ret.mi[i][j], x.mi[i][0]+y.mi[1][j]-c[x.t+1]), 
        ret.mi[i][j] = min(ret.mi[i][j], x.mi[i][1]+y.mi[0][j]-c[x.t+1]), 
        ret.mi[i][j] = min(ret.mi[i][j], x.mi[i][1]+y.mi[1][j]-c[x.t+1]);
    return ret;
}
void update(int v) {tr[v] = tr[v<<1]+tr[v<<1|1];}
void build(int v, int s, int t) {
    if (s == t) {tr[v] = init(s); return;}
    build(v<<1, s, mid), build(v<<1|1, mid+1, t);
    tr[v] = tr[v<<1]+tr[v<<1|1];
}
void modifyr(int v, int s, int t, int p) {
    if (s == t) {tr[v] = init(s); return;}
    if (p <= mid) modifyr(v<<1, s, mid, p);
    if (p >= mid+1) modifyr(v<<1|1, mid+1, t, p);
    tr[v] = tr[v<<1]+tr[v<<1|1];
}
void modifyc(int v, int s, int t, int p) {
    if (s == t) {tr[v] = init(s); return;}
    if (p <= mid+1) modifyc(v<<1, s, mid, p);
    if (p >= mid+1) modifyc(v<<1|1, mid+1, t, p);
    tr[v] = tr[v<<1]+tr[v<<1|1];
}
node query(int v, int s, int t, int l, int r) {
    if (s >= l && t <= r) return tr[v];
    if (r <= mid) return query(v<<1, s, mid, l, r);
    if (l >= mid+1) return query(v<<1|1, mid+1, t, l, r);
    return query(v<<1, s, mid, l, r)+query(v<<1|1, mid+1, t, l, r);
}
int main() {
    read(n), read(m);
    for (int i = 1; i < n; i++) read(ru[i]);
    for (int i = 1; i < n; i++) read(rd[i]);
    for (int i = 1; i <= n; i++) read(c[i]);
    n--, build(1, 1, n);
    while (m--) {
        int opt; read(opt);
        if (opt == 1) {
            int l, r; read(l), read(r);
            if (l == r) printf("%d\n", c[l]);
            else {
                node res = query(1, 1, n, l, r-1);
                int ans = min(res.mi[0][0], res.mi[0][1]);
                ans = min(ans, min(res.mi[1][0], res.mi[1][1]));
                printf("%d\n", ans);
            }
        } else {
            int p, x; read(p), read(x);
            if (opt == 2) ru[p] = x, modifyr(1, 1, n, p);
            if (opt == 3) rd[p] = x, modifyr(1, 1, n, p);
            if (opt == 4) c[p] = x, modifyc(1, 1, n, p);
        }
    }
    return 0;
}