#include <bits/stdc++.h>
#define int ll
using namespace std;
typedef long long ll;
const int MAXN = 1e6;
const ll MOD = 2305843009213693951;
int perm[MAXN];
int psorted[MAXN];
ll coeffs[MAXN];
int n, q;
map<int, int> compress;
map<ll, int> hsh_count; // values that are here - values that should be here
int decompress[MAXN];
int uf[MAXN];
int sz[MAXN];
ll hshs[MAXN];
ll ans4 = 0;
int find(int i) {
return (uf[i] == -1) ? i : (uf[i] = find(uf[i]));
}
int get(ll k) {
if (hsh_count.find(k) == hsh_count.end()) return 0;
return hsh_count[k];
}
void ins(int rt) {
ll hsh = hshs[rt];
if (hsh != 0) ans4 += (ll) sz[rt]*get(MOD-hsh);
hsh_count[hsh] += sz[rt];
}
void deins(int rt) {
ll hsh = hshs[rt];
hsh_count[hsh] -= sz[rt];
if (hsh_count[hsh] == 0) hsh_count.erase(hsh);
if (hsh != 0) ans4 -= (ll) sz[rt]*get(MOD-hsh);
}
bool good() {
return (hsh_count.size() == 1 && hsh_count.begin()->first == 0);
}
ll mult(ll a, ll b) {
unsigned __int128 r = a;
r *= b;
r %= MOD;
return (ll) r;
}
void merge(int a, int b) {
int ra = find(a);
int rb = find(b);
if (ra == rb) return;
deins(ra);
deins(rb);
uf[ra] = rb;
sz[rb] += sz[ra];
hshs[rb] = (hshs[rb]+hshs[ra]) % MOD;
ins(rb);
}
ll get_coeff(int i) {
return coeffs[compress[perm[i]]];
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> n >> q;
default_random_engine gen;
uniform_int_distribution<ll> dist(1, MOD-1);
for (int i = 0; i < n; i++) {
coeffs[i] = dist(gen)^dist(gen);
}
for (int i = 0; i < n; i++) {
int x; cin >> x;
perm[i] = x;
psorted[i] = x;
}
sort(psorted, psorted+n);
fill(uf, uf+n, -1);
fill(sz, sz+n, 1);
int t = 1;
compress[psorted[0]] = 0;
decompress[0] = psorted[0];
for (int i = 1; i < n; i++) {
if (psorted[i] == psorted[i-1]) continue;
compress[psorted[i]] = t;
decompress[t++] = psorted[i];
}
for (int i = 0; i < n; i++) {
hshs[i] = (get_coeff(i)+MOD-coeffs[compress[psorted[i]]]) % MOD;
ins(i);
}
for (int i = 0; i < q; i++) {
int a, b; cin >> t;
if (t == 1) {
cin >> a >> b; a--; b--;
int ra = find(a);
int rb = find(b);
if (ra == rb) {
swap(perm[a], perm[b]);
continue;
}
deins(ra);
deins(rb);
hshs[ra] += MOD-get_coeff(a);
hshs[rb] += MOD-get_coeff(b);
hshs[ra] %= MOD;
hshs[rb] %= MOD;
swap(perm[a], perm[b]);
hshs[ra] += get_coeff(a);
hshs[rb] += get_coeff(b);
hshs[ra] %= MOD;
hshs[rb] %= MOD;
ins(ra);
ins(rb);
}
if (t == 2) {
cin >> a >> b; a--; b--;
merge(a, b);
}
if (t == 3) {
if (good()) cout << "DA\n";
else cout << "NE\n";
}
if (t == 4) {
cout << ans4 << "\n";
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
852 KB |
Output is correct |
2 |
Correct |
6 ms |
852 KB |
Output is correct |
3 |
Correct |
7 ms |
928 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
68 ms |
5376 KB |
Output is correct |
2 |
Correct |
91 ms |
5832 KB |
Output is correct |
3 |
Correct |
160 ms |
6768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
905 ms |
28412 KB |
Output is correct |
2 |
Correct |
3792 ms |
50856 KB |
Output is correct |
3 |
Correct |
4302 ms |
68800 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1620 ms |
58876 KB |
Output is correct |
2 |
Correct |
3574 ms |
85832 KB |
Output is correct |
3 |
Correct |
1715 ms |
84960 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
904 ms |
52232 KB |
Output is correct |
2 |
Correct |
1880 ms |
59760 KB |
Output is correct |
3 |
Correct |
1717 ms |
85136 KB |
Output is correct |