关于这类问题的一个经典的套路就是:利用差分将区间翻转转换为点对翻转。
既然操作差分了,那么原序列初始时也得以差分的形式进行表示。我们发现,原序列中一定恰好有 \(4\) 个 \(1\)。
根据题目,翻转操作就是对两个端点采取异或运算。不妨把所有这样的两个端点连上一条边权为 \(r-l+1\) 的边,我们发现,一条路径也就等价于对路径的两个端点进行翻转操作(中间的恰好翻转两次,抵消掉了)。
而我们的路径,必定是每次选择恰好两个 \(1\) 进行翻转,否则必然不比这样优。
考虑预处理出每个 \(1\) 之间两两的最短路,手动枚举一下 \(3\) 种情况即可。
点击查看代码
#include <bits/stdc++.h>
#define FL(i, a, b) for(int i = (a); i <= (b); ++i)
#define FR(i, a, b) for(int i = (a); i >= (b); --i)
using namespace std;
typedef long long ll;
const int N = 5e5 + 10;
const ll INF = 1e17;
struct E{int v, w;}; vector<E> e[N];
int n, m, a[6], s[6], vis[N]; ll ans = INF, d[3][N];
priority_queue<pair<ll, int> > q;
void dijkstra(int s, ll dis[]){
fill(vis + 1, vis + n + 1, 0);
fill(dis + 1, dis + n + 1, INF);
q.push(make_pair(dis[s] = 0, s));
while(!q.empty()){
int u = q.top().second; q.pop();
if(vis[u]) continue; vis[u] = 1;
for(const auto &p: e[u]){
if(dis[u] + p.w < dis[p.v])
q.push(make_pair(-(dis[p.v] = dis[u] + p.w), p.v));
}
}
}
int main(){
scanf("%d", &s[0]), a[0] = 1;
FL(i, 1, 4){
scanf("%d", &s[i]);
s[i] += s[i - 1], a[i] = s[i - 1] + 1;
}
n = s[4] + 1, scanf("%d", &m);
FL(i, 1, m){
int l, r; scanf("%d%d", &l, &r);
e[l].emplace_back((E){r + 1, r - l + 1});
e[r + 1].emplace_back((E){l, r - l + 1});
}
FL(i, 1, 3) dijkstra(a[i], d[i - 1]);
ans = min(ans, d[0][a[2]] + d[2][a[4]]);
ans = min(ans, d[0][a[3]] + d[1][a[4]]);
ans = min(ans, d[0][a[4]] + d[1][a[3]]);
printf("%lld\n", ans >= INF? -1 : ans);
return 0;
}