Official Analysis (C++)

Explanation

If you've done Wormhole Sort, this problem should look a bit familiar. From that problem's editorial, we know that it's possible to sort a component iff each positions' sorted position is in the same component as itself. This motivates a DSU-esque solution (for more info look at the Guide solution for Wormhole Sort).

Hashing

The main issue is addressing type 3 and type 4 queries. We need to be able to efficiently check if a component can be sorted, and if it can't, we also need to see how many components it can be paired up with so that they can be sorted as a whole.

To do this, we have to check if a component has all the needed numbers for it to be able to be rearranged into sorted order.

For example, say this was our (0-indexed) array:

A component that consisted of the indexes $0$, $3$, and $4$ would need the numbers $2$, $7$, and $7$ to be sortable.

We can get all the needed numbers by sorting the given array and getting the numbers at the positions of the components, but how can we quickly check if the two sets of numbers are the same? The answer is hashing.

If we assign each number a certain random number, we can obtain our hash by multiplying each random number by the number of times it occurs in the set.

For example, if our component was the multiset ${3, 3, 4, 4, 5}$, and $R_i$ would be the random number of $i$, our hash would be:

Each component should not only have a hash of its number, but also a hash of the numbers it's supposed to have. For example, if our component was just the number $3$ but needs a $4$ to be sorted, its hash and required hash would be $R_3$ and $R_4$ respectively. Having this "required hash" allows us to quickly check if each component is sortable or not.

When executing a union operation (aka a type 1 query), we can add the hashes and required hashes of the two components to get the hash of the combined component. When swapping two array elements (a type 2 query), we add and subtract the swapped elements' random values from each component, while leaving the required hashes untouched.

Tracking "Bad" Components

However, when updating components, we also have to keep track of all the (henceforth referred to as "bad") components in the array to answer the output queries.

First, we need the number of bad components after each modification. To answer a type 3 query, we check if there's any bad components. If there are, we output NE, and otherwise, we output DA.

However, answering type 4 queries are a bit more tricky. We need some way to match up components such that the sum of their required hashes equals the sum of their actual hashes. In other words, if we let $x$ be the actual hash and $y$ be the required hash, we need to find all pairs of components ($i$ and $j$) such that the following is satisfied:

If we put the $i$s on one side, and $j$s on another, we get this:

This motivates us keeping a map of the difference between the required hash and actual hash and the number of positions whose components have such a difference. It doesn't matter whether we subtract the required hash from the actual hash or vice versa, as long as we stay consistent. We also keep track of the number of pairs of bad components that can be matched up.

When adding or removing a bad component, we get its difference $d$ and see how many positions whose components have the difference $-d$ through the map to update the number of pairs.

Implementation

Time Complexity: $\mathcal{O}(Q \cdot \alpha(N))$

Chance of Collision: $\mathcal{O}\left(\frac{N^2}{MOD_1 * MOD_2}\right)$

Copy
#include <algorithm>
#include <iostream>
#include <random>
#include <unordered_map>
#include <vector>

using std::cout;
using std::endl;
using std::vector;
using ll = long long;