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

P11118 [ROI 2024] 无人机比赛 (Day 2) 题解

我们可以将比赛过程分为 \(n\times m\) 轮,每轮有一架无人机从上一个门飞至下一个门,其余的传送。

考虑每轮是哪个没有传送。发现是飞向下一个门时间最少且编号最小的。设 \(w_{i,j}\) 表示 \(i\)\(j-1\) 号门飞向 \(j\) 号门所需的时间,发现实际上这个顺序是对这 \(n\) 个数组的归并。具体来说就是每次取这 \(n\) 个数组中开头最小的那一个,然后删去它,直到删空。

注意到若一个数 \(w_{i,l}\) 被删去,且存在一个 \(r\) 满足 \((\max_{j=l}^{r}{w_{i,j}})\le w_{i,l}\),那么 \(w_{i,l\sim r}\) 会被连续删去。证明很显然。那么可以将这些会被连续删去的合并成一个段。

容易发现每个段的段首元素单调递增,即 \(w_{i,l_1}<w_{i,l_2}<\dots<w_{i,l_{m'}}\),其中 \(m'\) 为段数。

\(d_i\) 表示门 \(i-1\)\(i\) 的距离,发现 \(w_{i,j}=t_i\times d_j\),而对于相同的 \(i\)\(t_j\) 相同,所以实际上我们在对 \(d\) 分段,所以可得 \(d_{l_1}<d_{l_2}<\dots<d_{l_{m'}}\),又由于 \(\sum d_{l_i} \le S\),其中 \(S\) 为总距离,所以 \(m' \le \mathcal O(\sqrt{S})\)

考虑怎么算答案。每次一个无人机飞至下一个门时,对答案的贡献为剩下的没到达终点的无人机个数,则答案为 \(\sum\limits_{i=1}^{n}\sum\limits_{j\not=i}\sum\limits_{k=1}^{m}{[w_{j,k}\le w_{i,m}]}\),又由于一大段会连续飞过去,所以同一段中的贡献相同,只需要算每段的段首,再乘上段的长度即可。所以答案为 \(\sum\limits_{i=1}^{n}\sum\limits_{j\not=i}\sum\limits_{k=1}^{m'}{[w_{j,k}\le w_{i,l_{m'}}]len_k}\)\(j\not=i\) 的不好算,将所有的算出来减去 \(j=i\) 的即可。

考虑优化这个计算过程。现在计算一次答案的复杂度为 \(\mathcal O(n^2\sqrt{S})\),考虑优化一个 \(n\)。我们固定 \(k\),当 \(t\) 有序时,发现 \(i,j\) 有单调性,那么固定 \(i,k\),可以找到 \(j\) 的限制 \(t_j \le R_{i,k}\)\(R_{i,k}\) 可以双指针求出,可以做前缀和维护 \(j\) 的个数。

假设我们已经算出 \(i\le x-1\) 的答案,考虑计算 \(x\) 对答案的增量。分两种情况:

  • \(i=x,j<x\) 时:

    增量为 \(\sum\limits_{j<x}\sum\limits_{k=1}^{m'}{[t_j\le R_{x,k}]len_k}\),枚举 \(k\)\(\mathcal O(n)\) 次在 \(t_x\) 的位置单点加 \(1\)\(\mathcal O(n\sqrt{S})\) 次查询 \(\le R_{x,k}\) 的前缀和,可以分块根号平衡。

  • \(i\le x,j=x\) 时:

    增量为 \(\sum\limits_{i\le x}\sum\limits_{k=1}^{m'}{[t_x\le R_{i,k}]len_k}\),枚举 \(k\)\(\mathcal O(n\sqrt{S})\) 次在 \(R_{i,k}\) 的位置单点加 \(len_k\)\(\mathcal O(n)\) 次查询 \(\ge t_x\) 的后缀和,也可以分块根号平衡。

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
#define x first
#define y second
const int N = 1.5e5 + 5;
int n, m, cnt, t[N], Id[N], T[N], s[N], d[N], B = 400, id[N];
signed R[N][555];
struct node {int l, r, d;
}a[N];
#define len(i) (a[i].r - a[i].l + 1)
struct block {int l, r;
}b[N];
int s1[N], s2[N], S1[N], S2[N];
inline void modify1(int x, int v) {for(int i = x; i <= b[id[x]].r; i++) s1[i] += v;for(int i = id[x]; i <= id[n]; i++) S1[i] += v;
}
inline int query1(int x) {return s1[x] + S1[id[x] - 1];
}
inline void modify2(int x, int v) {s2[x] += v, S2[id[x]] += v;
}
inline int query2(int x) {int res = 0;for(int i = x; i <= b[id[x]].r; i++) res += s2[i];for(int i = id[x] + 1; i <= id[n]; i++) res += S2[i];return res;
}
signed main() {cin.tie(0) -> sync_with_stdio(0);cin >> n >> m;for(int i = 1; i <= n; i++) cin >> t[i], Id[i] = i;stable_sort(Id + 1, Id + 1 + n, [&](int a, int b) {return t[a] < t[b];});for(int i = 1; i <= n; i++)T[Id[i]] = i;for(int i = 1; i <= m; i++) cin >> s[i], d[i] = s[i] - s[i - 1];a[cnt = 1].l = 1, a[1].d = d[1];for(int i = 2; i <= m; i++) {if(d[i] > d[a[cnt].l]) a[cnt].r = i - 1, a[++cnt].l = i, a[cnt].d = d[i];}a[cnt].r = m;for(int k = 1; k <= cnt; k++) {for(int i = 1, j = 0; i <= n; i++) {while(j < n && (PII){t[Id[j + 1]] * a[k].d, Id[j + 1]} <= (PII){t[Id[i]] * a[cnt].d, Id[i]}) j++;R[Id[i]][k] = j;}}for(int i = 1; i <= n; i++) {id[i] = (i - 1) / B + 1;if(id[i] != id[i - 1]) b[id[i]].l = i, b[id[i - 1]].r = i - 1;}b[id[n]].r = n;int ans = 0;for(int i = 1; i <= n; i++) {for(int k = 1; k <= cnt; k++) {modify2(R[i][k], len(k));ans += query1(R[i][k]) * len(k);}modify1(T[i], 1), ans += query2(T[i]);ans -= m;cout << ans << '\n';}return 0;
}
http://www.hskmm.com/?act=detail&tid=30164

相关文章:

  • 基于遗传算法和粒子群优化在梁结构拓扑优化中的技术方案
  • 网络拓扑的认识与体会
  • P6333 [COCI2007-2008#1] ZAPIS 题解
  • 直播预告|PostgreSQL 18 六大新特性深度解析
  • 新型电力系统下 MyEMS 微电网协同调度:实践路径与园区落地案例
  • 抖音超人福袋助手,抖音福袋扭蛋机,抖音抢福袋工具,
  • 操作指南:国标GB28181/RTSP推流EasyGBS算法算力平台如何查看设备端录像回看?
  • 【华中科大主办|往届EI均检索】第四届声学,流体力学与工程国际学术会议(AFME 2025)
  • Codeforces Round 1058 (Div. 2) (4/8)
  • 10.13
  • P8037 [COCI2015-2016#7] Prokletnik 题解
  • 论文解读-《Learning Discrete Structures for Graph Neural Networks》 - zhang
  • 【A】The Lost Ship in the Sky
  • 2025 AI 品牌最新推荐排行榜:聚焦商业落地能力,甄选懂需求的实力服务机构东北 Ai/大连 Ai/大连 Ai 培训/大连 Ai 开发/大连 Ai 推广公司推荐
  • 基于经验模态分解的去趋势波动分析(EMD-DFA)方法
  • 双碳目标下企业零碳转型的 MyEMS 碳流可视化支撑体系:路径探索与效能评估
  • Langchain+Neo4j+Agent 的结合案例-电商销售 - 详解
  • ERP原理笔记
  • 2025 智慧康养实训室/专业建设/虚拟仿真/仿真实训室推荐榜:北京教之道 5 星领衔,适配多元康养场景
  • Wireshark】抓包实战,图文详解TCP三次握手及四次挥手原理
  • 2025 年国内水泵厂家最新推荐排行榜:涵盖多类型水泵,助力用户精准选购优质产品立式多级/自吸/磁力/排污/真空/离心水泵厂家推荐
  • 2025 年国内工业水泵厂家最新推荐排行榜:聚焦污水 / 离心 / 渣浆 / 大功率 / 泥浆类设备,助力企业精准选型
  • 基于深度学习的图像增强-zeros-DCE模型源码分享
  • redhat 链接宝塔mysql报错问题发现到解决
  • vue2初始化过程
  • [Doris/函数] Doris 之数据查询
  • 如何用AI绘制程序时序图
  • LLVM 后端支持 RISCV 矩阵扩展都有哪些方式
  • 简单聊聊数据可视化大屏制作的前端设计与后端开发
  • [THUWC 2018] 字胡串