This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define PB push_back
#define ft first
#define sd second
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define i2 array<int,2>
using namespace std;
using namespace __gnu_pbds;
typedef unsigned long long ull;
typedef long long ll;
const int N = 1000100;
const int BIG = 1000100;
const int oo = 2e9;
gp_hash_table<ull, int> mem;
ull val[BIG], sum[N];
int a[N], pr[N], siz[N], n, q, srt[N];
ll ans = 0;
//mt19937_64 rnd(chrono::system_clock().now().time_since_epoch().count());
mt19937_64 rnd(413);
int get(int x) { return (pr[x] == x ? x : pr[x] = get(pr[x])); }
void delt(int xx){
if (sum[xx] == 0) return;
ull inv = ull(0) - sum[xx];
if (mem.find(inv) != mem.end())
ans -= 2 * mem[inv] * ll(siz[xx]);
}
void decv(int xx){
if (sum[xx] == 0) return;
mem[sum[xx]] -= siz[xx];
if (mem[sum[xx]] == 0)
mem.erase(sum[xx]);
}
void add(int xx){
if (sum[xx] == 0) return;
ull inv = ull(0) - sum[xx];
if (mem.find(inv) != mem.end())
ans += 2 * mem[inv] * ll(siz[xx]);
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef _LOCAL
freopen("in.txt","r",stdin);
#endif // _LOCAL
cin >> n >> q;
for (int i = 1; i < BIG; i++)
val[i] = rnd();
for (int i = 0; i < n; i++) {
cin >> a[i];
srt[i] = a[i];
pr[i] = i;
siz[i] = 1;
}
sort(srt, srt + n);
for (int i = 0; i < n; i++)
if (a[i] != srt[i]) {
sum[i] = val[a[i]] - val[srt[i]];
mem[sum[i]]++;
}
//cerr << sz(mem) << '\n';
for (int i = 0; i < n; i++)
if (a[i] != srt[i]) {
ull cur = -val[a[i]] + val[srt[i]];
if (mem.find(cur) != mem.end())
ans++;
}
for (int i = 0; i < n; i++)
for (; q; q--){
int tp; cin >> tp;
// //cerr << sz(mem) << '\n';
if (tp == 1){
int x, y; cin >> x >> y;
x--; y--;
swap(a[x], a[y]);
int xx = get(x), yy = get(y);
if (xx == yy) continue;
delt(xx);
delt(yy);
decv(xx);
decv(yy);
if (sum[xx] != ull(0) && sum[xx] + sum[yy] == ull(0))
ans += 2 * ll(siz[xx]) * ll(siz[yy]);
sum[xx] -= val[a[y]] - val[a[x]];
sum[yy] += val[a[y]] - val[a[x]];
if (sum[yy] > 0) mem[sum[yy]] += siz[yy];
if (sum[xx] > 0) mem[sum[xx]] += siz[xx];
add(yy);
add(xx);
if (sum[xx] != ull(0) && sum[xx] + sum[yy] == ull(0))
ans -= 2 * ll(siz[xx]) * ll(siz[yy]);
} else if (tp == 2){
int x, y; cin >> x >> y;
x--; y--;
int xx = get(x), yy = get(y);
if (xx == yy) continue;
delt(xx);
delt(yy);
decv(xx);
decv(yy);
if (sum[xx] != ull(0) && sum[xx] + sum[yy] == ull(0))
ans += 2 * ll(siz[xx]) * ll(siz[yy]);
pr[xx] = yy;
siz[yy] += siz[xx];
sum[yy] += sum[xx];
if (sum[yy] > 0) mem[sum[yy]] += siz[yy];
add(yy);
} else if (tp == 3){
cout << (sz(mem) == 0 ? "DA\n" : "NE\n");
} else { //4
if (ans % 2 == 1){
while (1) {}
}
// assert(ans % 2 == 0);
cout << ans / 2 << '\n';
}
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |