백준 25462 - Inverzije (C++)

문제

• 문제 링크

  
   BOJ 25462 - Inverzije 
  

• 문제 요약

길이 $N$인 수열과 $Q$개의 구간 쿼리가 주어진다.
각 쿼리에 맞는 답을 출력하자.

• 제한

TL : $4$ sec, ML : $1024$ MB




$1 ≤ N, Q ≤ 100,000$

$1 ≤ a_i, b_i, P_i ≤ N$

알고리즘 분류

• 자료 구조(data structures)
• 세그먼트 트리(segment tree)
• 오프라인 쿼리(offline_queries)
• mo's(mo's algorithm)

풀이

수쿼 $23$ 을 풀어 봤다면 보자마자 솔루션이 떠올랐을 것이다.
쿼리 내용 보자.

$Q :$ $[a, b]$ 에 대해, $a ≤ i < j ≤ b$ 면서 $P_i > P_j$ 인 $(i, j)$ 쌍의 개수.

전형적인 $mo's$ 문제 형태이다.
어떤 수 $x$가 현재 보고 있는 구간의 끝점에서 추가될 때 / 제거될 때 로 나눠 생각해보자.

추가 될 때 : 현재 보는 구간 상에 $x$보다 작은 수(또는 큰 수) 의 개수를 더해 주어야 한다.

제거 될 때 : 현재 보는 구간 상에 $x$보다 작은 수(또는 큰 수) 의 개수를 빼내 주어야 한다.

작은 수 / 큰 수 가 갈리는 이유는 당연히 구간의 끝 점이 왼 쪽에서 변하냐, 오른 쪽에서 변하냐에 따라 취급 기준이 달라지기 때문이다.

또한 구간 관리는 세그먼트 트리를 이용하면 간단하고 효율적으로 관리할 수 있다.

하나 유의할 건 재귀 세그보다 펜윅 세그를 이용하도록 하자.
이렇게 자잘한 업데이트가 많이 일어나는 상황에선 재귀 / 펜윅 간에 상수 차이를 무시할 수 없다.

최종적으로 약 $O(max(N, Q) * √NlogN)$ 정도로 문제를 해결할 수 있다.

전체 코드

#include<bits/stdc++.h>
#define N 100001
using namespace std;
 
struct _Q { int s, e, i; }Q[N];
long long t, an[N];
int n, q, seg[N], c[N];
 
void Init()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> q;
    for (int i(1); i <= n; cin >> c[i++]);
    for (int i{}; i < q; i++)
        cin >> Q[i].s >> Q[i].e, Q[i].i = i;
}
void f(int p, int q)
{
    while (p <= N - 1)
        seg[p] += q, p += p & -p;
}
int g(int p, int r = 0)
{
    while (p)
        r += seg[p], p -= p & -p;
    return r;
}
void Solve(int s, int e)
{
    sort(Q, Q + q, [](_Q x, _Q y)
        {
            x.s /= 400, y.s /= 400;
            return x.s ^ y.s ? x.s < y.s : x.e < y.e;
        });
    for (int i{}; i < q; i++)
    {
        while (s > Q[i].s) t += g(c[--s] - 1), f(c[s], 1);
        while (s < Q[i].s) t -= g(c[s] - 1), f(c[s++], -1);
        while (e > Q[i].e) t -= g(N - 1) - g(c[e]), f(c[e--], -1);
        while (e < Q[i].e) t += g(N - 1) - g(c[++e]), f(c[e], 1);
        an[Q[i].i] = t;
    }
    for (int i{}; i < q; cout << an[i++] << '\n');
}
int main()
{
    Init();
    Solve(Q[0].s, Q[0].s - 1);
}

comment

끝