#include <bits/stdc++.h>
using namespace std;
//#define int long long
mt19937_64 rd(time(NULL));
const int N = 1e6 + 5;
const int SWAP = 1;
const int ADD = 2;
const int SORT = 3;
const int COUNT = 4;
int n, q;
int a[N];
int sa[N];
long long hash_val[N];
int par[N];
long long h[N], sh[N];
int cnt;
map <long long, int> mp;
long long ans;
void read_input() {
cin >> n >> q;
for (int i = 1; i <= n; i++)
cin >> a[i];
}
void pre_ds() {
for (int i = 0; i <= 1e6; i++) {
hash_val[i] = uniform_int_distribution<long long>(0, 1e18)(rd);
}
for (int i = 0; i <= n; i++) {
par[i] = -1;
}
}
int root (int u) {
return par[u] < 0 ? u : par[u] = root(par[u]);
}
bool violate (int u) {
return h[u] != sh[u];
}
void del (int u) {
u = root(u);
if (!violate(u))
return;
cnt--;
mp[sh[u] - h[u]] -= -par[u];
ans -= -par[u] * mp[h[u] - sh[u]];
}
void add (int u) {
u = root(u);
if (!violate(u))
return;
cnt++;
ans += -par[u] * mp[h[u] - sh[u]];
mp[sh[u] - h[u]] += -par[u];
}
bool join (int u, int v) {
u = root(u);
v = root(v);
if (u == v)
return false;
del(u);
del(v);
if (par[u] > par[v])
swap(u, v);
h[u] += h[v];
sh[u] += sh[v];
par[u] += par[v];
par[v] = u;
add(u);
return true;
}
void build_dsu() {
for (int i = 1; i <= n; i++) {
sa[i] = a[i];
}
sort(sa + 1, sa + n + 1);
for (int i = 1; i <= n; i++) {
h[i] = hash_val[a[i]];
sh[i] = hash_val[sa[i]];
if (a[i] != sa[i]) {
add(i);
}
}
}
void solve() {
while (q--) {
int t;
cin >> t;
if (t == SWAP) {
int u, v;
cin >> u >> v;
int ru = root(u);
int rv = root(v);
if (ru == rv) {
swap(a[u], a[v]);
continue;
}
del(ru);
del(rv);
h[ru] -= hash_val[a[u]];
h[rv] -= hash_val[a[v]];
h[ru] += hash_val[a[v]];
h[rv] += hash_val[a[u]];
add(ru);
add(rv);
swap(a[u], a[v]);
}
else if (t == ADD) {
int u, v;
cin >> u >> v;
join(u, v);
}
else if (t == SORT) {
cout << (cnt == 0 ? "DA\n" : "NE\n");
}
else {
cout << ans << "\n";
}
}
}
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("bb.cpp", "r", stdin);
read_input();
pre_ds();
build_dsu();
solve();
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
8148 KB |
Output is correct |
2 |
Correct |
14 ms |
8096 KB |
Output is correct |
3 |
Correct |
14 ms |
8132 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
8148 KB |
Output is correct |
2 |
Correct |
13 ms |
8148 KB |
Output is correct |
3 |
Correct |
12 ms |
8148 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
8148 KB |
Output is correct |
2 |
Correct |
12 ms |
8148 KB |
Output is correct |
3 |
Correct |
15 ms |
8148 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
8148 KB |
Output is correct |
2 |
Correct |
12 ms |
8148 KB |
Output is correct |
3 |
Correct |
12 ms |
8272 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
8228 KB |
Output is correct |
2 |
Correct |
13 ms |
8144 KB |
Output is correct |
3 |
Correct |
13 ms |
8288 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
8660 KB |
Output is correct |
2 |
Correct |
17 ms |
8612 KB |
Output is correct |
3 |
Correct |
18 ms |
8664 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
53 ms |
11768 KB |
Output is correct |
2 |
Correct |
81 ms |
13172 KB |
Output is correct |
3 |
Correct |
118 ms |
16356 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
837 ms |
38412 KB |
Output is correct |
2 |
Correct |
3653 ms |
128784 KB |
Output is correct |
3 |
Correct |
4258 ms |
183080 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1667 ms |
77548 KB |
Output is correct |
2 |
Correct |
2965 ms |
98444 KB |
Output is correct |
3 |
Correct |
1221 ms |
86212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
713 ms |
43272 KB |
Output is correct |
2 |
Correct |
1955 ms |
82568 KB |
Output is correct |
3 |
Correct |
1228 ms |
86416 KB |
Output is correct |