글 읽기 - 해당 문제의 세그먼트트리 풀이코드 해설 가능할까요?

qktlf789456 2년 전 0

톡방에서 코드를 공유해주셨습니다.

몇시간 봐도 잘 이해가 가질않네요 ㅠ

세그트리도 저런방식은 적응도 안되서 그런지 로직이 이해가지않습니다.

혹시 어떤식으로 풀이가 된건지 해석좀가능할까요?

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <queue>

#define f(i,p)for(int i=0;i<p;i++)
#define x first
#define y second
#define all(x)x.begin(),x.end()


using namespace std;
using ll = long long;
int arr[500'010];

int tree[1048673];

vector<int> v;



int update(int n, int s, int e, int l, int r) {
    if (e < l || r < s || !tree[n])
        return 0;

    if (s == e) 
    {
        int k = tree[n];
        if (s != r)tree[n] = 0;
        return k;
    }

    int mid = s + e >> 1;
    int k = 0;

    k += update(n << 1, s, mid, l, r);
    k += update(n << 1 | 1, mid + 1, e, l, r);

    tree[n] = tree[n << 1] + tree[n << 1 | 1];

    return k;
}
void update(int n, int s, int e, int t) {
    if (e < t || t < s)return;
    if (s == e) {
        tree[n]++;
        return;
    }int mid = s + e >> 1;
    update(n << 1, s, mid, t);
    update(n << 1 | 1, mid + 1, e, t);
    tree[n] = tree[n << 1] + tree[n << 1 | 1];
}


int query(int n, int s, int e, int l, int r) {
    if (e < l || r < s)return 0;
    if (l <= s && e <= r)return tree[n];
    int mid = s + e >> 1;
    return query(n << 1, s, mid, l, r) + query(n << 1 | 1, mid + 1, e, l, r);
}


signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        v.push_back(arr[i]);
    }
    sort(all(v));


    v.erase(unique(all(v)), v.end());


    long long ans = 0;
    int pv = n + 5;


    for (int i = 0; i < n; i++)
    {
        arr[i] = lower_bound(all(v), arr[i]) - v.begin() + 2;
        ans += update(1, 1, pv, 1, arr[i]);


        if (query(1, 1, pv, arr[i] + 1, pv))ans++;
        update(1, 1, pv, arr[i]);
    }
    cout << ans;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

해당 문제의 세그먼트트리 풀이코드 해설 가능할까요?

qktlf789456 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말