#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
const int64_t BASE = 1234577;
const int64_t MAX_N = 1e6;
const int64_t MAX_P = 1e6;
int64_t p[MAX_N + 5], q[MAX_N + 5];
int64_t basePowers[MAX_P + 5];
__gnu_pbds::gp_hash_table< int64_t, int64_t > totalWithDiff;
int64_t totalPairs;
void Add(int64_t diff, int64_t cnt) {
if(diff != 0) {
totalPairs += (int64_t) cnt * totalWithDiff[-diff];
}
totalWithDiff[diff] += cnt;
}
void Remove(int64_t diff, int64_t cnt) {
if(diff != 0) {
totalPairs -= (int64_t) cnt * totalWithDiff[-diff];
}
totalWithDiff[diff] -= cnt;
}
class UnionFind {
private:
int64_t parents[MAX_N + 5], sizes[MAX_N + 5], sumsP[MAX_N + 5], sumsQ[MAX_N + 5];
public:
void Init(int64_t pCntNodes) {
for(int64_t i = 1; i <= pCntNodes; i++) {
sumsP[i] = basePowers[p[i] - 1];
sumsQ[i] = basePowers[q[i] - 1];
parents[i] = i;
sizes[i] = 1;
int64_t diff = sumsP[i] - sumsQ[i];
Add(diff, 1);
}
}
int64_t Find(int64_t x) {
if(x == parents[x]) {
return x;
}
else {
parents[x] = Find(parents[x]);
return parents[x];
}
}
void Swap(int64_t x, int64_t y) {
int64_t parX = Find(x);
int64_t parY = Find(y);
if(parX == parY) {
std::swap(p[x], p[y]);
return;
}
int64_t diffX = sumsP[parX] - sumsQ[parX];
Remove(diffX, sizes[parX]);
int64_t diffY = sumsP[parY] - sumsQ[parY];
Remove(diffY, sizes[parY]);
sumsP[parX] -= basePowers[p[x] - 1];
sumsP[parX] = sumsP[parX] + basePowers[p[y] - 1];
sumsP[parY] -= basePowers[p[y] - 1];
sumsP[parY] = sumsP[parY] + basePowers[p[x] - 1];
std::swap(p[x], p[y]);
diffX = sumsP[parX] - sumsQ[parX];
Add(diffX, sizes[parX]);
diffY = sumsP[parY] - sumsQ[parY];
Add(diffY, sizes[parY]);
}
void Union(int64_t x, int64_t y) {
int64_t parX = Find(x);
int64_t parY = Find(y);
if(parX == parY) {
return;
}
int64_t diffX = sumsP[parX] - sumsQ[parX];
Remove(diffX, sizes[parX]);
int64_t diffY = sumsP[parY] - sumsQ[parY];
Remove(diffY, sizes[parY]);
if(sizes[parX] <= sizes[parY]) {
parents[parX] = parY;
sizes[parY] += sizes[parX];
sumsP[parY] = sumsP[parY] + sumsP[parX];
sumsQ[parY] = sumsQ[parY] + sumsQ[parX];
diffY = sumsP[parY] - sumsQ[parY];
Add(diffY, sizes[parY]);
}
else {
parents[parY] = parX;
sizes[parX] += sizes[parY];
sumsP[parX] = sumsP[parX] + sumsP[parY];
sumsQ[parX] = sumsQ[parX] + sumsQ[parY];
diffX = sumsP[parX] - sumsQ[parX];
Add(diffX, sizes[parX]);
}
}
};
UnionFind dsu;
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int64_t n, m;
std::cin >> n >> m;
for(int64_t i = 1; i <= n; i++) {
std::cin >> p[i];
q[i] = p[i];
}
std::sort(q + 1, q + 1 + n);
basePowers[0] = 1;
for(int64_t i = 1; i < q[n]; i++) {
basePowers[i] = basePowers[i - 1] * BASE;
}
dsu.Init(n);
for(int64_t i = 0; i < m; i++) {
int64_t t;
std::cin >> t;
if(t == 1) {
int64_t a, b;
std::cin >> a >> b;
dsu.Swap(a, b);
}
else if(t == 2) {
int64_t a, b;
std::cin >> a >> b;
dsu.Union(a, b);
}
else if(t == 3) {
std::cout << (totalWithDiff[0] == n ? "DA" : "NE") << '\n';
}
else {
std::cout << totalPairs << '\n';
}
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
3 ms |
376 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
380 KB |
Output is correct |
2 |
Correct |
3 ms |
504 KB |
Output is correct |
3 |
Correct |
3 ms |
504 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
504 KB |
Output is correct |
2 |
Correct |
2 ms |
504 KB |
Output is correct |
3 |
Correct |
3 ms |
632 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
504 KB |
Output is correct |
2 |
Correct |
2 ms |
504 KB |
Output is correct |
3 |
Correct |
3 ms |
632 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
1144 KB |
Output is correct |
2 |
Correct |
6 ms |
1016 KB |
Output is correct |
3 |
Correct |
7 ms |
1272 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
51 ms |
5684 KB |
Output is correct |
2 |
Correct |
57 ms |
7792 KB |
Output is correct |
3 |
Correct |
81 ms |
14680 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
670 ms |
45904 KB |
Output is correct |
2 |
Correct |
1223 ms |
174100 KB |
Output is correct |
3 |
Correct |
1548 ms |
321484 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1004 ms |
124540 KB |
Output is correct |
2 |
Correct |
1190 ms |
124068 KB |
Output is correct |
3 |
Correct |
1002 ms |
123768 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
758 ms |
55448 KB |
Output is correct |
2 |
Correct |
1028 ms |
124252 KB |
Output is correct |
3 |
Correct |
947 ms |
123600 KB |
Output is correct |