/*
DATE: 2020-03-13 10:51:02
NAME:
PROBLEM: COCI16_ZAMJENE
*/
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6;
const long long MOD = 1e16 + 3;
const int prime = 331;
long long add(long long x, long long y) {
return ((x % MOD) + (y % MOD)) % MOD;
}
long long sub(long long x, long long y) {
return ((x % MOD) + MOD - (y % MOD)) % MOD;
}
long long mul(long long x, long long y) {
return ((x % MOD) * (y % MOD)) % MOD;
}
long long liftt[MAXN + 7];
long long lift(int x) {
return liftt[x];
}
int p[MAXN + 7];
int q[MAXN + 7];
int par[MAXN + 7];
long long r[MAXN + 7];
long long P[MAXN + 7];
long long Q[MAXN + 7];
unordered_map<long long, long long> cnt;
long long ans_for_4 = 0;
void ins(int x, int y) {
// cerr << "ins: " << x << " " << y << " " << p[y] << "\n";
long long t = sub(P[x], Q[x]);
// cerr << t << "\t" << cnt[t] << "\t" << cnt[-t] << "\n";
if (t != 0) {
ans_for_4 -= r[x] * cnt[sub(0, t)];
}
cnt[t] -= r[x];
P[x] = add(P[x], lift(p[y]));
t = sub(P[x], Q[x]);
if (t != 0) {
ans_for_4 += r[x] * cnt[sub(0, t)];
}
cnt[t] += r[x];
// cerr << t << "\t" << cnt[t] << "\t" << cnt[-t] << "\n";
}
void del(int x, int y) {
long long t = sub(P[x], Q[x]);
if (t != 0) {
ans_for_4 -= r[x] * cnt[sub(0, t)];
}
cnt[t] -= r[x];
P[x] = sub(P[x], lift(p[y]));
t = sub(P[x], Q[x]);
if (t != 0) {
ans_for_4 += r[x] * cnt[sub(0, t)];
}
cnt[t] += r[x];
}
void makeset(int x) {
par[x] = x;
r[x] = 1;
Q[x] = lift(q[x]);
P[x] = 0;
cnt[sub(P[x], Q[x])] += r[x];
ins(x, x);
}
int findset(int x) {
if (par[x] != x) {
par[x] = findset(par[x]);
}
return par[x];
}
void link(int x, int y) {
x = findset(x);
y = findset(y);
if (x == y) {
return;
}
if (r[x] > r[y]) {
par[y] = x;
long long t = sub(P[x], Q[x]);
if (t != 0) {
ans_for_4 -= r[x] * cnt[sub(0, t)];
}
cnt[sub(P[x], Q[x])] -= r[x];
t = sub(P[y], Q[y]);
if (t != 0) {
ans_for_4 -= r[y] * cnt[sub(0, t)];
}
cnt[sub(P[y], Q[y])] -= r[y];
P[x] = add(P[x], P[y]);
Q[x] = add(Q[x], Q[y]);
r[x] += r[y];
t = sub(P[x], Q[x]);
if (t != 0) {
ans_for_4 += r[x] * cnt[sub(0, t)];
}
cnt[sub(P[x], Q[x])] += r[x];
}
else {
par[x] = y;
long long t = sub(P[x], Q[x]);
if (t != 0) {
ans_for_4 -= r[x] * cnt[sub(0, t)];
}
cnt[sub(P[x], Q[x])] -= r[x];
t = sub(P[y], Q[y]);
if (t != 0) {
ans_for_4 -= r[y] * cnt[sub(0, t)];
}
cnt[sub(P[y], Q[y])] -= r[y];
P[y] = add(P[y], P[x]);
Q[y] = add(Q[y], Q[x]);
r[y] += r[x];
t = sub(P[y], Q[y]);
if (t != 0) {
ans_for_4 += r[y] * cnt[sub(0, t)];
}
cnt[sub(P[y], Q[y])] += r[y];
}
}
int main() {
liftt[0] = 1;
for (int i = 1; i <= MAXN; i++) {
liftt[i] = mul(liftt[i - 1], prime);
}
int n, qry;
cin >> n >> qry;
for (int i = 1; i <= n; i++) {
scanf("%d", &p[i]);
q[i] = p[i];
}
sort(q + 1, q + n + 1);
for (int i = 1; i <= n; i++) {
makeset(i);
}
while (qry--) {
// for (unordered_map<long long, int>::iterator it = cnt.begin(); it != cnt.end(); it++) {
// cerr << it->first << " " << it->second << "\n";
// }
int ty;
scanf("%d", &ty);
if (ty == 1) {
int a, b;
scanf("%d %d", &a, &b);
int x = findset(a);
int y = findset(b);
if (x == y) {
continue;
}
del(x, a);
ins(x, b);
del(y, b);
ins(y, a);
swap(p[a], p[b]);
}
else if (ty == 2) {
int a, b;
scanf("%d %d", &a, &b);
link(a, b);
}
else if (ty == 3) {
if (cnt[0] == n) {
printf("DA\n");
}
else {
printf("NE\n");
}
}
else if (ty == 4) {
printf("%lld\n", ans_for_4);
}
}
return 0;
}
Compilation message
zamjene.cpp: In function 'int main()':
zamjene.cpp:165:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &p[i]);
~~~~~^~~~~~~~~~~~~
zamjene.cpp:180:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &ty);
~~~~~^~~~~~~~~~~
zamjene.cpp:183:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &a, &b);
~~~~~^~~~~~~~~~~~~~~~~
zamjene.cpp:198:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &a, &b);
~~~~~^~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
18 ms |
8180 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
18 ms |
8184 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
17 ms |
8184 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
17 ms |
8184 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
17 ms |
8184 KB |
Output is correct |
| 2 |
Correct |
17 ms |
8184 KB |
Output is correct |
| 3 |
Correct |
18 ms |
8312 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
23 ms |
8696 KB |
Output is correct |
| 2 |
Correct |
24 ms |
8696 KB |
Output is correct |
| 3 |
Correct |
24 ms |
8700 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
97 ms |
12152 KB |
Output is correct |
| 2 |
Correct |
108 ms |
13608 KB |
Output is correct |
| 3 |
Correct |
134 ms |
15880 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1070 ms |
42500 KB |
Output is correct |
| 2 |
Correct |
2254 ms |
128936 KB |
Output is correct |
| 3 |
Correct |
2532 ms |
145496 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1496 ms |
77712 KB |
Output is correct |
| 2 |
Correct |
1979 ms |
96468 KB |
Output is correct |
| 3 |
Correct |
1452 ms |
79880 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1077 ms |
50952 KB |
Output is correct |
| 2 |
Correct |
1568 ms |
81392 KB |
Output is correct |
| 3 |
Correct |
1501 ms |
80084 KB |
Output is correct |
