<div id="readability-page-1" class="page"><div id="main">
 
 

 

 
 
 

 <article itemscope="" itemtype="http://schema.org/Article">
 

 

 

 
 <header>

 
 
 
 

 
 </header>
 

 <div itemprop="articleBody">
 
 
 
 

 
 
 
 












 <h3 id="문제-링크">문제 링크</h3>
<ul>
 <li>http://icpc.me/21823</li>
</ul>

<h3 id="문제-출처">문제 출처</h3>
<ul>
 <li>2021 CCO Day1 1번</li>
</ul>

<h3 id="사용-알고리즘">사용 알고리즘</h3>
<ul>
 <li>Regions Trick</li>
</ul>

<h3 id="시간복잡도">시간복잡도</h3>
<ul>
 <li>$O((N+K)\sqrt N \log N)$</li>
</ul>

<h3 id="풀이">풀이</h3>
어떤 수열 $A$와 target permutation $P$가 주어졌을 때, $i &lt; j$이면서 $P$에서 $A[i]$가 $A[j]$보다 뒤에 있는 순서쌍 $(i, j)$의 개수를 구하는 문제입니다. 
$P = \left{ 1, 2, \cdots, N \right}$인 초기 상태에서의 순서쌍의 개수는 단순한 inversion counting 문제입니다. $P$에서 인접한 두 수 $P[t]$와 $P[t+1]$의 위치를 교환할 때 inversion 개수의 변화를 살펴봅시다.

편의상 $u = P[t], v = P[t+1]$이라고 하겠습니다. $A[i] = u, A[j] = v$인 모든 순서쌍 $(i, j)$에 대해, $i &lt; j$였다면 inversion의 개수가 1 증가하고, 반대로 $i &gt; j$였다면 1 감소합니다. 따라서 $A[i] = u$인 모든 $i$를 보면서, 자신보다 앞에 있는 $v$의 개수와 뒤에 있는 $v$의 개수를 구하면 문제를 해결할 수 있습니다. 
각 수가 등장하는 위치를 알고 있다면 $A[i] = u$인 모든 $i$를 순회하면서 $v$가 등장하는 위치에 대해 이분 탐색을 수행해서 원하는 값을 구할 수 있습니다. 따라서 각 쿼리의 시간 복잡도는 $O(\min(S[u], S[v]) \log \max(S[u], S[v]))$입니다.

이 방법을 그대로 적용하면 전체 시간 복잡도가 $O(KN \log N)$이지만, 쿼리의 결과를 저장해서 중복 계산을 방지하면(IOI’09 Regions Trick) $O((N+K)\sqrt N \log N)$에 문제를 해결할 수 있습니다.

<h3 id="전체-코드">전체 코드</h3>
<div><table><tbody><tr><td><pre>1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42</pre></td><td><pre><code>#include &lt;bits/stdc++.h&gt;
using namespace std;
using ll = long long;

int N, K, Q, A[101010], B[101010], T[101010];
vector&lt;int&gt; P[101010]; ll R;
void Add(int x, int v){ for(x+=3; x&lt;101010; x+=x&amp;-x) T[x] += v; }
int Get(int x){ int ret = 0; for(x+=3; x; x-=x&amp;-x) ret += T[x]; return ret; }

map&lt;pair&lt;int,int&gt;, ll&gt; Cache;
ll Swap(int u, int v){
 auto it = Cache.lower_bound(make_pair(u, v));
 if(it != Cache.end() &amp;&amp; it-&gt;first == make_pair(u, v)) return it-&gt;second;

 ll res = 0;
 if(P[u].size() &lt; P[v].size()){
 for(auto i : P[u]){
 int cnt = P[v].end() - lower_bound(P[v].begin(), P[v].end(), i);
 res += cnt - ((int)P[v].size() - cnt);
 }
 }
 else{
 for(auto i : P[v]){
 int cnt = lower_bound(P[u].begin(), P[u].end(), i) - P[u].begin();
 res += cnt - ((int)P[u].size() - cnt);
 }
 }
 Cache.emplace_hint(it, make_pair(u, v), res);
 return res;
}

int main(){
 ios_base::sync_with_stdio(false); cin.tie(nullptr);
 cin &gt;&gt; N &gt;&gt; K &gt;&gt; Q; iota(B+1, B+K+1, 1);
 for(int i=1; i&lt;=N; i++) cin &gt;&gt; A[i], P[A[i]].push_back(i);
 for(int i=N; i&gt;=1; i--) R += Get(A[i]-1), Add(A[i], 1);
 for(int q=1; q&lt;=Q; q++){
 int t; cin &gt;&gt; t;
 R += Swap(B[t], B[t+1]); swap(B[t], B[t+1]);
 cout &lt;&lt; R &lt;&lt; "\n";
 }
}
</code></pre></td></tr></tbody></table></div>


 
 </div>

 

 

 

 
 </article>

 
</div></div>

JusticeHui가 PS하는 블로그

문제 링크
http://icpc.me/21823
문제 출처
2021 CCO Day1 1번
사용 알고리즘
Regions Trick
시간복잡도
$O((N+K)\sqrt N \log N)$
풀이
어떤 수열 $A$와 target permutation $P$가 주어졌을 때, $i < j$이면서 $P$에서 $A[i]$가 $A[j]$보다 뒤에 있는 순서쌍 $(i, j)$의 개수를 구하는 문제입니다.
편의상 $u = P[t], v = P[t+1]$이라고 하겠습니다. $A[i] = u, A[j] = v$인 모든 순서쌍 $(i, j)$에 대해, $i < j$였다면 inversion의 개수가 1 증가하고, 반대로 $i > j$였다면 1 감소합니다. 따라서 $A[i] = u$인 모든 $i$를 보면서, 자신보다 앞에 있는 $v$의 개수와 뒤에 있는 $v$의 개수를 구하면 문제를 해결할 수 있습니다.
이 방법을 그대로 적용하면 전체 시간 복잡도가 $O(KN \log N)$이지만, 쿼리의 결과를 저장해서 중복 계산을 방지하면(IOI’09 Regions Trick) $O((N+K)\sqrt N \log N)$에 문제를 해결할 수 있습니다.
전체 코드
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int N, K, Q, A[101010], B[101010], T[101010];
vector<int> P[101010]; ll R;
void Add(int x, int v){ for(x+=3; x<101010; x+=x&-x) T[x] += v; }
int Get(int x){ int ret = 0; for(x+=3; x; x-=x&-x) ret += T[x]; return ret; }
map<pair<int,int>, ll> Cache;
ll Swap(int u, int v){
 auto it = Cache.lower_bound(make_pair(u, v));
 if(it != Cache.end() && it->first == make_pair(u, v)) return it->second;
 ll res = 0;
 if(P[u].size() < P[v].size()){
 for(auto i : P[u]){
 int cnt = P[v].end() - lower_bound(P[v].begin(), P[v].end(), i);
 res += cnt - ((int)P[v].size() - cnt);
 }
 }
 else{
 for(auto i : P[v]){
 int cnt = lower_bound(P[u].begin(), P[u].end(), i) - P[u].begin();
 res += cnt - ((int)P[u].size() - cnt);
 }
 }
 Cache.emplace_hint(it, make_pair(u, v), res);
 return res;
}
int main(){
 ios_base::sync_with_stdio(false); cin.tie(nullptr);
 cin >> N >> K >> Q; iota(B+1, B+K+1, 1);
 for(int i=1; i<=N; i++) cin >> A[i], P[A[i]].push_back(i);
 for(int i=N; i>=1; i--) R += Get(A[i]-1), Add(A[i], 1);
 for(int q=1; q<=Q; q++){
 int t; cin >> t;
 R += Swap(B[t], B[t+1]); swap(B[t], B[t+1]);
 cout << R << "\n";
 }
}

백준21823 Swap Swap Sort

댓글