#include <bits/stdc++.h>
#define FOR(i, u, v) for (int i = u; i <= v; i++)
#define FORD(i, v, u) for (int i = v; i >= u; i--)
#define ll long long
#define pill pair<int, ll>
#define PB push_back
#define mp make_pair
#define F first
#define S second
#define N 1000005
#define BASE 97
#define maxc 1000000007
#define mid (r + l)/2
using namespace std;
int n, numQ, a[N], b[N], sz[N], numCC, cc, root[N];
ll val[2][N], ansType4, base[N];
map<ll, int> ma;
template <typename T> inline void read(T &x){char c;bool nega=0;while((!isdigit(c=getchar()))&&(c!='-'));if(c=='-'){nega=1;c=getchar();}x=c-48;while(isdigit(c=getchar())) x=x*10+c-48;if(nega) x=-x;}
template <typename T> inline void writep(T x){if(x>9) writep(x/10);putchar(x%10+48);}
template <typename T> inline void write(T x){if(x<0){putchar('-');x=-x;}writep(x);putchar(' ');}
template <typename T> inline void writeln(T x){write(x);putchar('\n');}
void setup()
{
read(n); read(numQ); cc = n;
FOR(i, 1, n) read(a[i]), b[i] = a[i];
}
void subcc(int u)
{
ll Val = val[0][u] - val[1][u];
if (Val == 0)
{
numCC--;
return;
}
ansType4 -= 1ll*sz[u]*ma[-Val];
ma[Val] -= sz[u];
}
void addcc(int u)
{
ll Val = val[0][u] - val[1][u];
if (Val == 0)
{
numCC++;
return;
}
ansType4 += 1ll*sz[u]*ma[-Val];
ma[Val] += sz[u];
}
void prepare()
{
sort(b+1, b+n+1);
base[0] = 1;
FOR(i, 1, N-1) base[i] = base[i-1]*BASE;
FOR(i, 1, n)
{
sz[i] = 1;
val[0][i] = base[a[i]];
val[1][i] = base[b[i]];
addcc(i);
}
}
int get_root(int u)
{
return (root[u] == 0) ? u : root[u] = get_root(root[u]);
}
void inline add(ll &A, ll B) {A += B;}
void inline sub(ll &A, ll B) {A -= B;}
int main()
{
ios_base::sync_with_stdio(0); cout.tie(0);
//freopen("INP.TXT", "r", stdin);
//freopen("OUT.TXT", "w", stdout);
setup();
prepare();
while (numQ--)
{
int type, u, v; read(type);
if (type <= 2) read(u), read(v);
if (type == 1)
{
int p = get_root(u);
int q = get_root(v);
if (p == q)
{
swap(a[u], a[v]);
continue;
}
subcc(p); subcc(q);
add(val[0][p], base[a[v]]);
add(val[0][q], base[a[u]]);
sub(val[0][p], base[a[u]]);
sub(val[0][q], base[a[v]]);
swap(a[u], a[v]);
addcc(p); addcc(q);
}
else if (type == 2)
{
int p = get_root(u);
int q = get_root(v);
if (p == q) continue;
subcc(p); subcc(q);
root[q] = p; sz[p] += sz[q];
add(val[0][p], val[0][q]);
add(val[1][p], val[1][q]);
cc--;
addcc(p);
}
else if (type == 3)
{
if (cc == numCC) cout <<"DA\n";
else cout <<"NE\n";
}
else cout <<ansType4<<'\n';
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
8184 KB |
Output is correct |
2 |
Correct |
7 ms |
8184 KB |
Output is correct |
3 |
Correct |
7 ms |
8056 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
8188 KB |
Output is correct |
2 |
Correct |
8 ms |
8184 KB |
Output is correct |
3 |
Correct |
8 ms |
8056 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
8184 KB |
Output is correct |
2 |
Correct |
8 ms |
8316 KB |
Output is correct |
3 |
Correct |
9 ms |
8312 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
8184 KB |
Output is correct |
2 |
Correct |
8 ms |
8312 KB |
Output is correct |
3 |
Correct |
10 ms |
8336 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
8184 KB |
Output is correct |
2 |
Correct |
8 ms |
8312 KB |
Output is correct |
3 |
Correct |
9 ms |
8312 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
8696 KB |
Output is correct |
2 |
Correct |
12 ms |
8696 KB |
Output is correct |
3 |
Correct |
11 ms |
8824 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
63 ms |
11768 KB |
Output is correct |
2 |
Correct |
92 ms |
13652 KB |
Output is correct |
3 |
Correct |
151 ms |
16764 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1093 ms |
40276 KB |
Output is correct |
2 |
Correct |
5072 ms |
131080 KB |
Output is correct |
3 |
Correct |
5456 ms |
181804 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2109 ms |
81236 KB |
Output is correct |
2 |
Correct |
4091 ms |
102264 KB |
Output is correct |
3 |
Correct |
1529 ms |
89976 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
848 ms |
47044 KB |
Output is correct |
2 |
Correct |
3032 ms |
86264 KB |
Output is correct |
3 |
Correct |
1589 ms |
90100 KB |
Output is correct |