#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;
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)
{
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=sqrt(N);
for(int i=1;i<=K;i++) if(cnt[i]>=M) big.push_back(i);
make_bb();
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:72:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | for(int i=0;i<v[b].size();i++)
| ~^~~~~~~~~~~~
Main.cpp:74: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]
74 | while(idx!=v[a].size() && v[a][idx]<v[b][i]) idx++;
| ~~~^~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
4948 KB |
Output is correct |
2 |
Correct |
4 ms |
5204 KB |
Output is correct |
3 |
Correct |
4 ms |
5204 KB |
Output is correct |
4 |
Correct |
7 ms |
6100 KB |
Output is correct |
5 |
Correct |
6 ms |
5148 KB |
Output is correct |
6 |
Correct |
4 ms |
5076 KB |
Output is correct |
7 |
Correct |
5 ms |
5204 KB |
Output is correct |
8 |
Correct |
5 ms |
5204 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
8308 KB |
Output is correct |
2 |
Correct |
15 ms |
9044 KB |
Output is correct |
3 |
Correct |
128 ms |
85864 KB |
Output is correct |
4 |
Correct |
15 ms |
6800 KB |
Output is correct |
5 |
Correct |
19 ms |
6996 KB |
Output is correct |
6 |
Correct |
18 ms |
7068 KB |
Output is correct |
7 |
Correct |
26 ms |
8084 KB |
Output is correct |
8 |
Correct |
26 ms |
9352 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
177 ms |
19324 KB |
Output is correct |
2 |
Correct |
172 ms |
20300 KB |
Output is correct |
3 |
Correct |
236 ms |
37348 KB |
Output is correct |
4 |
Correct |
377 ms |
96900 KB |
Output is correct |
5 |
Correct |
2625 ms |
17844 KB |
Output is correct |
6 |
Correct |
2183 ms |
17720 KB |
Output is correct |
7 |
Correct |
2142 ms |
17744 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
4948 KB |
Output is correct |
2 |
Correct |
4 ms |
5204 KB |
Output is correct |
3 |
Correct |
4 ms |
5204 KB |
Output is correct |
4 |
Correct |
7 ms |
6100 KB |
Output is correct |
5 |
Correct |
6 ms |
5148 KB |
Output is correct |
6 |
Correct |
4 ms |
5076 KB |
Output is correct |
7 |
Correct |
5 ms |
5204 KB |
Output is correct |
8 |
Correct |
5 ms |
5204 KB |
Output is correct |
9 |
Correct |
13 ms |
8308 KB |
Output is correct |
10 |
Correct |
15 ms |
9044 KB |
Output is correct |
11 |
Correct |
128 ms |
85864 KB |
Output is correct |
12 |
Correct |
15 ms |
6800 KB |
Output is correct |
13 |
Correct |
19 ms |
6996 KB |
Output is correct |
14 |
Correct |
18 ms |
7068 KB |
Output is correct |
15 |
Correct |
26 ms |
8084 KB |
Output is correct |
16 |
Correct |
26 ms |
9352 KB |
Output is correct |
17 |
Correct |
177 ms |
19324 KB |
Output is correct |
18 |
Correct |
172 ms |
20300 KB |
Output is correct |
19 |
Correct |
236 ms |
37348 KB |
Output is correct |
20 |
Correct |
377 ms |
96900 KB |
Output is correct |
21 |
Correct |
2625 ms |
17844 KB |
Output is correct |
22 |
Correct |
2183 ms |
17720 KB |
Output is correct |
23 |
Correct |
2142 ms |
17744 KB |
Output is correct |
24 |
Correct |
1180 ms |
21980 KB |
Output is correct |
25 |
Correct |
677 ms |
22688 KB |
Output is correct |
26 |
Correct |
393 ms |
23168 KB |
Output is correct |
27 |
Correct |
303 ms |
23348 KB |
Output is correct |
28 |
Correct |
283 ms |
24224 KB |
Output is correct |
29 |
Correct |
256 ms |
25396 KB |
Output is correct |
30 |
Correct |
331 ms |
26672 KB |
Output is correct |
31 |
Correct |
291 ms |
26612 KB |
Output is correct |
32 |
Correct |
242 ms |
35148 KB |
Output is correct |
33 |
Correct |
2602 ms |
21932 KB |
Output is correct |
34 |
Correct |
2135 ms |
21868 KB |
Output is correct |
35 |
Correct |
1813 ms |
22068 KB |
Output is correct |
36 |
Correct |
1170 ms |
22012 KB |
Output is correct |
37 |
Correct |
715 ms |
22804 KB |
Output is correct |
38 |
Correct |
529 ms |
22988 KB |
Output is correct |
39 |
Correct |
273 ms |
26568 KB |
Output is correct |
40 |
Correct |
289 ms |
32896 KB |
Output is correct |
41 |
Correct |
329 ms |
37492 KB |
Output is correct |
42 |
Correct |
302 ms |
42060 KB |
Output is correct |
43 |
Correct |
325 ms |
45968 KB |
Output is correct |
44 |
Correct |
316 ms |
56236 KB |
Output is correct |
45 |
Correct |
333 ms |
53692 KB |
Output is correct |
46 |
Correct |
373 ms |
26092 KB |
Output is correct |
47 |
Correct |
465 ms |
25772 KB |
Output is correct |
48 |
Correct |
899 ms |
25732 KB |
Output is correct |
49 |
Correct |
700 ms |
24784 KB |
Output is correct |
50 |
Correct |
255 ms |
34100 KB |
Output is correct |
51 |
Correct |
201 ms |
33308 KB |
Output is correct |
52 |
Correct |
199 ms |
33048 KB |
Output is correct |
53 |
Correct |
318 ms |
41748 KB |
Output is correct |
54 |
Correct |
323 ms |
41548 KB |
Output is correct |
55 |
Correct |
3 ms |
4948 KB |
Output is correct |