P3246 [HNOI2016] 序列 Solution

Description

给定序列 $a=(a_1,a_2,\cdots ,a_n)$，处理 $q$ 个查询 $(l,r)$.
对每个查询求出 $\sum _{[s,t]\in [l,r]}\underset{i=s}{\overset{t}{\max }}{a}_i$.

Limitations

$1\le n,q\le 10^5$
$|a_i|\le 10^9$
$2\text{s},500\text{MB}$

Solution

扫描线做法.
将询问离线，挂在 $r$ 上，从 $1\sim n$ 扫一遍，将子段转化为后缀.
我们用单调栈，在加入 $a_i$ 前弹掉所有 $>a_i$ 的数，并维护一个序列 $w$.
设弹出了 $p$，弹出后栈顶为 $q$，则需要在 $w$ 上把 $(q,p]$ 减去 $a_j$，加入 $a_i$ 时将 $(\text{top},i]$ 加上 $a_i$.
维护完单调栈后，标记一个版本.
然后对每个 $r=i$ 的查询，需要求 $w_{l\cdots r}$ 的历史和.
直接上 loj193 维护 $w$ 即可.

Code

$3.12\text{KB},0.96\text{s},16.91\text{MB}\text{(in total, C++20 with O2)}$
线段树删了.

#include <bits/stdc++.h>
using namespace std;using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
using ui128 = unsigned __int128;
using f4 = float;
using f8 = double;
using f16 = long double;template<class T>
bool chmax(T &a, const T &b){if(a < b){ a = b; return true; }return false;
}template<class T>
bool chmin(T &a, const T &b){if(a > b){ a = b; return true; }return false;
}namespace seg_tree {}
using seg_tree::SegTree;
using pii = pair<int, int>;signed main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int n, m;scanf("%d %d", &n, &m);vector<i64> a(n);for (int i = 0; i < n; i++) scanf("%lld", &a[i]);vector<vector<pii>> adj(n);for (int i = 0, l, r; i < m; i++) {scanf("%d %d", &l, &r), l--, r--;adj[r].emplace_back(l, i);}stack<int> stk;SegTree sgt(n);vector<i64> ans(m);for (int i = 0; i < n; i++) {while (!stk.empty() && a[stk.top()] > a[i]) {int j = stk.top(); stk.pop();if (stk.empty()) sgt.range_add(0, j, -a[j]);else sgt.range_add(stk.top() + 1, j, -a[j]);}if (stk.empty()) sgt.range_add(0, i, a[i]);else sgt.range_add(stk.top() + 1, i, a[i]);stk.push(i);sgt.apply(0, 0, 0, 1);for (auto [j, id] : adj[i]) ans[id] = sgt.range_hsum(j, i);}for (int i = 0; i < m; i++) printf("%lld\n", ans[i]);return 0;
}