#include <iostream>
#include <vector>
#include <string>
#include <fstream>
#include <algorithm>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <bitset>
#include <deque>
#include <queue>
#include <tuple>
#include <cmath>
#include <cctype>
#include <stack>
#include <cassert>
#include <iomanip>
#include <random>
#include <chrono>
using namespace std;
using ll = long long;
ll P = (1LL<<61LL) - 1LL;
int N, Q;
ll p[1000001], goal[1000001];
ll ph[1000001];
ll ah[1000001], gh[1000001];
unordered_map<ll, ll> hcnt;
ll par[1000001], cnt[1000001];
ll pres = 0;
ll badSets = 0;
void gen_hash() {
unsigned seed = chrono::system_clock::now().time_since_epoch().count();
mt19937_64 mt(seed);
for (int i = 1; i <= N; i++) ph[i] = mt() % P;
}
int get(int x) {
return x==par[x] ? x : par[x] = get(par[x]);
}
void unite(int a, int b) {
assert(a == get(a) && b == get(b) && a != b);
if (cnt[a] < cnt[b]) swap(a, b);
if (ah[a] != gh[a]) {
badSets--;
hcnt[(ah[a] - gh[a]+P)%P] -= cnt[a];
pres -= cnt[a]*hcnt[(gh[a] - ah[a]+P)%P];
}
if (ah[b] != gh[b]) {
badSets--;
hcnt[(ah[b] - gh[b]+P)%P] -= cnt[b];
pres -= cnt[b]*hcnt[(gh[b] - ah[b]+P)%P];
}
par[b] = a;
cnt[a] += cnt[b], cnt[b] = 0;
ah[a] = (ah[a] + ah[b]) % P;
gh[a] = (gh[a] + gh[b]) % P;
if (ah[a] != gh[a]) {
badSets++;
hcnt[(ah[a] - gh[a]+P)%P] += cnt[a];
pres += cnt[a]*hcnt[(gh[a] - ah[a]+P)%P];
}
}
int main() {
cin >> N >> Q;
for (int i = 1; i <= N; i++) {
cin >> p[i]; goal[i] = p[i];
}
sort(goal+1, goal+1+N);
gen_hash();
for (int i = 1; i <= N; i++) {
par[i] = i, cnt[i] = 1;
ah[i] = ph[p[i]], gh[i] = ph[goal[i]];
if (ah[i] != gh[i]) {
badSets++;
hcnt[(ah[i] - gh[i] + P)%P] += cnt[i];
pres += cnt[i]*hcnt[(gh[i]-ah[i]+P)%P];
}
}
for (int q = 1; q <= Q; q++) {
int t; cin >> t;
if (t == 1) {
int A, B; cin >> A >> B;
ll av = p[A], bv = p[B];
swap(p[A], p[B]);
A = get(A); B = get(B);
if (A == B) continue; // shouldn't change the outcome of the program but useful to eliminate redundancy
// remove from answers to 3 and 4
if (ah[A] != gh[A]) {
badSets--;
hcnt[(ah[A] - gh[A]+P)%P] -= cnt[A];
pres -= cnt[A]*hcnt[(gh[A] - ah[A]+P)%P];
}
if (ah[B] != gh[B]) {
badSets--;
hcnt[(ah[B] - gh[B]+P)%P] -= cnt[B];
pres -= cnt[B]*hcnt[(gh[B] - ah[B]+P)%P];
}
// adjust data structure
ah[A] = (ah[A] - ph[av] + ph[bv]) % P;
if (ah[A] < 0) ah[A] += P;
ah[B] = (ah[B] - ph[bv] + ph[av]) % P;
if (ah[B] < 0) ah[B] += P;
// add back to answers to 3 and 4
if (ah[A] != gh[A]) {
badSets++;
hcnt[(ah[A] - gh[A]+P)%P] += cnt[A];
pres += cnt[A]*hcnt[(gh[A] - ah[A]+P)%P];
}
if (ah[B] != gh[B]) {
badSets++;
hcnt[(ah[B] - gh[B]+P)%P] += cnt[B];
pres += cnt[B]*hcnt[(gh[B] - ah[B]+P)%P];
}
} else if (t == 2) { // combine dsu's with A and B
int A, B; cin >> A >> B;
A = get(A); B = get(B);
if (A == B) continue;
unite(A, B);
} else if (t == 3) {
cout << (badSets==0 ? "DA" : "NE") << endl;
} else if (t == 4) {
cout << pres << endl;
}
// cout << "after applying query " << q << ": " << endl;
// cout << "par, cnt: " << endl;
// for (int i = 1; i <= N; i++) cout << par[i] << " "; cout << endl;
// for (int i = 1; i <= N; i++) cout << cnt[i] << " "; cout << endl;
// for (int i = 1; i <= N; i++) cout << ah[i] << " "; cout << endl;
// for (int i = 1; i <= N; i++) cout << gh[i] << " "; cout << endl;
// cout << "badsets, pres: " << badSets << " " << pres << endl;
// for (auto pp : hcnt) cout << pp.first << " " << pp.second << endl;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
340 KB |
Output is correct |
| 2 |
Correct |
2 ms |
340 KB |
Output is correct |
| 3 |
Correct |
2 ms |
316 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
324 KB |
Output is correct |
| 2 |
Correct |
2 ms |
340 KB |
Output is correct |
| 3 |
Correct |
3 ms |
456 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
340 KB |
Output is correct |
| 2 |
Correct |
2 ms |
340 KB |
Output is correct |
| 3 |
Correct |
2 ms |
320 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
340 KB |
Output is correct |
| 2 |
Correct |
3 ms |
340 KB |
Output is correct |
| 3 |
Correct |
3 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
340 KB |
Output is correct |
| 2 |
Correct |
2 ms |
320 KB |
Output is correct |
| 3 |
Correct |
2 ms |
468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
980 KB |
Output is correct |
| 2 |
Correct |
15 ms |
1108 KB |
Output is correct |
| 3 |
Correct |
15 ms |
1020 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
173 ms |
7268 KB |
Output is correct |
| 2 |
Correct |
188 ms |
8528 KB |
Output is correct |
| 3 |
Correct |
192 ms |
10328 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1586 ms |
49808 KB |
Output is correct |
| 2 |
Correct |
2422 ms |
118304 KB |
Output is correct |
| 3 |
Correct |
2543 ms |
141496 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1884 ms |
94568 KB |
Output is correct |
| 2 |
Correct |
2305 ms |
111488 KB |
Output is correct |
| 3 |
Correct |
1792 ms |
109724 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1651 ms |
72060 KB |
Output is correct |
| 2 |
Correct |
2065 ms |
97016 KB |
Output is correct |
| 3 |
Correct |
1822 ms |
109624 KB |
Output is correct |
