PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Medium
PREREQUISITES:
Segment trees (or sets)
PROBLEM:
You’re given an array of length 2N that includes every integer in [1, N] twice each.
You can do the following:
- Choose an integer k and k indices i_1 \lt i_2 \lt\ldots\lt i_k
- For each j in [1, k] in order, move the element at index i_j to the start of the array.
A is called balanced if it’s possible to perform this operation and turn A into a palindrome.
Process Q updates to the array.
Each update will swap two elements at arbitrary positions.
After each update, report if A is balanced.
EXPLANATION:
From the solution to the easy version of the problem, we already know a simple greedy algorithm that tells us whether the array is balanced or not.
Since we clearly cannot run this for each query, let’s try to understand what it actually does.
For each integer x, let’s define f_x and s_x to be the indices containing the first and second occurrences of x in the array; with f_x \lt s_x always.
A closer look at the greedy algorithm reveals that we’re actually doing the following:
- Let L be an empty list.
- Process x in descending order of s_x (so we’re looking at second occurrences of elements in decreasing order.)
- If for the current x we have f_x \lt \text{back}(L) (or L is empty) then append f_x to L.
Otherwise, break immediately.
In the end, the indices in L are exactly the ones that we must choose in our operation.
If we look at this a bit deeper, the following can be observed.
Let’s arrange the values \{1, 2, \ldots, N\} in descending order of their s_x values - call this permutation P, so we have s_{P_i} \gt s_{P_{i+1}}.
Then, the array A is balanced if and only if the array f, when viewed under this permutation, is bitonic with a unique minimum, i.e. first decreases then increases.
That is, we must have some index m such that f_{P_1} \gt f_{P_2} \gt\ldots \gt f_{P_m} \lt f_{P_{m+1}} \lt\ldots\lt f_{P_N}.
(Note that m = 1 and m = N are also allowed, in which case the sequence becomes monotonic; this is fine.)
This follows from the fact that the first decreasing part corresponds exactly to the values that will be chosen by the subsequence we operate on; while the second ascending part corresponds to the remaining elements that do not move, and will be part of the “middle” palindrome - since their corresponding second-occurrences are decreasing, the first-occurrences must be increasing given that the first and second half are reverses of each other.
The condition about the array f being bitonic (under the appropriate permutation) is hence a necessary and sufficient condition for the array to be balanced.
The question now is, how do we maintain this check across updates?
Each swap can change the permutation P of second-occurrence order, and elements can move around a lot, so it’s not clear how we maintain the sequence f under the permutation.
However, here we can use a small trick to not have to worry about this at all - specifically, we utilize the fact that the values of s_x will always be distinct integers in [1, 2N].
Let’s define a new array B of length 2N, such that for each x we have B[s_x] = f_x.
N positions in the array B will be “empty”. (for implementation purposes, we can treat empty positions as containing -1, or really any constant you like which is outside [1, 2N].)
If we’re able to maintain this array B, observe that its non-empty elements will exactly form the sequence f when permuted by P, which is what we want!
Maintaining the array B is clearly trivial, after each swap at most two of its elements can change so it corresponds to just a couple of point updates.
Finally, we need to build some structure on the array B that will tell us whether its non-empty elements form a bitonic array with a unique minimum or not.
One way to do this, is to observe that an array is of this form if and only if it doesn’t contain a peak, i.e. an element that’s larger than both its neighbors.
So, we can for example build a segment tree on the array B, and store in each range the number of “peaks” present in it when looking at the non-empty positions.
To merge nodes, you’ll need to also know the leftmost and rightmost two non-empty elements in each range (to decide if the “middle” elements become peaks after a merge; since nothing else can become one if it wasn’t already.)
This leads to a fairly easy to implement \mathcal{O}(\log N)-per-update solution; for implementation details you can see the code below.
It’s in fact possible to forego the segment tree entirely and just use a handful of sets to maintain the information we need, though this leads to a rather unwieldy implementation (at least in comparison to the segment tree solution.)
If you’re interested, the tester’s code below does this.
TIME COMPLEXITY:
\mathcal{O}((N+Q)\log N) per testcase.
CODE:
Editorialist's code (C++)
// #include <bits/allocator.h>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 RNG(chrono::high_resolution_clock::now().time_since_epoch().count());
const int inf = 1e9;
struct Node {
int peaks;
array<int, 2> left, right;
Node() {
peaks = 0;
left = right = {inf, inf};
}
};
Node unit;
template<class T>
struct SegTree {
T f(T a, T b) {
T res;
res.peaks = a.peaks + b.peaks;
if (a.right[1] != inf and b.left[0] != inf) {
res.peaks += a.right[0] > max(a.right[1], b.left[0]);
}
if (a.right[0] != inf and b.left[1] != inf) {
res.peaks += b.left[0] > max(a.right[0], b.left[1]);
}
// left
if (a.left[0] == inf) res.left = b.left;
else {
res.left = a.left;
if (a.left[1] == inf) res.left[1] = b.left[0];
}
// right
if (b.right[0] == inf) res.right = a.right;
else {
res.right = b.right;
if (b.right[1] == inf) res.right[1] = a.right[0];
}
return res;
}
vector<T> s; int n;
SegTree(int _n = 0, T def = unit) : s(2*_n, def), n(_n) {}
void update(int pos, T val) {
for (s[pos += n] = val; pos /= 2;)
s[pos] = f(s[pos * 2], s[pos * 2 + 1]);
}
T query(int b, int e) {
T ra = unit, rb = unit;
for (b += n, e += n; b < e; b /= 2, e /= 2) {
if (b % 2) ra = f(ra, s[b++]);
if (e % 2) rb = f(s[--e], rb);
}
return f(ra, rb);
}
};
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
int t; cin >> t;
while (t--) {
int n, q; cin >> n >> q;
vector a(2*n+1, 0), first(n+1, 0), second(n+1, 0);
for (int i = 1; i <= 2*n; ++i) {
cin >> a[i];
if (first[a[i]] == 0) first[a[i]] = i;
else second[a[i]] = i;
}
SegTree<Node> seg(2*n + 1);
auto upd = [&] (int x) {
Node cur;
cur.left[0] = cur.right[0] = first[x];
seg.update(second[x], cur);
};
auto del = [&] (int x) {
seg.update(second[x], unit);
};
for (int i = 1; i <= n; ++i) upd(i);
while (q--) {
int x, y; cin >> x >> y;
if (a[x] != a[y]) {
del(a[x]);
del(a[y]);
if (first[a[x]] == x) first[a[x]] = y;
else second[a[x]] = y;
if (first[a[x]] > second[a[x]]) swap(first[a[x]], second[a[x]]);
if (first[a[y]] == y) first[a[y]] = x;
else second[a[y]] = x;
if (first[a[y]] > second[a[y]]) swap(first[a[y]], second[a[y]]);
upd(a[x]);
upd(a[y]);
swap(a[x], a[y]);
}
if (seg.query(1, 2*n+1).peaks == 0) cout << "Yes\n";
else cout << "No\n";
}
}
}
Tester's code (C++)
#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;
void solve(int test_case){
ll n,Q; cin >> n >> Q;
n *= 2;
vector<ll> a(n+5);
rep1(i,n) cin >> a[i];
reverse(a.begin()+1,a.begin()+n+1); // operator on rev(A)
// for each x --> p[x] and q[x]
vector<ll> p(n+5,-1), q(n+5,-1);
rep1(i,n){
ll x = a[i];
if(p[x] == -1){
p[x] = i;
}
else{
q[x] = i;
}
}
// for a given value of p[x], what is the value of q[x]?
vector<ll> qh(n+5,-1);
rep1(x,n/2){
qh[p[x]] = q[x];
}
// maintain set of pos for each x
vector<set<ll>> posx(n+5);
rep1(i,n) posx[a[i]].insert(i);
set<ll> active_inds;
set<ll> dec_pos, inc_pos;
ll prev_guy = -1;
rep1(x,n){
if(qh[x] == -1) conts;
active_inds.insert(x);
if(prev_guy != -1){
if(qh[prev_guy] < qh[x]){
inc_pos.insert(prev_guy);
}
else{
dec_pos.insert(prev_guy);
}
}
prev_guy = x;
}
auto rem = [&](ll i){
// qh[i] should be removed
// find ind in active, remove left and right contrib, then ins left,right new pair
auto it = active_inds.find(i);
assert(it != active_inds.end());
// remove left contrib
if(it != active_inds.begin()){
auto j = *prev(it);
if(qh[j] < qh[i]){
inc_pos.erase(j);
}
else{
dec_pos.erase(j);
}
}
// remove right contrib
if(next(it) != active_inds.end()){
auto j = *next(it);
if(qh[i] < qh[j]){
inc_pos.erase(i);
}
else{
dec_pos.erase(i);
}
}
// merge left and right if both exist
if(it != active_inds.begin() and next(it) != active_inds.end()){
ll lp = *prev(it), rp = *next(it);
if(qh[lp] < qh[rp]){
inc_pos.insert(lp);
}
else{
dec_pos.insert(lp);
}
}
// erase i from active_inds
active_inds.erase(i);
};
auto ins = [&](ll i){
active_inds.insert(i);
auto it = active_inds.find(i);
assert(it != active_inds.end());
// remove left and right if both exist
if(it != active_inds.begin() and next(it) != active_inds.end()){
ll lp = *prev(it), rp = *next(it);
if(qh[lp] < qh[rp]){
inc_pos.erase(lp);
}
else{
dec_pos.erase(lp);
}
}
// ins left contrib
if(it != active_inds.begin()){
auto j = *prev(it);
if(qh[j] < qh[i]){
inc_pos.insert(j);
}
else{
dec_pos.insert(j);
}
}
// ins right contrib
if(next(it) != active_inds.end()){
auto j = *next(it);
if(qh[i] < qh[j]){
inc_pos.insert(i);
}
else{
dec_pos.insert(i);
}
}
};
auto upd = [&](ll x){
// update p[x] and q[x]
p[x] = *posx[x].begin();
q[x] = *(++posx[x].begin());
qh[p[x]] = q[x];
};
rep1(id,Q){
ll i,j; cin >> i >> j;
i = n-i+1, j = n-j+1;
if(a[i] != a[j]){
ll x = a[i], y = a[j];
swap(a[i],a[j]);
posx[x].erase(i), posx[x].insert(j);
posx[y].erase(j), posx[y].insert(i);
rem(p[x]), rem(p[y]);
qh[p[x]] = -1, qh[p[y]] = -1;
upd(x), upd(y);
ins(p[x]), ins(p[y]);
}
ll last_inc = -inf2, first_dec = inf2;
if(!inc_pos.empty()) last_inc = *inc_pos.rbegin();
if(!dec_pos.empty()) first_dec = *dec_pos.begin();
if(last_inc < first_dec) yes;
else no;
}
}
int main()
{
fastio;
int t = 1;
cin >> t;
rep1(i, t) {
solve(i);
}
cerr << "RUN SUCCESSFUL" << endl;
return 0;
}