PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Medium
PREREQUISITES:
Prefix sums, (optional) binary search, RMQ data structures (segment tree/sparse table)
PROBLEM:
You’re given an array A containing the elements 1 and 2.
Consider the following process:
- Start with p = 1.
- While p \le N, replace p with p + A_p.
This counts as one step.
f(A) is the number of steps taken by this process.
You can swap adjacent elements of A.
Let f(A) be the minimum number of swaps needed to maximize the value of f(A).
You must answer Q queries.
Each query gives you (L, R), and you must find the answer for the subarray [A_L, \ldots, A_R].
EXPLANATION:
From the easy version, we already know how to find the answer for a single array.
To answer range queries, let’s now figure out what information is needed.
Recall that the solution differed slightly depending on whether the number of twos in the array was even or odd.
Let’s work with the odd count first, since it was easier.
For an odd number of twos, at positions x_1, x_2, \ldots, x_k, the answer was simply
This is relatively easy to adapt to solving range queries.
For each i, define suf_i = (x_{i+1} - x_i - 1) + suf_{i+2}.
So, suf_i denotes the cost of pairing up all twos starting from the i-th one.
Now, for the subarray [L, R],
- Let p be the smallest index such that x_p \ge L.
This is the leftmost 2 in the subarray. - Let q be the largest index such that x_q \le E.
This is the rightmost 2 in the subarray. - The answer is then simply suf_p - suf_q + (R - x_q), because we must pair up all the twos starting from p, then exclude the pairs starting from q, and finally add in the cost of moving the 2 at x_q to the end.
So, after building the suffix sums, this case is answered in \mathcal{O}(1) time.
Finding p and q is simple, and can be done using binary search on the sorted list of positions; or even by just precomputing the appropriate positions/using some sort of prefix or suffix sums.
Next, consider an odd number of twos.
We had two cases: either pair everything up, or leave one occurrence of 2 unpaired (which then forces the last occurrence to the end of the subarray).
We consider them separately.
The case of pairing everything up is simple, and can be done in the same way using the suf array from the odd case.
Specifically, if we find p and q as described there, the cost here is simply suf_p - suf_{q+1}.
Now we come to the case of ‘skipping’ one element of a pair.
For this, suppose we ‘skip’ the element at index x_i.
Then, the cost will be
This can also be rewritten in terms of the suffix sums we formed, to be
Here, note that suf_p - suf_q + (N - x_q) is a constant.
So, we’re only really interested in choosing whichever i minimizes suf_{i+1} - suf_i, where the choices of i are \{p, p+2, p+4, \ldots, q-1\}.
This is a ‘range’ minimum query over the array suf, just that the range only includes elements with a certain parity.
To solve this, we can simply build two separate range minimum query structures: one for the even-indexed elements and one for the odd-indexed elements of suf.
Then, we simply perform a range minimum query on the appropriate one (whichever has the same parity as p) to get the answer!
Data structures to quickly handle range minimum queries include segment trees and sparse tables - pick your favorite.
TIME COMPLEXITY:
\mathcal{O}(N + Q\log N) per testcase.
CODE:
Tester's code (C++)
#include <algorithm>
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)
template<typename T>
void amin(T &a, T b) {
a = min(a,b);
}
template<typename T>
void amax(T &a, T b) {
a = max(a,b);
}
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
/*
*/
const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
template<typename T>
struct segtree {
// https://codeforces.com/blog/entry/18051
/*=======================================================*/
struct data {
pll a;
};
data neutral = {{inf2,inf2}};
data merge(data &left, data &right) {
data curr;
curr.a.ff = min(left.a.ff,right.a.ff);
curr.a.ss = min(left.a.ss,right.a.ss);
return curr;
}
void create(int i, T v) {
ll ind = i-n;
if(ind&1){
tr[i].a.ff = v;
}
else{
tr[i].a.ss = v;
}
}
void modify(int i, T v) {
}
/*=======================================================*/
int n;
vector<data> tr;
segtree() {
}
segtree(int siz) {
init(siz);
}
void init(int siz) {
n = siz;
tr.assign(2 * n, neutral);
}
void build(vector<T> &a, int siz) {
rep(i, siz) create(i + n, a[i]);
rev(i, n - 1, 1) tr[i] = merge(tr[i << 1], tr[i << 1 | 1]);
}
void pupd(int i, T v) {
modify(i + n, v);
for (i = (i + n) >> 1; i; i >>= 1) tr[i] = merge(tr[i << 1], tr[i << 1 | 1]);
}
data query(int l, int r) {
data resl = neutral, resr = neutral;
for (l += n, r += n; l <= r; l >>= 1, r >>= 1) {
if (l & 1) resl = merge(resl, tr[l++]);
if (!(r & 1)) resr = merge(tr[r--], resr);
}
return merge(resl, resr);
}
};
void solve(int test_case){
ll n,q; cin >> n >> q;
vector<ll> a(n+5);
rep1(i,n) cin >> a[i];
vector<ll> twos;
twos.pb(0);
rep1(i,n) if(a[i] == 2) twos.pb(i);
vector<ll> two_pref(n+5);
rep1(i,n) two_pref[i] = two_pref[i-1]+(a[i]==2);
ll siz = sz(twos)-1;
vector<ll> pair_sum(siz+5);
rev(i,siz-1,1){
pair_sum[i] = pair_sum[i+2]+(twos[i+1]-twos[i]-1);
}
vector<ll> pair_back(siz+5);
for(int i = 2; i <= siz; ++i){
pair_back[i] = pair_back[i-2]+(twos[i]-twos[i-1]-1);
}
vector<ll> fv(siz+5);
rep1(i,siz){
fv[i] = pair_back[i-1]+pair_sum[i+1];
}
segtree<ll> st(siz+5);
st.build(fv,siz+1);
while(q--){
ll l,r; cin >> l >> r;
ll o_r = r;
l = two_pref[l-1]+1, r = two_pref[r];
if(l > r){
cout << 0 << endl;
conts;
}
ll cnt = r-l+1;
if(cnt&1){
ll ans = pair_sum[l]-pair_sum[r]+(o_r-twos[r]);
cout << ans << endl;
conts;
}
ll res1 = pair_sum[l]-pair_sum[r+1];
ll res2 = inf2;
auto px = st.query(l,r).a;
if(l&1){
res2 = px.ff;
}
else{
res2 = px.ss;
}
res2 -= pair_back[l-1]+pair_sum[r];
res2 += o_r-twos[r];
ll ans = min(res1,res2);
cout << ans << endl;
}
}
int main()
{
fastio;
int t = 1;
cin >> t;
rep1(i, t) {
solve(i);
}
cerr << "RUN SUCCESSFUL" << endl;
return 0;
}