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

洛谷 P13973 [VKOSHP 2024] Nightmare Sum

先用单调栈预处理出 i 位置左右第一个小于 a[i] 的位置,然后计算出 tot 数组 (tot[i]: 所有以 a[i] 为最小值的子数组总数) 和 pos 数组去记录每个数的位置所在 (每个数互不相同)。构造离线查询,对于固定的 i,枚举所有正整数 t 使得 t * a[i] <= maxA,把这个 t 对应的阈值 T = t * a[i] - 1 上记一条查询 “询问以 a[i] 为最小值且最大值 ≤ T 的子数组个数”。queries[T] 存的就是所有需要在阈值 T 下回答的索引 i,最后按 T 倒序维护值 > T 的位置集合并回答查询,然后容斥一下 tot[i] * t 减去这些子数组最大值不是 maxA 的数量就是最后答案。

#include <bits/stdc++.h>// https://www.luogu.com.cn/problem/P13973
// from: cpp.json
#define INF 8e18
#define LD long double
#define i128 __int128_t
#define int long long
using namespace std;void solve() {int n;cin >> n;vector<int> a(n + 1);for (int i = 1; i <= n; i++) {cin >> a[i];}int maxA = *max_element(a.begin(), a.end());vector<int> L(n + 1), R(n + 1);{vector<int> stk;for (int i = 1; i <= n; i++) {while (!stk.empty() && a[stk.back()] > a[i]) {stk.pop_back();}L[i] = stk.empty() ? 0 : stk.back();stk.push_back(i);}}{vector<int> stk;for (int i = n; i >= 1; i--) {while (!stk.empty() && a[stk.back()] > a[i]) {stk.pop_back();} R[i] = stk.empty() ? n + 1 : stk.back();stk.push_back(i);}}// 所有以 a[i] 为最小值的子数组总数vector<int> tot(n + 1);for (int i = 1; i <= n; i++) {tot[i] = (i - L[i]) * (R[i] - i);}vector<int> pos(maxA + 1);for (int i = 1; i <= n; i++) {pos[a[i]] = i;}vector<vector<int>> queries(maxA);for (int i = 1; i <= n; i++) {int v = a[i];int limit = maxA / v;for (int t = 1; t <= limit; t++) {int T = t * v - 1;queries[T].push_back(i);}}set<int> st;int sum = 0;for (int T = maxA - 1; T >= 0; T--) {if (pos[T + 1] != 0) {st.insert(pos[T + 1]);}for (auto idx : queries[T]) {auto it = st.lower_bound(idx);int r = (it == st.end() ? n + 1 : *it);int l;if (it == st.begin()) {l = 0;} else {auto it2 = it;it2--;l = *it2;}int left = max(L[idx], l);int right = min(R[idx], r);if (left < idx && right > idx) {int cnt = (idx - left) * (right - idx);sum += cnt;}}}int ans = 0;for (int i = 1; i <= n; i++) {int t = maxA / a[i];ans += tot[i] * t;}ans -= sum;cout << ans << '\n';
}signed main() {ios::sync_with_stdio(false);cin.tie(nullptr);solve();return 0;
}
http://www.hskmm.com/?act=detail&tid=13863

相关文章:

  • 发布/订阅(Publish/Subscribe)与交换机(Exchange)
  • 线性结构之链表
  • 二叉树最近公共祖先
  • AI 编程“效率幻觉”:为何你感觉快了,项目却慢了?
  • lc1033-移动石子直到连续
  • 一些正在制作的“格林达姆”测试项目,以及“假无损”
  • 个人项目
  • 北京 意大利学签 北京意大利签证中心 贵宾 vip vfs
  • 第1周
  • 多商家在线客服系统 - 客服用户表设计方案
  • 九月22号
  • 25.9.22 继续MySQL
  • 使用python读取windows注册表
  • 当日总结
  • 3123004481
  • 使用python读取windows日志表
  • 开机RAM分析调试SOP
  • 9.20 模拟赛 T4
  • 2025.9.21 测试 (a1a2a3a4a5)
  • 原码、反码和补码
  • Русский язык
  • 基于Hex Editor Neo的二进制文件模板
  • 【F#学习】字符
  • kubebuilder创建Operator示例
  • 集训总结(八)
  • 使用try-finally结构执行状态重置
  • java03预习
  • x6831卡顿分析
  • 实测对比:权威榜单之微信排版软件Top5(含详细测评)
  • 【F#学习】布尔运算优先级