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

Problem

【NOIP2017模拟3】任性的国王

Description

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

Input

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

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

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

Constraint

对于的数据：。
另有的数据：所有竖边的代价为且永不改变。
对于全部数据：。
所有输入和输出数据保证合法，且不超过。

Source

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

标签：线段树 MST

Solution

线段树维护特殊的网格图。

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

对于其余区间，需要从两个子区间合并而来。设左右区间为，则两区间相交处的竖边为。
那么对于此区间的，一定从和合并而来。如果用和合并，其合并出的所有情况的权值无法直接算出，但其一定能由其余的三种合并方式得到，于是可以不用管这种合并方式。注意合并时第列的两条边会在两棵生成树中均联通，所以需要删去其中一棵中连接两点的边，即减去。
由此，我们用线段树维护这个信息，对于修改，直接到该位置重新赋初值然后维护其祖先的信息即可。
时间复杂度。

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;
}