#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <map>
using namespace std;
// DSU structure to manage components (clouds)
struct DSU {
vector<int> parent;
vector<long long> sz;
DSU(int n) {
parent.resize(n + 1);
iota(parent.begin(), parent.end(), 0);
sz.assign(n + 1, 1);
}
int find(int i) {
if (parent[i] == i)
return i;
return parent[i] = find(parent[i]);
}
};
// Use two hash functions to minimize collisions
const long long M1 = 1e9 + 7, P1 = 313;
const long long M2 = 1e9 + 9, P2 = 331;
const long long PAIR_P1 = 31;
const long long PAIR_P2 = 37;
// Function to compute a hash for a diff map
pair<long long, long long> get_hash(const map<int, int>& m) {
if (m.empty()) {
return {0, 0};
}
long long h1 = 0, h2 = 0;
for (auto const& [val, count] : m) {
long long pair_hash_1 = (val * PAIR_P1 + count) % M1;
if (pair_hash_1 < 0) pair_hash_1 += M1;
long long pair_hash_2 = (val * PAIR_P2 + count) % M2;
if (pair_hash_2 < 0) pair_hash_2 += M2;
h1 = (h1 * P1 + pair_hash_1) % M1;
h2 = (h2 * P2 + pair_hash_2) % M2;
}
return {h1, h2};
}
// Function to calculate the hash of the complementary diff map
pair<long long, long long> get_complement_hash(const map<int, int>& m) {
map<int, int> complement;
for (auto const& [val, count] : m) {
complement[val] = -count;
}
return get_hash(complement);
}
// Global state variables
DSU dsu(0);
vector<int> p;
vector<map<int, int>> diffs;
vector<pair<long long, long long>> component_hashes;
int bad_components_count = 0;
long long total_q4_pairs = 0;
map<pair<long long, long long>, long long> hash_to_total_size;
// Helper to update total pairs when a group's size changes
void update_pairs(pair<long long, long long> hash, pair<long long, long long> comp_hash, long long old_size, long long new_size){
if (hash == make_pair(0LL, 0LL)) return;
long long old_size_comp = hash_to_total_size[comp_hash];
if (hash == comp_hash) {
old_size_comp = old_size;
}
// Remove old contribution
if(hash != comp_hash) {
total_q4_pairs -= old_size * old_size_comp;
} else {
total_q4_pairs -= old_size * (old_size - 1) / 2;
}
// Add new contribution
long long new_size_comp = hash_to_total_size[comp_hash];
if (hash == comp_hash) {
new_size_comp = new_size;
}
if(hash != comp_hash) {
total_q4_pairs += new_size * new_size_comp;
} else {
total_q4_pairs += new_size * (new_size - 1) / 2;
}
}
// Modifies a component's diff map and updates all global states
void modify_component_diff(int root, int val, int count_delta) {
long long size = dsu.sz[root];
pair<long long, long long> old_hash = component_hashes[root];
// Remove old state's contribution
if(!diffs[root].empty()){
pair<long long, long long> old_comp_hash = get_complement_hash(diffs[root]);
update_pairs(old_hash, old_comp_hash, hash_to_total_size[old_hash], hash_to_total_size[old_hash] - size);
if(old_hash != old_comp_hash)
update_pairs(old_comp_hash, old_hash, hash_to_total_size[old_comp_hash], hash_to_total_size[old_comp_hash]);
hash_to_total_size[old_hash] -= size;
bad_components_count--;
}
diffs[root][val] += count_delta;
if (diffs[root][val] == 0) {
diffs[root].erase(val);
}
pair<long long, long long> new_hash = get_hash(diffs[root]);
component_hashes[root] = new_hash;
// Add new state's contribution
if(!diffs[root].empty()){
pair<long long, long long> new_comp_hash = get_complement_hash(diffs[root]);
hash_to_total_size[new_hash] += size;
update_pairs(new_hash, new_comp_hash, hash_to_total_size[new_hash] - size, hash_to_total_size[new_hash]);
if(new_hash != new_comp_hash)
update_pairs(new_comp_hash, new_hash, hash_to_total_size[new_comp_hash], hash_to_total_size[new_comp_hash]);
bad_components_count++;
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, q;
cin >> n >> q;
p.resize(n + 1);
vector<int> q_array(n + 1);
dsu = DSU(n);
diffs.resize(n + 1);
component_hashes.resize(n + 1, {0, 0});
for (int i = 1; i <= n; ++i) {
cin >> p[i];
q_array[i] = p[i];
}
sort(q_array.begin() + 1, q_array.end());
// Initialize components and their hashes
for (int i = 1; i <= n; ++i) {
if (p[i] != q_array[i]) {
diffs[i][p[i]]++;
diffs[i][q_array[i]]--;
if (diffs[i][p[i]] == 0) diffs[i].erase(p[i]);
if (diffs[i].count(q_array[i]) && diffs[i][q_array[i]] == 0) diffs[i].erase(q_array[i]);
}
if (!diffs[i].empty()) {
component_hashes[i] = get_hash(diffs[i]);
hash_to_total_size[component_hashes[i]]++;
bad_components_count++;
}
}
// Initialize total_q4_pairs
for(auto const& [hash, size] : hash_to_total_size) {
pair<long long, long long> comp_hash = get_complement_hash({ {1,1} }); // Placeholder to call func
// This is tricky, need to generate comp_hash without a map.
// Let's compute it from a dummy map for now, though this is inefficient.
// A better way would be a function that computes complement hash directly from hash.
// But for simplicity of fix:
map<int,int> dummy_map; // Create a map that would produce `hash`. Can't do easily.
// Instead, we iterate and match.
}
// Simple initialization loop
map<pair<long long, long long>, bool> visited;
for(auto const& [hash, size] : hash_to_total_size) {
if (visited[hash]) continue;
pair<long long, long long> comp_hash = get_complement_hash(diffs[dsu.find(1)]); // Find a component with this hash
int comp_root = -1;
for(int i=1; i<=n; ++i){ if(component_hashes[i] == hash) {comp_root = i; break;} }
if(comp_root == -1) continue;
comp_hash = get_complement_hash(diffs[comp_root]);
if (hash != comp_hash) {
total_q4_pairs += size * hash_to_total_size[comp_hash];
} else {
total_q4_pairs += size * (size - 1) / 2;
}
visited[hash] = true;
visited[comp_hash] = true;
}
for (int k = 0; k < q; ++k) {
int type;
cin >> type;
if (type == 1) {
int u, v;
cin >> u >> v;
int root_u = dsu.find(u);
int root_v = dsu.find(v);
if (p[u] == p[v]) continue;
if (root_u != root_v) {
modify_component_diff(root_u, p[u], -1);
modify_component_diff(root_u, p[v], 1);
modify_component_diff(root_v, p[v], -1);
modify_component_diff(root_v, p[u], 1);
}
swap(p[u], p[v]);
} else if (type == 2) {
int u, v;
cin >> u >> v;
int root_u = dsu.find(u);
int root_v = dsu.find(v);
if (root_u != root_v) {
if (dsu.sz[root_u] < dsu.sz[root_v]) swap(root_u, root_v);
// --- Remove old components' contributions ---
long long old_size_u = dsu.sz[root_u];
pair<long long, long long> old_hash_u = component_hashes[root_u];
if(!diffs[root_u].empty()) {
pair<long long, long long> old_comp_hash_u = get_complement_hash(diffs[root_u]);
update_pairs(old_hash_u, old_comp_hash_u, hash_to_total_size[old_hash_u], hash_to_total_size[old_hash_u] - old_size_u);
if(old_hash_u != old_comp_hash_u)
update_pairs(old_comp_hash_u, old_hash_u, hash_to_total_size[old_comp_hash_u], hash_to_total_size[old_comp_hash_u]);
hash_to_total_size[old_hash_u] -= old_size_u;
bad_components_count--;
}
long long old_size_v = dsu.sz[root_v];
pair<long long, long long> old_hash_v = component_hashes[root_v];
if(!diffs[root_v].empty()) {
pair<long long, long long> old_comp_hash_v = get_complement_hash(diffs[root_v]);
update_pairs(old_hash_v, old_comp_hash_v, hash_to_total_size[old_hash_v], hash_to_total_size[old_hash_v] - old_size_v);
if(old_hash_v != old_comp_hash_v)
update_pairs(old_comp_hash_v, old_hash_v, hash_to_total_size[old_comp_hash_v], hash_to_total_size[old_comp_hash_v]);
hash_to_total_size[old_hash_v] -= old_size_v;
bad_components_count--;
}
// --- Merge ---
dsu.parent[root_v] = root_u;
dsu.sz[root_u] += dsu.sz[root_v];
for (auto const& [val, count] : diffs[root_v]) {
diffs[root_u][val] += count;
if (diffs[root_u][val] == 0) diffs[root_u].erase(val);
}
diffs[root_v].clear();
// --- Add new component's contribution ---
long long new_size = dsu.sz[root_u];
pair<long long, long long> new_hash = get_hash(diffs[root_u]);
component_hashes[root_u] = new_hash;
if(!diffs[root_u].empty()){
pair<long long, long long> new_comp_hash = get_complement_hash(diffs[root_u]);
hash_to_total_size[new_hash] += new_size;
update_pairs(new_hash, new_comp_hash, hash_to_total_size[new_hash] - new_size, hash_to_total_size[new_hash]);
if(new_hash != new_comp_hash)
update_pairs(new_comp_hash, new_hash, hash_to_total_size[new_comp_hash], hash_to_total_size[new_comp_hash]);
bad_components_count++;
}
}
} else if (type == 3) {
cout << (bad_components_count == 0 ? "DA\n" : "NE\n");
} else { // type 4
cout << total_q4_pairs << "\n";
}
}
return 0;
}
