PQ - Editorial

editorial
,
1

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

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

DIFFICULTY:

2692

PREREQUISITES:

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