当前位置: 首页 > news >正文

[QOJ888] Travel around China 题解

[QOJ888] Travel around China 题解

Petrozavodsk Winter 2021. Day 4. PKU Contest (Common Contest 1)

考虑 \(n = 2\),猫树分治,考虑统计所有经过 \(mid\) 的区间,从 \(mid\) 开始跑最短路,处理出区间左右端点到 \(mid\) 列的最短路,最后要求的形如 \(\sum_{x\in Left, y\in Right} \min(d_{1,i,mid}+d_{1,mid,j}, d_{2, i, mid} + d_{2, mid, j})\),分类讨论谁取 \(\min\),就是一个二维偏序。

考虑 \(n = 3\),同样的猫树分治,不过这里会多一种情况,就是 \((1, i)\) 可能绕一圈到达 \((3, i)\),设 \(f_i\) 到达 \((3,i)\) 的最小代价,转移有:向左走、向右走、直接向下走三种情况,那么可以用 Dijkstra 求出 \(f_i\),最后还是分类讨论 \(\min\) 取谁做二维偏序即可。

代码难度较高。

时间复杂度:\(O(n\log ^2n)\)

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#define int long long
#define x first
#define y second
using namespace std;
typedef unsigned long long ull;
typedef pair<int, int> PII;
const int N = 5e5 + 10, mod = 1e9 + 7, INF = 1e18;int n, m, a[4][N], f[N], ans, d[4][4][N];
struct qwq {int d, r, c;bool operator < (const qwq &W) const {return d < W.d;}bool operator > (const qwq &W) const {return d > W.d;}
};
priority_queue<qwq, vector<qwq>, greater<qwq> > heap;
void trans(int o, int r, int c, int v) {if(d[o][r][c] > v)d[o][r][c] = v, heap.push({v, r, c});
}
void dijkstra(int o, int s, int l, int r) {for(int i = 1; i <= 3; i ++) for(int j = l; j <= r; j ++) d[o][i][j] = INF;heap.push({a[o][s], o, s});d[o][o][s] = a[o][s];while(heap.size()) {auto t = heap.top(); heap.pop();if(t.d != d[o][t.r][t.c]) continue;if(t.r > 1) trans(o, t.r - 1, t.c, t.d + a[t.r - 1][t.c]);if(t.r < 3) trans(o, t.r + 1, t.c, t.d + a[t.r + 1][t.c]);if(t.c < r) trans(o, t.r, t.c + 1, t.d + a[t.r][t.c + 1]);if(t.c > l) trans(o, t.r, t.c - 1, t.d + a[t.r][t.c - 1]);}
}
void chkmin(int &a, int b) {if(a > b) a = b;
}
int disc[N], tot;
int findl(int x) {return upper_bound(disc + 1, disc + tot + 1, x) - disc - 1;
}
int findl2(int x) {return lower_bound(disc + 1, disc + tot + 1, x) - disc - 1;
}
int tr[N], tr2[N];
void update(int u, int c, int d) {for(; u <= tot; u += u & -u)tr[u] += c, tr2[u] += d;
}
int query(int u) {int sum = 0; for(; u; u &= u - 1)sum += tr[u];return sum;
}
int query2(int u) {int sum = 0; for(; u; u &= u - 1)sum += tr2[u];return sum % mod;
}
int F(int i, int j, int x, int y) {return d[x][i][j] - d[y][i][j];
}
void solve(int l, int r) {if(l == r) {(ans += (a[1][l] + a[2][l] * 2 + a[3][l] + f[l]) % mod) %= mod;return ;}int mid = l + r >> 1;solve(l, mid), solve(mid + 1, r);for(int o = 1; o <= 3; o ++) dijkstra(o, mid, l, r);for(int o = 1; o <= 3; o ++) for(int i = l; i <= r; i ++) chkmin(d[o][1][i], d[o][3][i] + f[i] - a[3][i]), chkmin(d[o][3][i], d[o][1][i] + f[i] - a[1][i]);for(int o = 1; o <= 3; o ++) for(int rw = 1; rw <= 3; rw ++) for(int i = mid+ 1; i <= r; i ++) d[o][rw][i] -= a[o][mid];vector<qwq> t1, t2;tot = 0;for(int i = 1; i <= 3; i ++) for(int j = l; j <= r; j ++) if(j <= mid) disc[++ tot] = F(i, j, 1, 3), t1.push_back({F(i, j, 1, 2), i, j});else t2.push_back({F(i, j, 2, 1), i, j});sort(t1.begin(), t1.end()), sort(t2.begin(), t2.end());sort(disc + 1, disc + tot + 1), tot = unique(disc + 1, disc + tot + 1) - disc - 1;for(int i = 0, j = 0; j < t2.size(); j ++) {while(i < t1.size() && t1[i].d <= t2[j].d) update(findl(F(t1[i].r, t1[i].c, 1, 3)), 1, d[1][t1[i].r][t1[i].c]), i ++;int pos = findl(F(t2[j].r, t2[j].c, 3, 1));(ans += (query(pos) * d[1][t2[j].r][t2[j].c] + query2(pos)) % mod);}for(int i = 1; i <= tot; i ++) tr[i] = tr2[i] = 0;t1.clear(), t2.clear();tot = 0;for(int i = 1; i <= 3; i ++) for(int j = l; j <= r; j ++) if(j <= mid) disc[++ tot] = F(i, j, 2, 1), t1.push_back({F(i, j, 2, 3), i, j});else t2.push_back({F(i, j, 3, 2), i, j});sort(t1.begin(), t1.end()), sort(t2.begin(), t2.end());sort(disc + 1, disc + tot + 1), tot = unique(disc + 1, disc + tot + 1) - disc - 1;for(int i = 0, j = 0; j < t2.size(); j ++) {while(i < t1.size() && t1[i].d <= t2[j].d) update(findl(F(t1[i].r, t1[i].c, 2, 1)), 1, d[2][t1[i].r][t1[i].c]), i ++;int pos = findl2(F(t2[j].r, t2[j].c, 1, 2));(ans += (query(pos) * d[2][t2[j].r][t2[j].c] + query2(pos)) % mod);}for(int i = 1; i <= tot; i ++) tr[i] = tr2[i] = 0;t1.clear(), t2.clear();tot = 0;for(int i = 1; i <= 3; i ++) for(int j = l; j <= r; j ++) if(j <= mid) disc[++ tot] = F(i, j, 3, 2), t1.push_back({F(i, j, 3, 1), i, j});else t2.push_back({F(i, j, 1, 3), i, j});sort(t1.begin(), t1.end()), sort(t2.begin(), t2.end());sort(disc + 1, disc + tot + 1), tot = unique(disc + 1, disc + tot + 1) - disc - 1;for(int i = 0, j = 0; j < t2.size(); j ++) {while(i < t1.size() && t1[i].d < t2[j].d) update(findl(F(t1[i].r, t1[i].c, 3, 2)), 1, d[3][t1[i].r][t1[i].c]), i ++;int pos = findl2(F(t2[j].r, t2[j].c, 2, 3));(ans += (query(pos) * d[3][t2[j].r][t2[j].c] + query2(pos)) % mod);}ans %= mod;for(int i = 1; i <= tot; i ++) tr[i] = tr2[i] = 0;
}signed main() {
//    freopen("ex_data.in", "r", stdin);ios::sync_with_stdio(0), cin.tie(0);cin >> n >> m;for(int i = 1; i <= 3; i ++) for(int j = 1; j <= m; j ++) cin >> a[i][j];priority_queue<PII, vector<PII>, greater<PII> > q;for(int i = 1; i <= m; i ++) f[i] = a[1][i] + a[2][i] + a[3][i], q.push({f[i], i});while(q.size()) {auto t = q.top().y, v = q.top().x; q.pop();if(v != f[t]) continue;
//    cout << v << '\n';if(t > 1) {if(f[t] + a[1][t - 1] + a[3][t - 1] < f[t - 1])f[t - 1] = f[t] + a[1][t - 1] + a[3][t - 1], q.push({f[t - 1], t - 1});}if(t < m) {if(f[t] + a[1][t + 1] + a[3][t + 1] < f[t + 1]) f[t + 1] = f[t] + a[1][t + 1] + a[3][t + 1], q.push({f[t + 1], t + 1});}} solve(1, m);cout << ans * 2 % mod << '\n';return 0;
}
http://www.hskmm.com/?act=detail&tid=31890

相关文章:

  • MySQL面试必考:从入门到精通的20个问题
  • 手撕大模型 | MQA 和 GQA 原理解析
  • P1912 [NOI2009] 诗人小G 分析
  • [COCI2022-2023#2] Tramvaji 题解
  • 一级指针和二级指针作为函数参数的区别
  • ROUGE指标
  • CSP-S 模拟 29
  • Linux 文件及相关安全操作指南
  • day012
  • 怎么能把一个横着的很长的excel表,输出成一个能完整展示在一个页面中的PDF
  • 高精度
  • 深入解析:Leetcode+Java+图论+岛屿问题
  • 简单介绍
  • agent技术框架
  • agent认知与原理分析
  • agent策略分析与Parer解读
  • Visual Studio 2022连接mysql数据库,解决System.Data.Odbc.OdbcException (0x80131937)
  • day05
  • [AI生成]Spark-TTS个人理解
  • 2025.10.3 测试
  • [20251015]建立和完善col_vlist.sql脚本.txt
  • [20251014]建立和完善col_list.sql脚本.txt
  • [20251014]建立完善通用的prx.sql脚本.txt
  • 倍增法
  • 复杂版式与印章干扰下的高精度社会团体法人登记证书识别技术
  • 征程 6 | BPU trace 简介与实操
  • 2025年预应力千斤顶厂家最新权威推荐榜:批发采购、张拉设备、同步顶升系统专业供应商综合测评与选购指南
  • 2025.10.15训练记录
  • 利用Next.js中间件漏洞实现SSRF攻击与RCE
  • 三级医疗服务体系 (Three Tiers of Care)