#include <iostream>
#include <algorithm>
#include <cstring>
#include <iomanip>
#include <fstream>
#include <cmath>
#include <vector>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include <stack>
#include <queue>
#include <assert.h>
#include <limits>
#include <cstdio>
using namespace std;
//#define RDEBUG 1
#ifdef RDEBUG
#define D(x) x
#else
#define D(x)
#endif
#define inf 0x7fffffff
#define MOD 1000000007
typedef long long ll;
ll add(ll a, ll b) {
a += b;
if(a >= MOD) {
a -= MOD;
}
return a;
}
ll sub(ll a, ll b) {
a -= b;
if(a < 0) {
a += MOD;
}
return a;
}
ll mul(ll a, ll b) {
return (a * b)%MOD;
}
void add_self(ll& a, ll b) {
a = add(a, b);
}
void sub_self(ll& a, ll b) {
a = sub(a, b);
}
void mul_self(ll& a, ll b) {
a = mul(a, b);
}
const ll MAXN = 100;
ll P[MAXN], Q[MAXN];
ll N, M;
ll b = 31;
map<ll, ll> cc, m;
ll nodes = 0;
ll parent[MAXN];
ll nrank[MAXN];
ll hsp[MAXN];
ll hsq[MAXN];
ll ppow[MAXN];
ll sets = N;
ll sorted = 0;
ll ans = 0;
bool s = 0;
void updans(ll i, ll np, ll nq) {
ll op = hsp[i], oq = hsq[i];
if (s) {
ans-=(m[op-oq]*(m[op-oq]-1))/2;
ans-=(m[oq-op]*(m[oq-op]-1))/2;
m[op-oq]--;
m[oq-op]--;
}
ans-=(m[np-nq]*(m[np-nq]-1))/2;
ans-=(m[nq-np]*(m[nq-np]-1))/2;
m[np-nq]++;
m[nq-np]++;
if (s) {
ans+=(m[op-oq]*(m[op-oq]-1))/2;
ans+=(m[oq-op]*(m[oq-op]-1))/2;
}
ans+=(m[np-nq]*(m[np-nq]-1))/2;
ans+=(m[nq-np]*(m[nq-np]-1))/2;
}
void create_set(ll t, ll a) {
nodes++;
parent[nodes] = nodes;
nrank[nodes] = 0;
hsp[nodes] = ppow[t];
hsq[nodes] = ppow[a];
updans(nodes, ppow[t], ppow[a]);
}
ll find_set(ll x) {
if (parent[x] != x) {
parent[x] = find_set(parent[x]);
}
return parent[x];
}
void merge_sets(ll x, ll y) {
sets--;
ll PX = find_set(x), PY = find_set(y);
sorted-=((hsq[PX] == hsp[PX]) + (hsq[PY] == hsp[PY]));
if (nrank[PX] > nrank[PY]) {
parent[PY] = PX;
updans(PX, add(hsp[PX], hsp[PY]), add(hsq[PX], hsq[PY]));
add_self(hsp[PX], hsp[PY]);
add_self(hsq[PX], hsq[PY]);
sorted+=(hsq[PX] == hsp[PX]);
} else {
parent[PX] = PY;
updans(PY, add(hsp[PX], hsp[PY]), add(hsq[PX], hsq[PY]));
add_self(hsp[PY], hsp[PX]);
add_self(hsq[PY], hsq[PX]);
sorted+=(hsq[PY] == hsp[PY]);
}
if (nrank[PX] == nrank[PY]) {
nrank[PY]++;
}
}
int main() {
ios_base :: sync_with_stdio(false);
cin.tie(nullptr);
cin >> N >> M;
for (ll i = 1; i<=N; i++) {
cin >> P[i];
Q[i] = P[i];
}
sort(Q+1, Q+N+1);
ll val = 1;
ppow[1] = 1;
for (ll i = 2; i<=N; i++) {
ppow[i] = mul(ppow[i-1], b);
}
for (ll i = 1; i<=N; i++) {
if (cc.find(Q[i]) == cc.end()) {
cc[Q[i]] = val;
val++;
}
}
for (ll i = 1; i<=N; i++) {
Q[i] = cc[Q[i]];
P[i] = cc[P[i]];
}
for (ll i = 1; i<=N; i++) {
create_set(P[i], Q[i]);
sorted+=(P[i] == Q[i]);
sets++;
}
s = 1;
for (ll i = 0; i<M; i++) {
ll type;
cin >> type;
if (type == 1) {
ll A, B;
cin >> A >> B;
ll s1 = find_set(A), s2 = find_set(B);
updans(s1, add(hsp[s1], sub(ppow[P[B]], ppow[P[A]])), hsq[s1]);
updans(s2, add(hsp[s2], sub(ppow[P[A]], ppow[P[B]])), hsq[s2]);
sorted-=(hsq[s1] == hsp[s1]) + (hsq[s2] == hsp[s2]);
add_self(hsp[s1], sub(ppow[P[B]], ppow[P[A]]));
add_self(hsp[s2], sub(ppow[P[A]], ppow[P[B]]));
sorted+=(hsq[s1] == hsp[s1]) + (hsq[s2] == hsp[s2]);
} else if (type == 2) {
ll A, B;
cin >> A >> B;
ll s1 = find_set(A), s2 = find_set(B);
if (s1 != s2) {
merge_sets(s1, s2);
}
} else if (type == 3) {
cout << (sorted == sets ? "DA" : "NE") << "\n";
} else {
ll sub = ((m[0]-1)*m[0]);
cout << (ans-sub)/2 << "\n";
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
632 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
760 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
