//package ojuz;
import java.io.*;
import java.util.*;
import java.util.concurrent.ThreadLocalRandom;
public class zamjene {
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
String[] first = reader.readLine().split(" ");
int n = Integer.parseInt(first[0]), q = Integer.parseInt(first[1]);
DSU dsu = new DSU(n, Arrays.stream(reader.readLine().split(" ")).mapToInt(Integer::parseInt).map(i -> i - 1).toArray());
for (int i = 0; i < q; i++) {
String[] query = reader.readLine().split(" ");
int type = Integer.parseInt(query[0]);
if (type == 1) {
int a = Integer.parseInt(query[1]) - 1, b = Integer.parseInt(query[2]) - 1;
int aRoot = dsu.find(a), bRoot = dsu.find(b);
if (aRoot != bRoot) {
dsu.ungood(aRoot);
dsu.ungood(bRoot);
dsu.remove(aRoot);
dsu.remove(bRoot);
// remove the two elements
dsu.hashCurrent[aRoot] -= dsu.rng[dsu.a[a]];
dsu.hashCurrent[bRoot] -= dsu.rng[dsu.a[b]];
// add them back
dsu.hashCurrent[aRoot] += dsu.rng[dsu.a[b]];
dsu.hashCurrent[bRoot] += dsu.rng[dsu.a[a]];
dsu.good(aRoot);
dsu.good(bRoot);
dsu.add(aRoot);
dsu.add(bRoot);
}
// swap the elements
int temp = dsu.a[a];
dsu.a[a] = dsu.a[b];
dsu.a[b] = temp;
} else if (type == 2) {
int a = Integer.parseInt(query[1]) - 1, b = Integer.parseInt(query[2]) - 1;
dsu.unite(a, b);
} else if (type == 3) {
writer.write(dsu.good == dsu.groups ? "DA" : "NE");
writer.newLine();
} else {
writer.write(String.valueOf(dsu.ans));
writer.newLine();
}
}
writer.flush();
}
static class DSU {
// multiset of hashCurrent[i] - hashSorted[i]
// this probably doesnt need to be a multiset, except for 0
public final Map<Long, Integer> freq = new HashMap<>();
public final int[] p, a, sorted, sz;
public final long[] hashCurrent, hashSorted, rng;
public long ans;
public int good, groups;
public DSU(int n, int[] a) {
this.a = a;
int[] temp = a.clone();
Arrays.sort(temp);
this.sorted = temp;
this.p = new int[n];
Arrays.setAll(p, i -> i);
this.hashCurrent = new long[n];
this.hashSorted = new long[n];
this.rng = new long[1_000_000];
Arrays.setAll(rng, i -> ThreadLocalRandom.current().nextLong());
Arrays.setAll(hashCurrent, i -> rng[a[i]]);
Arrays.setAll(hashSorted, i -> rng[sorted[i]]);
this.sz = new int[n];
Arrays.fill(this.sz, 1);
for (int i = 0; i < n; i++) {
good(i);
add(i);
}
this.groups = n;
}
public int find(int i) {
return p[i] == i ? i : (p[i] = find(p[i]));
}
public void unite(int a, int b) {
if ((a = find(a)) == (b = find(b))) return;
if (sz[a] > sz[b]) {
unite(b, a);
return;
}
ungood(a);
ungood(b);
remove(a);
remove(b);
p[a] = b;
// hashCurrent will be modified by the main code
hashCurrent[b] += hashCurrent[a];
hashSorted[b] += hashSorted[a];
sz[b] += sz[a];
groups--;
good(b);
add(b);
}
public void good(int i) {
if (hashSorted[i] == hashCurrent[i]) good++;
}
public void ungood(int i) {
if (hashSorted[i] == hashCurrent[i]) good--;
}
public void remove(int i) {
long key = hashCurrent[i] - hashSorted[i];
if (key == 0) return;
freq.merge(key, -sz[i], Integer::sum);
ans -= (long) freq.getOrDefault(-key, 0) * sz[i];
}
public void add(int i) {
long key = hashCurrent[i] - hashSorted[i];
if (key == 0) return;
freq.merge(key, sz[i], Integer::sum);
ans += (long) freq.getOrDefault(-key, 0) * sz[i];
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |