#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 1e9 + 7;
const int maxn = 1e6 + 1;
int sz[maxn], a[maxn], p[maxn], q[maxn];
ll P[maxn], Hsh = 20071030, h[maxn], H[maxn], ans = 0;
map<ll, ll> m;
void update(int t, ll val, int sze) {
if(val != 0) ans += t * m[-val] * sze;
m[val] += t * sze;
}
int find(int x) {
if(a[x] == x) return x;
else return a[x] = find(a[x]);
}
void unite(int u, int v) {
u = find(u);
v = find(v);
if(u == v) return;
if(sz[v] > sz[u]) swap(u, v);
update(-1, (h[v] - H[v]), sz[v]);
update(-1, (h[u] - H[u]), sz[u]);
sz[u] += sz[v];
a[v] = u;
h[u] += h[v];
H[u] += H[v];
update(1, (h[u] - H[u]), sz[u]);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, Q;
cin >> n >> Q;
P[0] = 1;
for(int i = 1; i < maxn; i++) {
P[i] = P[i - 1] * Hsh;
P[i] %= mod;
}
for(int i = 1; i <= n; i++) {
cin >> p[i];
q[i] = p[i];
a[i] = i;
sz[i] = 1;
}
sort(q + 1, q + n + 1);
for(int i = 1; i <= n; i++) {
h[i] = P[p[i]];
H[i] = P[q[i]];
update(1, (h[i] - H[i]), 1);
}
while(Q--) {
int t, u, v;
cin >> t;
if(t == 1) {
cin >> u >> v;
int U = find(u);
int V = find(v);
if(U == V) {
swap(p[u], p[v]);
continue;
}
update(-1, (h[U] - H[U]), sz[U]);
update(-1, (h[V] - H[V]), sz[V]);
h[U] -= P[p[u]];
h[V] -= P[p[v]];
swap(p[u], p[v]);
h[U] += P[p[u]];
h[V] += P[p[v]];
update(1, (h[U] - H[U]), sz[U]);
update(1, (h[V] - H[V]), sz[V]);
}
if(t == 2) {
cin >> u >> v;
unite(u, v);
}
if(t == 3) {
cout << (m[0] == n ? "DA" : "NE") << '\n';
}
if(t == 4) cout << ans << '\n';
}
return 0;
}
# | 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... |