이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000009
#define BASE 10016
int main()
{
size_t n, q;
cin >> n >> q;
vector<int64_t> y(n);
for (int64_t &x : y)
cin >> x;
vector<int64_t> z(y.begin(), y.end());
sort(z.begin(), z.end());
vector<int64_t> p(1000001);
p[0] = 1;
for (size_t i = 1; i < p.size(); i++)
p[i] = (p[i - 1] * BASE) % MOD;
vector<size_t> comp(n);
vector<set<size_t>> comp_set(n);
for (size_t i = 0; i < n; i++)
{
comp[i] = i;
comp_set[i] = {i};
}
vector<int64_t> h1(n), h2(n);
for (size_t i = 0; i < n; i++)
{
h1[i] = p[y[i]];
h2[i] = p[z[i]];
}
set<size_t> cant_sort;
for (size_t i = 0; i < n; i++)
if (h1[i] != h2[i])
cant_sort.insert(i);
map<int64_t, size_t> d;
size_t num_pairs = 0;
for (size_t i = 0; i < n; i++)
{
if (h1[i] != h2[i])
{
num_pairs += d[-(h1[i] - h2[i])];
d[h1[i] - h2[i]]++;
}
}
for (size_t i = 0; i < q; i++)
{
int t;
cin >> t;
switch (t)
{
case 1:
{
int64_t a, b;
cin >> a >> b;
a--, b--;
if (comp[a] == comp[b])
break;
if (h1[comp[a]] != h2[comp[a]])
{
num_pairs -= comp_set[comp[a]].size() * d[h2[comp[a]] - h1[comp[a]]];
d[h1[comp[a]] - h2[comp[a]]] -= comp_set[comp[a]].size();
}
if (h1[comp[b]] != h2[comp[b]])
{
num_pairs -= comp_set[comp[b]].size() * d[h2[comp[b]] - h1[comp[b]]];
d[h1[comp[b]] - h2[comp[b]]] -= comp_set[comp[b]].size();
}
h1[comp[a]] = (h1[comp[a]] - p[y[a]] + p[y[b]] + MOD) % MOD;
h1[comp[b]] = (h1[comp[b]] - p[y[b]] + p[y[a]] + MOD) % MOD;
if (h1[comp[a]] != h2[comp[a]])
{
num_pairs += comp_set[comp[a]].size() * d[h2[comp[a]] - h1[comp[a]]];
d[h1[comp[a]] - h2[comp[a]]] += comp_set[comp[a]].size();
}
if (h1[comp[b]] != h2[comp[b]])
{
num_pairs += comp_set[comp[b]].size() * d[h2[comp[b]] - h1[comp[b]]];
d[h1[comp[b]] - h2[comp[b]]] += comp_set[comp[b]].size();
}
cant_sort.erase(comp[a]);
cant_sort.erase(comp[b]);
if (h1[comp[a]] != h2[comp[a]])
cant_sort.insert(comp[a]);
if (h1[comp[b]] != h2[comp[b]])
cant_sort.insert(comp[b]);
swap(y[a], y[b]);
break;
}
case 2:
{
int64_t a, b;
cin >> a >> b;
a--, b--;
if (comp[a] == comp[b])
break;
if (h1[comp[a]] != h2[comp[a]])
{
num_pairs -= comp_set[comp[a]].size() * d[h2[comp[a]] - h1[comp[a]]];
d[h1[comp[a]] - h2[comp[a]]] -= comp_set[comp[a]].size();
}
if (h1[comp[b]] != h2[comp[b]])
{
num_pairs -= comp_set[comp[b]].size() * d[h2[comp[b]] - h1[comp[b]]];
d[h1[comp[b]] - h2[comp[b]]] -= comp_set[comp[b]].size();
}
if (comp_set[comp[a]].size() < comp_set[comp[b]].size())
swap(a, b);
comp_set[comp[a]].insert(comp_set[comp[b]].begin(), comp_set[comp[b]].end());
size_t const c = comp[b];
for (size_t const &j : comp_set[c])
comp[j] = comp[a];
comp_set[c].clear();
h1[comp[a]] = (h1[comp[a]] + h1[c]) % MOD;
h2[comp[a]] = (h2[comp[a]] + h2[c]) % MOD;
if (h1[comp[a]] != h2[comp[a]])
{
num_pairs += comp_set[comp[a]].size() * d[h2[comp[a]] - h1[comp[a]]];
d[h1[comp[a]] - h2[comp[a]]] += comp_set[comp[a]].size();
}
cant_sort.erase(comp[a]);
cant_sort.erase(c);
if (h1[comp[a]] != h2[comp[a]])
cant_sort.insert(comp[a]);
break;
}
case 3:
{
cout << (cant_sort.empty() ? "DA" : "NE") << '\n';
break;
}
case 4:
{
cout << num_pairs << '\n';
break;
}
}
}
}
# | 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... |