| 比赛 |
NOIP2025模拟赛4 |
评测结果 |
AAAAAAAAAAATTTTAAAAA |
| 题目名称 |
Swap Swap Sort |
最终得分 |
80 |
| 用户昵称 |
特朗普 |
运行时间 |
11.776 s |
| 代码语言 |
C++ |
内存使用 |
22.61 MiB |
| 提交时间 |
2025-11-27 08:44:53 |
显示代码纯文本
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
// ciallo
#include <bits/stdc++.h>
#define N 100005
#define B 1000
#define Poly vector <int>
#define pb push_back
#define ll long long
#define mt make_tuple
using namespace std;
int n, k, q, a[N], p[N], t[N];
Poly vec[N], num;
ll ans = 0;
vector < tuple <int, int, int> > f[N];
void update(int x, int v) {
for (; x; x -= x & -x) {
t[x] += v;
}
}
int query(int x) {
int ans = 0;
for (; x <= k; x += x & -x) {
ans += t[x];
}
return ans;
}
int pre(int c, int k) {
if (vec[c].empty()) return 0;
else if (vec[c].front() > k) return 0;
else if (vec[c].back() <= k) return vec[c].size();
else {
return upper_bound(vec[c].begin(), vec[c].end(), k) - vec[c].begin();
}
}
int suc(int c, int k) {
if (vec[c].empty()) return 0;
else if (vec[c].back() < k) return 0;
else if (vec[c].front() >= k) return vec[c].size();
else {
return vec[c].size() - (lower_bound(vec[c].begin(), vec[c].end(), k) - vec[c].begin());
}
}
int main() {
freopen("Sort.in" ,"r",stdin );
freopen("Sort.out","w",stdout);
ios :: sync_with_stdio(0), cin.tie(0);
cin >> n >> k >> q;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
vec[ a[i] ].pb(i);
ans += query(a[i] + 1);
update(a[i], 1);
}
iota(p + 1, p + n + 1, 1);
for (int i = 1; i <= k; ++i) {
if (vec[i].size() > B) num.pb(i);
}
for (int i = 1; i <= n; ++i) {
for (auto j : num) {
if (i != j) {
int sum1 = 0, sum2 = 0;
for (auto pos : vec[i]) {
sum1 += pre(j, pos);
sum2 += suc(j, pos);
}
f[i].pb(mt(j, sum1, sum2));
}
}
}
while (q--) {
int pos; cin >> pos;
int x = p[pos], y = p[ pos + 1 ];
if (vec[x].size() > B) {
for (auto i : f[y]) {
if (get <0> (i) == x) {
ans += get <1> (i);
ans -= get <2> (i);
break;
}
}
}
else if (vec[y].size() > B) {
for (auto i : f[x]) {
if (get <0> (i) == y) {
ans += get <2> (i);
ans -= get <1> (i);
}
}
}
else {
int len1 = vec[x].size(), len2 = vec[y].size();
int j = 0;
for (int i = 0; i < len1; ++i) {
while (j < len2 && vec[y][j] <= vec[x][i]) ++j;
ans -= j;
ans += len2 - j;
}
}
swap(p[pos], p[ pos + 1 ]);
cout << ans << "\n";
}
return 0;
}