#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
const ll mx = 1e6+5, p = 2183581;
int n, q; int vals[mx], sorted[mx];
int par[mx], sz[mx]; ll pPow[mx], cnP[mx], cnQ[mx];
gp_hash_table<ll, ll> diff; ll cnt;
int find(int node) { return (node == par[node]) ? node : par[node] = find(par[node]); }
void upd(int i, int change){
change *= sz[i];
if (cnP[i] != cnQ[i]) cnt += diff[cnQ[i]-cnP[i]]*change;
diff[cnP[i]-cnQ[i]] += change;
}
void merge(int a, int b){
a = find(a); b = find(b);
if (a == b) return;
if (sz[a] > sz[b]) swap(a, b);
upd(a, -1); upd(b, -1);
par[a] = b; sz[b] += sz[a]; cnP[b] += cnP[a]; cnQ[b] += cnQ[a];
upd(b, 1);
}
void Swap(int a, int b){
int parA = find(a), parB = find(b);
upd(parA, -1); upd(parB, -1);
cnP[parA] = (cnP[parA]-pPow[vals[a]]+pPow[vals[b]]);
cnP[parB] = (cnP[parB]-pPow[vals[b]]+pPow[vals[a]]);
upd(parA, 1); upd(parB, 1);
swap(vals[a], vals[b]);
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> q; pPow[0] = 1;
for (int i = 0; i < n; i++){
cin >> vals[i]; sorted[i] = vals[i];
pPow[i+1] = (pPow[i]*p);
}
sort(sorted, sorted+n); iota(par, par+n, 0); fill(sz, sz+n, 1);
for (int i = 0; i < n; i++){
cnP[i] = pPow[vals[i]], cnQ[i] = pPow[sorted[i]];
diff[cnP[i]-cnQ[i]]++;
}
map<int, bool> visited;
for (int i = 0; i < n; i++){
if (cnP[i] != cnQ[i] and !visited[cnP[i]-cnQ[i]]){
cnt += diff[cnP[i]-cnQ[i]]*diff[cnQ[i]-cnP[i]];
visited[cnP[i]-cnQ[i]] = true; visited[cnQ[i]-cnP[i]] = true;
}
}
for (int i = 0; i < q; i++){
int t, a, b; cin >> t; if (t <= 2) { cin >> a >> b; a--; b--; }
if (t == 1) Swap(a, b);
if (t == 2) merge(a, b);
if (t == 3) cout<<((diff[0] == n) ? "DA":"NE")<<endl;
if (t == 4) cout<<cnt<<endl;
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
332 KB |
Output is correct |
2 |
Correct |
2 ms |
332 KB |
Output is correct |
3 |
Correct |
2 ms |
332 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
2 ms |
332 KB |
Output is correct |
3 |
Correct |
2 ms |
332 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
332 KB |
Output is correct |
2 |
Correct |
2 ms |
460 KB |
Output is correct |
3 |
Correct |
2 ms |
460 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
332 KB |
Output is correct |
2 |
Correct |
2 ms |
460 KB |
Output is correct |
3 |
Correct |
2 ms |
460 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
332 KB |
Output is correct |
2 |
Correct |
2 ms |
460 KB |
Output is correct |
3 |
Correct |
3 ms |
588 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
956 KB |
Output is correct |
2 |
Correct |
13 ms |
888 KB |
Output is correct |
3 |
Correct |
15 ms |
1128 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
129 ms |
4860 KB |
Output is correct |
2 |
Correct |
141 ms |
6984 KB |
Output is correct |
3 |
Correct |
180 ms |
14376 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1504 ms |
41856 KB |
Output is correct |
2 |
Incorrect |
2726 ms |
200064 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1775 ms |
116848 KB |
Output is correct |
2 |
Correct |
2371 ms |
126540 KB |
Output is correct |
3 |
Correct |
1683 ms |
115676 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1574 ms |
47872 KB |
Output is correct |
2 |
Correct |
1886 ms |
116848 KB |
Output is correct |
3 |
Correct |
1731 ms |
115836 KB |
Output is correct |