ABC480G
2026-10-20 19:08:07
发布于：广东
15阅读
0回复
0点赞
Difficulty：4.4（青下位）/ Easy
简单典题。
定义 为 结尾的答案。注意到转移时要动态维护 ，考虑对 和 上个单调栈，区间 chkmax / chkmin 相当于区间加减，上个线段树优化即可。
#include <bits/stdc++.h>
namespace cjdst{
typedef long long ll;
typedef std::pair <int, int> pii;
typedef std::pair <ll, ll> pll;
void init(){
std::ios::sync_with_stdio(0);
std::cin.tie(0), std::cout.tie(0);
}
const int N = 800000;
ll a[N + 5];
ll dp[N + 5];
ll tr[N + 5], lazytag[N + 5];
std::vector <pll> mx{{0, 0x3f3f3f3f3f3f3f3fll}}, mn{{0, -0x3f3f3f3f3f3f3f3fll}};
int n;
void push_down(int u){
tr[u << 1] += lazytag[u];
tr[u << 1 | 1] += lazytag[u];
lazytag[u << 1] += lazytag[u];
lazytag[u << 1 | 1] += lazytag[u];
lazytag[u] = 0;
}
void modify(int u, int l, int r, int l2, int r2, ll val){
if(l >= l2 && r <= r2){
tr[u] += val;
lazytag[u] += val;
// std::cout << "qwq " << u << ' ' << l << ' ' << r << ' ' << tr[u] << '\n';
return;
}
push_down(u);
int mid = (l + r) >> 1;
if(l2 <= mid) modify(u << 1, l, mid, l2, r2, val);
if(r2 > mid) modify(u << 1 | 1, mid + 1, r, l2, r2, val);
tr[u] = std::min(tr[u << 1], tr[u << 1 | 1]);
}
void modify_idx(int u, int l, int r, int idx, ll val){
if(l == r){
tr[u] = val;
// std::cout << "qwq " << u << ' ' << l << ' ' << r << ' ' << tr[u] << '\n';
return;
}
push_down(u);
int mid = (l + r) >> 1;
if(idx <= mid) modify_idx(u << 1, l, mid, idx, val);
else modify_idx(u << 1 | 1, mid + 1, r, idx, val);
tr[u] = std::min(tr[u << 1], tr[u << 1 | 1]);
}
ll query(int u, int l, int r, int l2, int r2){
if(l >= l2 && r <= r2) return tr[u];
push_down(u);
int mid = (l + r) >> 1;
ll ans = 0x3f3f3f3f3f3f3f3fll;
if(l2 <= mid) ans = std::min(ans, query(u << 1, l, mid, l2, r2));
if(r2 > mid) ans = std::min(ans, query(u << 1 | 1, mid + 1, r, l2, r2));
return ans;
}
void test_tr(int u, int l, int r){
if(l == r){
std::cout << l << ' ' << r << ' ' << tr[u] << '\n';
return;
}
push_down(u);
int mid = (l + r) >> 1;
test_tr(u << 1, l, mid);
test_tr(u << 1 | 1, mid + 1, r);
}
ll tmp_ds[N + 5];
void test(){
for(int i = 1; i <= n + 1; i++){
std::cout << tmp_ds[i] << ' ';
}
std::cout << '\n';
}
void _modify(int l, int r, ll val){
// std::cout << "[" << l << ", " << r << "] += " << val << '\n';
// for(int i = l; i <= r; i++) tmp_ds[i] += val;
// test();
modify(1, 1, n + 2, l + 1, r + 1, val);
}
void _modify_idx(int idx, ll val){
// std::cout << idx << " = " << val << '\n';
// tmp_ds[idx] = val;
// test();
modify_idx(1, 1, n + 2, idx + 1, val);
}
ll _query(ll l, ll r){
// std::cout << "Query [" << l << ", " << r << "]" << '\n';
return query(1, 1, n + 2, l + 1, r + 1);
return 0;
}
void solve(){
std::cin >> n;
for(int i = 1; i <= n; i++){
std::cin >> a[i];
}
memset(tr, 63, sizeof(tr));
// memset(tmp_ds, 63, sizeof(tmp_ds));
_modify_idx(1, 0);
for(int i = 1; i <= n; i++){
pll lst, lst2;
// std::cout << i << ":\n";
// std::cout << "Mx\n";
while(mx.back().second <= a[i]){
// std::cerr << "Pop!\n";
lst = mx.back();
mx.pop_back();
_modify(mx.back().first + 1, lst.first, -lst.second);
}
_modify(mx.back().first + 1, i, a[i]);
// std::cout << "Mn\n";
while(mn.back().second >= a[i]){
lst2 = mn.back();
mn.pop_back();
_modify(mn.back().first + 1, lst2.first, lst2.second);
}
_modify(mn.back().first + 1, i, -a[i]);
mx.push_back({i, a[i]});
mn.push_back({i, a[i]});
if(i == 1) continue;
// test_tr(1, 1, n);
dp[i] = _query(0, i - 1);
_modify_idx(i + 1, dp[i]);
// std::cout << i << ": " << dp[i] << '\n';
}
std::cout << dp[n] << '\n';
}
}
int main(){
cjdst::init();
int T = 1;
// std::cin >> T;
for(int _ = 1; _ <= T; _++){
cjdst::solve();
}
}
时间复杂度：。
有帮助，赞一个