P8037 [COCI2015-2016#7] Prokletnik 题解

如果你做过 GSS2，那么你会发现它们很像，都是询问最优子段的问题。

这里有一个 trick，对于这一类询问最优子段的问题，首先考虑将询问离线，然后扫描线。若当前扫描到 \(i\)，设 \(f_j\) 表示以 \(j\) 为左端点，\(i\) 为右端点的子段信息，可以维护 \(f_j\) 的历史最值求解。

如何理解这个历史最值。由于是扫描线依次添加每一个位置，那么 \(f_j\) 的历史最值即为以 \(j\) 为左端点，且右端点在 \([j, i]\) 的最优子段。可以用线段树维护区间历史最值。

那么问题在于如何维护 \(f_j\)。不妨设左小右大，那么左大右小将序列取倒数即可。

不难发现，若 \(i\) 能够成为最大值，则 \(\max\limits_{k\in[j,i]}{a_k} \le a_i\)。可以用单调栈维护 \(L_i\) 表示 \(i\) 左边第一个小于 \(a_i\) 的数的位置，则 \(j \in (L_i, i]\)。

考虑哪些 \(j\) 是合法的。在扫描线的同时维护一个单调栈，单调不减。那么在栈中的位置一定是合法的 \(j\)，弹出位置一定不合法。将不合法的位置标记，则 \((L_i, i]\) 中未被标记的位置即为所有合法的 \(j\)。用线段树区间修改即可。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 5;
int n, Q, a[N], L[N], ans[N];
struct node
{int l, r, id;
};
vector<node> q;
struct Tree
{int maxi, tag, hismaxi, histag;
}tree[N << 2];
#define ls (cur << 1)
#define rs (cur << 1 | 1)
#define mid (lt + rt >> 1)
void pushup(int cur)
{tree[cur].maxi = max(tree[ls].maxi, tree[rs].maxi);tree[cur].hismaxi = max(tree[ls].hismaxi, tree[rs].hismaxi);return;
}
void build(int cur, int lt, int rt)
{tree[cur] = {0, 0, 0, 0};if(lt == rt){tree[cur] = {-lt + 1, 0, 0, 0};return;}build(ls, lt, mid), build(rs, mid + 1, rt);return pushup(cur);
}
void addtag(int cur, int tag, int histag)
{tree[cur].hismaxi = max(tree[cur].hismaxi, tree[cur].maxi + histag), tree[cur].maxi += tag;tree[cur].histag = max(tree[cur].histag, tree[cur].tag + histag), tree[cur].tag += tag;return;
}
void pushdown(int cur)
{if(!tree[cur].tag && !tree[cur].histag)return;addtag(ls, tree[cur].tag, tree[cur].histag);addtag(rs, tree[cur].tag, tree[cur].histag);tree[cur].tag = 0, tree[cur].histag = 0;return;
}
void update(int cur, int lt, int rt, int l, int r, int val)
{if(r < lt || rt < l)return;if(l <= lt && rt <= r){tree[cur].tag += val, tree[cur].histag = max(tree[cur].histag, tree[cur].tag);tree[cur].maxi += val, tree[cur].hismaxi = max(tree[cur].hismaxi, tree[cur].maxi);return;}pushdown(cur);update(ls, lt, mid, l, r, val), update(rs, mid + 1, rt, l, r, val);return pushup(cur);
}
int query(int cur, int lt, int rt, int l, int r)
{if(r < lt || rt < l)return 0;if(l <= lt && rt <= r)return tree[cur].hismaxi;pushdown(cur);return max(query(ls, lt, mid, l, r), query(rs, mid + 1, rt, l, r));
}
void solve()
{stack<int> stk;for(int i = n; i; i--){while(!stk.empty() && a[stk.top()] < a[i])L[stk.top()] = i + 1, stk.pop();stk.push(i);}while(!stk.empty())L[stk.top()] = 1, stk.pop();build(1, 1, n);int i = 0;for(auto [l, r, id] : q){while(i < r){i++;while(!stk.empty() && a[stk.top()] > a[i])update(1, 1, n, stk.top(), stk.top(), INT_MIN), stk.pop();stk.push(i);update(1, 1, n, L[i], i, i);update(1, 1, n, L[i], i, -i);}ans[id] = max(ans[id], query(1, 1, n, l, r));}return;
}
signed main()
{cin.tie(0) -> sync_with_stdio(0);cin >> n >> Q;for(int i = 1; i <= n; i++)cin >> a[i];for(int i = 1; i <= Q; i++){int l, r;cin >> l >> r;q.push_back({l, r, i});}sort(q.begin(), q.end(), [](auto x, auto y){return x.r < y.r;});solve();for(int i = 1; i <= n; i++)a[i] = -a[i];solve();for(int i = 1; i <= Q; i++)cout << ans[i] << "\n";return 0;
}