#include <bits/stdc++.h>
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fir first
#define sec second
#define pii pair<int, int>
typedef long long ll;
using namespace std;
const int mxN=100005;
ll N, M, K, Q;
int A[mxN];
ll cnt[mxN];
int B[mxN];
vector <int> v[mxN];
vector <int> big;
vector <ll> pref[mxN];
map <pii, ll> mp; ///mp[a, b] = a ... b 의 개수
ll ans;
void make_bb()
{
for(int i=0;i<big.size();i++)
{
for(int j=i+1;j<big.size();j++)
{
int n1=big[i], n2=big[j];
ll inv=0;
int idx=0;
for(int k=0;k<v[n2].size();k++)
{
while(idx!=v[n1].size() && v[n1][idx]<v[n2][k]) idx++;
inv+=idx;
}
mp[pii(n1, n2)]=inv;
mp[pii(n2, n1)]=cnt[n1]*cnt[n2]-inv;
}
}
}
void make_pref()
{
for(int now : big)
{
pref[now].resize(N+1);
pref[now][0]=0;
for(int i=1;i<=N;i++) pref[now][i]=pref[now][i-1]+(A[i]==now);
}
}
ll fen[mxN];
void upd(int now, int x){while(now<=N) fen[now]+=x, now+=(now&(-now));}
ll sum(int now)
{
int ret=0;
while(now) ret+=fen[now], now-=(now&(-now));
return ret;
}
ll solv(int s, int e){return sum(e)-sum(s-1);}
void init_inv()
{
for(int i=K;i>=1;i--)
{
for(int x : v[i]) ans+=sum(x);
for(int x : v[i]) upd(x, 1);
}
}
ll minv(int a, int b)
{
ll ret=0;
assert(cnt[b]<M);
for(int x : v[b]) ret+=pref[a][x];
return ret;
}
ll sinv(int a, int b)
{
ll ret=0, idx=0;
for(int i=0;i<v[b].size();i++)
{
while(idx!=v[a].size() && v[a][idx]<v[b][i]) idx++;
ret+=idx;
}
return ret;
}
ll inv(int a, int b)
{
return sinv(a, b);
if(cnt[a]<cnt[b]) return cnt[a]*cnt[b]-inv(b, a);
if(cnt[b]>=M) return mp[pii(a, b)];
if(cnt[a]>=M && cnt[b]<M) return minv(a, b);
else return sinv(a, b);
}
int main()
{
gibon
cin >> N >> K >> Q;
for(int i=1;i<=N;i++) cin >> A[i], v[A[i]].push_back(i), cnt[A[i]]++;
M=1;
while((M+1)*(M+1)<=N) M++;
for(int i=1;i<=K;i++) if(cnt[i]>=M) big.push_back(i);
assert(big.size()<=M+4);
make_bb();
assert(mp.size()<=M*M);
make_pref();
init_inv();
for(int i=1;i<=K;i++) B[i]=i;
while(Q--)
{
int a;
cin >> a;
ll ninv=inv(B[a+1], B[a]);
ans-=ninv;
ans+=cnt[B[a]]*cnt[B[a+1]]-ninv;
swap(B[a], B[a+1]);
cout << ans << '\n';
}
}
Compilation message
Main.cpp: In function 'void make_bb()':
Main.cpp:20:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
20 | for(int i=0;i<big.size();i++)
| ~^~~~~~~~~~~
Main.cpp:22:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
22 | for(int j=i+1;j<big.size();j++)
| ~^~~~~~~~~~~
Main.cpp:27:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
27 | for(int k=0;k<v[n2].size();k++)
| ~^~~~~~~~~~~~~
Main.cpp:29:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
29 | while(idx!=v[n1].size() && v[n1][idx]<v[n2][k]) idx++;
| ~~~^~~~~~~~~~~~~~
Main.cpp: In function 'll sinv(int, int)':
Main.cpp:73:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | for(int i=0;i<v[b].size();i++)
| ~^~~~~~~~~~~~
Main.cpp:75:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | while(idx!=v[a].size() && v[a][idx]<v[b][i]) idx++;
| ~~~^~~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from Main.cpp:1:
Main.cpp: In function 'int main()':
Main.cpp:96:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
96 | assert(big.size()<=M+4);
| ~~~~~~~~~~^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
84 ms |
5324 KB |
Output is correct |
| 3 |
Correct |
73 ms |
5260 KB |
Output is correct |
| 4 |
Correct |
17 ms |
6160 KB |
Output is correct |
| 5 |
Correct |
7 ms |
5080 KB |
Output is correct |
| 6 |
Correct |
4 ms |
5076 KB |
Output is correct |
| 7 |
Correct |
5 ms |
5204 KB |
Output is correct |
| 8 |
Correct |
4 ms |
5204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
66 ms |
8288 KB |
Output is correct |
| 2 |
Correct |
47 ms |
9012 KB |
Output is correct |
| 3 |
Correct |
125 ms |
85876 KB |
Output is correct |
| 4 |
Correct |
15 ms |
6764 KB |
Output is correct |
| 5 |
Correct |
17 ms |
6996 KB |
Output is correct |
| 6 |
Correct |
24 ms |
7104 KB |
Output is correct |
| 7 |
Correct |
25 ms |
8088 KB |
Output is correct |
| 8 |
Correct |
30 ms |
9352 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5039 ms |
8544 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
84 ms |
5324 KB |
Output is correct |
| 3 |
Correct |
73 ms |
5260 KB |
Output is correct |
| 4 |
Correct |
17 ms |
6160 KB |
Output is correct |
| 5 |
Correct |
7 ms |
5080 KB |
Output is correct |
| 6 |
Correct |
4 ms |
5076 KB |
Output is correct |
| 7 |
Correct |
5 ms |
5204 KB |
Output is correct |
| 8 |
Correct |
4 ms |
5204 KB |
Output is correct |
| 9 |
Correct |
66 ms |
8288 KB |
Output is correct |
| 10 |
Correct |
47 ms |
9012 KB |
Output is correct |
| 11 |
Correct |
125 ms |
85876 KB |
Output is correct |
| 12 |
Correct |
15 ms |
6764 KB |
Output is correct |
| 13 |
Correct |
17 ms |
6996 KB |
Output is correct |
| 14 |
Correct |
24 ms |
7104 KB |
Output is correct |
| 15 |
Correct |
25 ms |
8088 KB |
Output is correct |
| 16 |
Correct |
30 ms |
9352 KB |
Output is correct |
| 17 |
Execution timed out |
5039 ms |
8544 KB |
Time limit exceeded |
| 18 |
Halted |
0 ms |
0 KB |
- |
