PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Easy-Med
PREREQUISITES:
Segment trees (with lazy propagation)
PROBLEM:
You’re given a permutation P.
You can perform the following operation:
- Choose a pivot index i such that P_i = i.
- Then, rearrange the elements before i among those indices, and the elements after i among those indices.
You’re also given several updates to P, each of which swaps two elements of P.
After each update, find the minimum number of operations needed to sort P, if it’s possible at all.
EXPLANATION:
Recall that we had the following criteria for computing the answer for a fixed permutation.
- If P is sorted, the answer is 0.
- If there exists an i such that P_i = i and 1, \ldots, i-1 appear among positions 1, \ldots, i-1 then the answer is 1.
- If there’s a fixed point to the right of 1, or a fixed point to the left of N, the answer is 2.
- If there are at least two non-adjacent fixed points; or there’s a fixed point i such that it can create another fixed point \lt i-1 or \gt i+1, the answer is 3.
- If there’s a fixed point i such that i-1 and i+1 can both be fixed, the answer is 4.
- If all else fails, the answer is -1.
Our task is now to maintain this information across swap updates.
Most of these are relatively easy to check.
Note that each swap affects only two elements, so we can always store the actual permutation P, the positions of elements, and the set of currently fixed points (call this F).
Now,
- Checking if P is sorted is easy: check if every element is fixed, i.e. F has size N.
- \text{ans} = 2 is another easy one: only the leftmost and rightmost fixed points need to be known, as well as the positions of 1 and N.
- \text{ans} = 4 is also quite easy to check: if it ever comes to that point, then there must be \lt 2 fixed points; so we can simply try all of them and look at positions of i-1 and i+1.
- \text{ans} = 3 requires a little more work.
First, check if the smallest and largest elements of F are adjacent or not: if they aren’t, we immediately know the answer is 3.
If they are adjacent, there’s at most two of them, so we can now test each one.
To test i, we need to know the smallest element in some prefix and the largest element in some suffix, on a dynamic array. This is a classical task, and can be done in \mathcal{O}(\log N) using a segment tree.
Each update to the permutation causes two updates to the permutation so there’s no issue with speed.
That leaves \text{ans} = 1, which is not all that obvious to check for.
Consider the following setup: create an array A of length N, initialized to [1, 2, 3, \ldots, N].
Then, for each index i, subtract 1 from the entire suffix starting at \max(i, P_i).
For example, if P = [2, 1, 4, 3], the resulting array A will equal [1, 0, 1, 0].
Essentially, A_i equals i minus the number of elements \leq i that are present till i.
In particular A_i = 0 if and only if all the elements 1, 2, \ldots, i appear at positions \leq i.
Now, for \text{ans} = 1 recall that we’re looking for an index i such that P_i = i and all of 1, 2, \ldots, i-1 appear till i-1.
This means we want P_i = i and A_{i-1} = 0.
However, observe that this in turn implies A_i = 0 as well.
So, what we’re really looking for is two adjacent zeros in A (we treat A_0 to be 0 as well).
We also need to keep A updated: each update to P corresponds to a couple of suffix additions/subtractions on A.
This is now a classical task, which can be solved with the additional observation that the values in A will always be non-negative.
Let’s build a segment tree on A that stores in each node:
- The minimum value.
- A flag denoting whether there are two adjacent minimums within this node.
- The leftmost and rightmost occurrences of the minimum within this node.
Merging two nodes is easy: if their minimums differ, take the one with a smaller minimum; if the minimums are equal then take values from both, and check for adjacency across the middle (by comparing the rightmost occurrence in the left node with the leftmost occurrence in the right node).
Range addition updates can be handled using lazy propagation: note that when applying an update to an entire node, only the value of the minimum will change: positional data won’t.
With this segment tree, checking for \text{ans} = 1 becomes straightforward: just query the entire tree, and check if both the minimum value is 0, and if there’s an adjacent pair of minimums in A.
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 {
using T = array<int, 4>;
T unit = {inf, 0, 0, 0};
int lo, hi;
T f(T a, T b) {
if (b == unit) return a;
if (a == unit) return b;
if (a[0] < b[0]) {
a[3] = 0;
return a;
}
if (a[0] > b[0]) {
b[2] = 0;
return b;
}
a[1] |= b[1];
a[1] |= (a[3] and b[2]);
a[3] = b[3];
return a;
}
Node *l = 0, *r = 0;
int madd = 0;
T val = unit;
Node(int _lo,int _hi):lo(_lo),hi(_hi){
if (lo+1 == hi) val[2] = val[3] = 1;
}
T query(int L, int R) {
if (R <= lo || hi <= L) return unit;
if (L <= lo && hi <= R) return val;
push();
return f(l->query(L, R), r->query(L, R));
}
void add(int L, int R, int x) {
if (R <= lo || hi <= L) return;
if (L <= lo && hi <= R) {
madd += x;
val[0] += x;
}
else {
push(), l->add(L, R, x), r->add(L, R, x);
val = f(l->val, r->val);
}
}
void push() {
if (!l) {
int mid = lo + (hi - lo)/2;
l = new Node(lo, mid); r = new Node(mid, hi);
}
if (madd)
l->add(lo,hi,madd), r->add(lo,hi,madd), madd = 0;
}
};
/**
* Point-update Segment Tree
* Source: kactl
* Description: Iterative point-update segment tree, ranges are half-open i.e [L, R).
* f is any associative function.
* Time: O(logn) update/query
*/
template<class T, T unit = T()>
struct SegTree {
T f(T a, T b) {
a[0] = min(a[0], b[0]);
a[1] = max(a[1], b[1]);
return a;
}
vector<T> s; int n;
SegTree(int _n = 0, T def = unit) : s(2*_n, def), n(_n) {}
void update(int pos, int val) {
for (s[pos += n] = {val, 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);
/**
* 0: sorted
* 1: some p[i] = i should have 1...i-1 to its left
* 2: left/right pivots, and pos(1)/pos(n)
* 3: range min/max queries
* 4: pos(n/2), pos(n/2-1), pos(n/2+1)
*/
int t; cin >> t;
while (t--) {
int n; cin >> n;
int q = 0;
cin >> q;
vector p(n+1, 0), pos(n+1, 0);
set<int> fixed;
for (int i = 1; i <= n; ++i) {
cin >> p[i];
pos[p[i]] = i;
if (p[i] == i) fixed.insert(i);
}
Node *seg = new Node(1, n+1);
SegTree<array<int, 2>, {INT_MAX, INT_MIN}> mnmxseg(n+1);
auto ans = [&] () {
// 0
if (size(fixed) == n) return 0;
if (size(fixed) == 0) return -1;
// 1
if (pos[1] == 1) return 1;
auto [mnval, flag, _, __] = seg -> query(1, n+1);
if (mnval == 0 and flag == 1) return 1;
// 2
int L = *begin(fixed), R = *rbegin(fixed);
if (pos[1] < R or pos[n] > L) return 2;
// 3
if (L+1 < R) return 3;
for (int i : {L, R}) {
// query [1...i-1] and [i+1...n]
if (i > 2) {
int mn = mnmxseg.query(1, i)[0];
if (mn < i-1) return 3;
}
if (i+2 <= n) {
int mx = mnmxseg.query(i+1, n+1)[1];
if (mx > i+1) return 3;
}
}
// 4
if (n%2 == 1) {
int m = (n+1)/2;
if (pos[m-1] < pos[m] and pos[m+1] > pos[m]) return 4;
}
return -1;
};
auto upd = [&] (int i, int j) {
int x = p[i], y = p[j];
seg -> add(max(x, pos[x]), n+1, 1);
seg -> add(max(y, pos[y]), n+1, 1);
for (int v : {i, j}) {
if (p[v] == v) fixed.erase(v);
}
swap(p[i], p[j]);
swap(pos[x], pos[y]);
for (int v : {i, j}) {
if (p[v] == v) fixed.insert(v);
}
mnmxseg.update(pos[x], x), mnmxseg.update(pos[y], y);
seg -> add(max(x, pos[x]), n+1, -1);
seg -> add(max(y, pos[y]), n+1, -1);
};
for (int i = 1; i <= n; ++i)
seg -> add(i, i+1, i-inf);
for (int i = 1; i <= n; ++i) {
seg -> add(max(i, pos[i]), n+1, -1);
}
for (int i = 1; i <= n; ++i)
mnmxseg.update(i, p[i]);
cout << ans() << ' ';
while (q--) {
int x, y; cin >> x >> y;
upd(x, y);
cout << ans() << ' ';
}
cout << '\n';
}
}