Glass Bridge (백준 13372)

안녕하세요. 오늘은 유리다리문제를 풀 거예요.

문제

https://www.acmicpc.net/problem/13372

아이디어

그림만 봐도 (i<j)이고 (A[i]>A[j])인 (i,j)의 개수를 세면 됩니다. 세그트리로 간단하게 해주면 됩니다. 초기화도 잘 해줘야합니다.

소스코드

#include <iostream>
#define ll long long
using namespace std;

ll tree[404040] = { 0 };
ll init(ll s, ll e, ll node)
{
    if (s == e) return tree[node] = 0;
    ll mid = (s + e) / 2;
    return tree[node] = init(s, mid, node * 2) + init(mid + 1, e, node * 2 + 1);
}
ll SUM(ll s, ll e, ll node, ll l, ll r)
{
    if (e < l || r < s) return 0;
    if (l <= s && e <= r) return tree[node];
    ll mid = (s + e) / 2;
    return SUM(s, mid, node * 2, l, r) + SUM(mid + 1, e, node * 2 + 1, l, r);
}
void change(ll s, ll e, ll node, ll idx) //idx번지에 1 추가
{
    if (e < idx || idx < s) return;
    tree[node]++;
    if (s == e) return;
    ll mid = (s + e) / 2;
    change(s, mid, node * 2, idx);
    change(mid + 1, e, node * 2 + 1, idx);
}

int main(void)
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll T, N, i, x, ans;
    cin >> T;
    while (T--)
    {
        cin >> N;
        ans = 0; init(1, N, 1);
        for (i = 1; i <= N; i++)
        {
            cin >> x;
            ans += SUM(1, N, 1, x + 1, N);
            change(1, N, 1, x);
        }
        cout << ans << "\n";
    }
}

안녕히계세요~