POI - Cards

Time Complexity: $\mathcal O(N\log N)$

Explanation

We can use a segment tree to solve this problem.

For each segment tree node with the range $[l, r]$, we will store if it's possible to arrange the cards $l\dots r$ so that we either

• don't flip card $l$ and card $r$
• don't flip card $l$ and flip card $r$
• flip card $l$ and don't flip card $r$
• flip card $l$ and card $r$

We can represent these states in a 2 by 2 matrix bool[2][2] where the first dimension stores whether we flip card $l$ and the second dimension stores whether we flip card $r$.

To calculate the states for a specific segment tree node, we loop through all possible states of our left child node $(a, b)$ and all possible states of our right child node $(c, d)$. If the transition from $b$ to $c$ works, then $(a, d)$ works since we're only considering endpoints.

To perform a swap operation with index $i$ and $j$, we simply swap the cards at $i$ and $j$. We can just recalculate all nodes in the segment tree that are related to either $i$ or $j$. Since there are around $\mathcal O(\log N)$ ranges in the segment tree that contain $i$ or $j$, this whole swap operation takes $\mathcal O(\log N)$.

Additionally, we also have to print if we can form a non-decreasing list using the cards. To do this, if any states of the root node in our segment tree (which covers $[1, n]$) is possible, then our answer is yes (TAK), otherwise no (NIE).

Implementation

Copy
#include <bits/stdc++.h>
using namespace std;

const int N = 1 << 18;

int n, q, aa[N][2];
bool tt[N << 1][2][2];

void pull(int i, int l, int r) {
	memset(tt[i], 0, sizeof(tt[i]));

Alternate Solution

We can reduce the number of states stored in the segment tree to just two:

• The minimum last value of the interval given that we take the lesser side of the first card (denote this as $FF$)
• The minimum last value of the interval given that we take the greater side of the first card (denote this as $SS$)

Note that it will always be optimal to take the lesser side of the last side given that we can take both. This, in turn, prepares the current interval with the next merging step, if applicable.

Let's denote the array of cards as $A$, where $A.FF$ is the front side and $A.SS$ is the back side. Without loss of generality, assume that $A[i].FF \leq A[i].SS$ for all $i \in [1, n]$. We consider merging interval $u$ and $v$ to create interval $w$, where $w$ corresponds to the array elements $[l, r]$. Note that this implies $u$ corresponds to $[l, m]$ and $v$ corresponds to $[m + 1, r]$, where $m = \lfloor \frac {l + r} 2 \rfloor$

• $w.FF = \begin{cases} v.FF & u.FF \leq A[m + 1].FF \\ v.SS & A[tm + 1].FF < u.FF \leq A[tm + 1].SS \\ \infty & \text{otherwise}\end{cases}$
• $w.SS = \begin{cases} v.FF & u.SS \leq A[m + 1].FF \\ v.SS & A[tm + 1].FF < u.SS \leq A[tm + 1].SS \\ \infty & \text{otherwise}\end{cases}$

Note that we choose $\infty$ to be the default value, because under our merge conditions, infinity conveniently overrides all other operators. This means that if any point of the array is discontinuous (or unable to be made into a non-decreasing sequence), node $1$ in the segment tree, which corresponds to the entire array, will also have $w.FF = w.SS = \infty$.

Time Complexity: $\mathcal{O}(N\log{N})$

Implementation

Copy
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pll = pair<ll, ll>;

#define MP make_pair
#define FF first
#define SS second