# PROBLEM LINK:

Setter: Danny Boy
Tester: Harris Leung
Editorialist: Trung Dang

2692

RMQ, Sweep Line

# PROBLEM:

Please look at the original statement from the link above; the LaTeX here is broken and I don’t know how to fix …

# EXPLANATION:

Denote subarrays to be either positive or negative depending on its score Notice that there is no reason for a negative subarray to have length larger than 1, since we can always divide such a subarray into subarrays of size 1 without changing the score.

Suppose we are fixing X. Let’s see how we can efficiently divide A:

• If A as a whole is a positive array, we should keep A as is.
• Else, let A_M be the largest element in A. Notice that any subarray containing A_M is a negative subarray, so we simply make A_M into its own negative subarray, and solve the left part [1, M - 1] and the right part [M + 1, N] recursively and independently.

This is how we can solve the problem with a fixed X. How about solving the problem with multiple X's (which is the original problem we are trying to solve)? We solve it using sweep line:

• The score is initially \sum_{i = 1}^{N} A_i.
• Consider the array A, and let Max(A) - SecondMax(A) = T. If X > T, then A is intact; otherwise if X \le T, then A is divided up into 3 subarrays as we discussed above. We store an event point: at X = T, the array A is divided up, and so the score is decreased by -2 A_M.
• Let’s go recursively to A_{[1, M - 1]}. This division only exists when X \le T. Again, let Max(A_{[1, M - 1]}) - SecondMax(A_{[1, M - 1]}) = T', then A_{[1, M - 1]} is intact when T' < X \le T, and is divided when X \le min(T', T). Therefore, we again store an event point: at X = \min(T, T'), A_{[1, M - 1]} is divided up, and the score is decreased by \max(A_{[1, M - 1]}).
• and so on.

After we recursively solve for all possible divisions, each query is then easily solved using the constructed event points.

# TIME COMPLEXITY:

Time complexity is O(N \log N) for each test case.

# SOLUTION:

Setter's Solution
#include <bits/stdc++.h>
#define ll long long
#define int long long
#define fi first
#define se second
#define mat vector<vector<ll>>
using namespace std;
void db() {cout << '\n';}
template <typename T, typename ...U> void db(T a, U ...b) {cout << a << ' ', db(b...);}
#ifdef Cloud
#define file freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#else
#define file ios::sync_with_stdio(false); cin.tie(0)
#endif
const int N = 300000, mod = 1e9 + 7, inf = 1e9 + 1;
vector<int> a;
struct range{
int l, r, dif;
bool operator < (const range &i) const{
return dif < i.dif;
}
};
struct seg{
int l, r, mid;
pair<int, int> ma;
seg *ch[2]{};
pair<int, int> maq(int _l, int _r){
if (_l <= l and _r >= r) return ma;
if (_l > r or _r < l) return {-1, -1};
return max(ch[0]->maq(_l, _r), ch[1]->maq(_l, _r));
}
void set(int pos, pair<int, int> val){
if (l == r) return void(ma = val);
if (pos <= mid) ch[0]->set(pos, val);
else ch[1]->set(pos, val);
ma = max(ch[0]->ma, ch[1]->ma);
}
seg(int _l, int _r) : l(_l), r(_r), mid(l + r >> 1){
if (l < r) ch[0] = new seg(l, mid), ch[1] = new seg(mid + 1, r);
}
} *rt;
int dif(int l, int r){
if (l == r) return inf;
pair<int, int> ma = rt->maq(l, r);
rt->set(ma.se, {-1, -1});
pair<int, int> sma = rt->maq(l, r);
rt->set(ma.se, ma);
return ma.fi - sma.fi;
}
ll ans = 0;
priority_queue<range> pq;
void godown(int l, int r, int x){
pair<int, int> ma = rt->maq(l, r);
ans -= ma.fi * 2;
if (ma.se > l)
pq.push({l, ma.se - 1, dif(l, ma.se - 1)});
if (ma.se < r)
pq.push({ma.se + 1, r, dif(ma.se + 1, r)});
}
void solve(){
int n, q;
cin >> n >> q;
vector<pair<int, int>> x;
a.resize(n);
ans = 0;
while (!pq.empty()) pq.pop();
rt = new seg(0, n - 1);
for (int i = 0; i < n; i++) {
cin >> a[i];
ans += a[i];
rt->set(i, {a[i], i});
}
for (int i = 0; i < q; i++) {
int X;
cin >> X;
x.push_back({X, i});
}
sort(x.begin(), x.end());
reverse(x.begin(), x.end());
pq.push({0, n - 1, dif(0, n - 1)});
int Ans[q];
for (auto i : x){
while (!pq.empty() and pq.top().dif >= i.fi){
auto rg = pq.top();
pq.pop();
godown(rg.l, rg.r, i.fi);
}
Ans[i.se] = ans;
}
for (int i : Ans) cout << i << ' ';
cout << '\n';
}
signed main(){
file;
int t;
cin >> t;
while (t--) solve();
}

Tester's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
int n,q;
ll a[300001];
int lc[300001],rc[300001];
ll sum[300001],m2[300001];
pair<ll,int>qr[300001];
ll res[300001];
void dfs(int id){
//cout << "dfs " << id << ' ' << lc[id] << ' ' << rc[id] << endl;
sum[id]=a[id];
m2[id]=-1e18;
if(lc[id]!=0){
dfs(lc[id]);
sum[id]+=sum[lc[id]];
m2[id]=max(m2[id],a[lc[id]]);
}
if(rc[id]!=0){
dfs(rc[id]);
sum[id]+=sum[rc[id]];
m2[id]=max(m2[id],a[rc[id]]);
}
}
void solve(){
cin >> n >> q;
for(int i=1; i<=n ;i++){
cin >> a[i];
lc[i]=rc[i]=0;
}
int rt=0;
stack<int>s;
for(int i=1; i<=n ;i++){
while(!s.empty() && a[i]>a[s.top()]){
lc[i]=s.top();s.pop();
}
if(!s.empty()){
rc[s.top()]=i;
}
else rt=i;
s.push(i);
}
dfs(rt);
for(int i=1; i<=q ;i++){
ll x;cin >> x;
qr[i]={x,i};
}
sort(qr+1,qr+q+1);reverse(qr+1,qr+q+1);
priority_queue<pair<ll,int> >pq;
pq.push({a[rt]-m2[rt],rt});
ll ans=sum[rt];
for(int i=1; i<=q ;i++){
ll x=qr[i].fi;
while(!pq.empty() && pq.top().fi>=x){
int id=pq.top().se;
pq.pop();
ans-=a[id]*2;
if(lc[id]!=0) pq.push({a[lc[id]]-m2[lc[id]],lc[id]});
if(rc[id]!=0) pq.push({a[rc[id]]-m2[rc[id]],rc[id]});
}
res[qr[i].se]=ans;
}
for(int i=1; i<=q ;i++) cout << res[i] << ' ';
cout << '\n';
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);
int t;cin >> t;while(t--) solve();
}

Editorialist's Solution
#include <bits/stdc++.h>
#include <atcoder/segtree>
using namespace std;
using namespace atcoder;

const int INF = 1E9 + 7;

pair<int, int> id() { return {-INF, 0}; }
pair<int, int> add(pair<int, int> a, pair<int, int> b) { return max(a, b); }

int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t; cin >> t;
while (t--) {
int n, q; cin >> n >> q;
vector<int> a(n);
segtree<pair<int, int>, add, id> seg(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
seg.set(i, {a[i], i});
}
vector<pair<int, int>> eve;
function<void(int, int, int)> solve = [&](int l, int r, int border) {
if (l >= r) {
return;
} else {
auto [mx, ind] = seg.prod(l, r);
int smx = add(seg.prod(l, ind), seg.prod(ind + 1, r)).first;
border = min(border, mx - smx);
eve.push_back({border, 2 * mx});
solve(l, ind, border); solve(ind + 1, r, border);
}
};
for (int i = 0; i < q; i++) {
int u; cin >> u;
eve.push_back({u, -i});
}
solve(0, n, INF);
sort(eve.begin(), eve.end());
long long cur = accumulate(a.begin(), a.end(), 0LL);
vector<long long> ans(q);
for (auto [_, xd] : eve) {
if (xd > 0) {
cur -= xd;
} else {
ans[-xd] = -cur;
}
}
for (int i = 0; i < q; i++) {
cout << ans[i] << " \n"[i == q - 1];
}
}
}

2 Likes