题解：AT_joisc2015_d IOIOI カード占い

· · 题解

更好的阅读体验？

似乎区间修改不是很好做，发现取反有可逆性，考虑差分。

令：f_i 表示 s_i 和 s_{i-1} 是否不同 (\tt 0/1）。

然后区间修改就变为了对 f_{l_i} 和 f_{r_i+1} 取反了。

观察得到初始的 f 有一个性质：只有 f_1, f_{a+1}, f_{a+b+1}, \cdots 为 1，其余为 0。

发现性质：$f_x$ 和 $f_y$ 取反，$f_y$ 再和 $f_z$ 取反，相当于 $f_x$ 和 $f_z$ 取反。 于是 $f_{a+1}$ 和 $f_{a+b+1}$ 取反，相当于 $f_{a+1}$ 和其他的数取反，其他的数再和 $f_{a+1}$ 取反。如图。 ![](https://s21.ax1x.com/2024/04/11/pFXcAZ4.png) 发现这样很像最短路的节点，考虑求最短路。 具体地，对于每一段 $l_i, r_i$，考虑连一条连通 $l_i, r_{i+1}$ 的无向边。 对于 $f_1, f_{a+1}, f_{a+b+1}, \cdots$ 取反，可以改为 **先两两之间取反再算出总代价**。 由于两两之间取反仅有 $3$ 种可能，$f_{a+1}, f_{a+b+1}$ 和 $f_{a+b+c+1}, f_{a+b+c+d+1}$ 取反，$f_{a+1},f_{a+b+c+1}$ 和 $f_{a+b+1},f_{a+b+c+d+1}$ 取反，$f_{a+1}, f_{a+b+c+d+1}$ 和 $f_{a+b+1},f_{a+b+c+1}$ 取反。 令 $\text{dis}(x,y)$ 代表 $x$ 到 $y$ 最短路，只需要求出： - $\text{dis}(a+1,a+b+1)+\text{dis}(a+b+c+1,a+b+c+d+1)

之后求 \text{min} 即可。使用堆优化 Dijkstra，复杂度 O(n \log (a+b+c+d+e))。

#include "bits/stdc++.h"
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define ull unsigned long long

#define OPEN freopen (".in", "r", stdin); freopen (".out", "w", stdout);
#define DATA freopen (".in", "w", stdout);

#define pc __builtin_popcount
#define db double
#define pii pair<int, int>
#define fi first
#define se second

#define F(i,x,y) for (int i = (x); i <= (y); ++i)
#define D(i,x,y) for (int i = (y); i >= (x); --i)

using namespace std;

const ll inf = 45ll * 1e17;
const ll mod = 998244353ll;
//const ll mod = 1ll * 1e9 + 7ll;

inline void Rd(int& x) {
    int f = 1; x = 0;
    char c = getchar();
    while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
    while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c - 48), c = getchar();
    x *= f;
}

inline void Wt(int x) {
    if (x < 10) {putchar(x + 48); return;}
    Wt(x / 10); putchar((x % 10) + 48);
}

int a, b, c, d, e, n, m;

int f[5];

ll minf[5][5];

ll dis[650000];

int cnt;

int hd[560000];

struct Node {
    ll dis;

    int x;

    bool operator <(const Node& p) const {
        return dis > p.dis;
    }
};

priority_queue<Node> q;

struct Edge {
    int to, nxt;
    ll dis;
}_e[560000];

void addedge(int u, int v, ll d) {
    ++ cnt;

    _e[cnt].to = v;
    _e[cnt].dis = d;
    _e[cnt].nxt = hd[u];
    hd[u] = cnt;
}

void init() {

    F(i, 1, m) dis[i] = inf;
}

void dij(int s) {
    dis[s] = 0ll;

    Node _; _.dis = 0ll; _.x = s;

    q.push(_);

    while (!q.empty()) {
        Node _ = q.top(); q.pop();

        int u = _.x;

        for (int i = hd[u]; i; i = _e[i].nxt) {
            int v = _e[i].to;

            ll d = _.dis + _e[i].dis;

            if (dis[v] > d) {
                dis[v] = d;

                Node t;
                t.dis = d; t.x = v;

                q.push(t);
            }
        }
    }
}

int main() {
    IOS

    cin >> a >> b >> c >> d >> e >> n;

    m = a + b + c + d + e + 1;

    F(i, 1, n) {
        int x, y;

        cin >> x >> y;

        ++ y;

        addedge(x, y, 1ll * (y - x));
        addedge(y, x, 1ll * (y - x));
    }

    f[1] = a + 1, f[2] = a + b + 1, f[3] = a + b + c + 1, f[4] = a + b + c + d + 1;

    F(i, 1, 4) {
        init();
        dij(f[i]);
        F(j, i + 1, 4) minf[i][j] = dis[f[j]];
    }

    ll mn = min(minf[1][2] + minf[3][4], min(minf[1][3] + minf[2][4], minf[1][4] + minf[2][3]));

    if (mn > inf) cout << "-1\n";
    else cout << mn << '\n';
}