[백준] 7578 공장

교차하는 케이블의 수를 세는 문제다

펜윅트리 or 머지소트로 풀수있다..!

처음에 세그먼트트리로 풀었는데 계속 시간초과가 나길래

방법이 틀린 줄 알았는데 map을 써서 시간초과가 났따 ㅎㅎ

문제를 푸는 방법은

1. 펜윅트리를 만든다. 초기값은 모두 0

2. 1~n까지 탐색을하며 B에서의 나의 위치 뒤에있는 것의 합을 더한다!

3. 그리고 나의 위치를 트리에서 1로 바꿔준다

교차점의 수를 세는 것이므로 A의 앞에있던 공장이 B에서는 뒤에있다면 교차점이 생긴다. 그래서 뒤에 1이 몇개있는지만 세어주면 된다!

소스코드 - 펜윅트리

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n;
#define ll long long
int a[500050], tree[500050],mp[1000010];
 
int sum(int i) {
    int ret = 0;
    while (i > 0) {
        ret += tree[i];
        i -= (i&(-i));
    }
    return ret;
}
 
void update(int i) {
    while (i <= n) {
        tree[i] += 1;
        i += (i&(-i));
    }
}
 
int main() {
    scanf(" %d", &n);
 
    for (int i = 1; i <= n; i++) scanf(" %d", &a[i]);
    for (int i = 1; i <= n; i++) {
        int x; scanf(" %d", &x);
        mp[x] = i;
    }
 
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        ans += (ll)sum(n) - (ll)sum(mp[a[i]]);
        update(mp[a[i]]);
    }
    printf("%lld\n", ans);
}

세그먼트트리

#include <iostream> #include <algorithm> #include <vector> #include <cmath> #include <map> using namespace std; #define ll long long int n; int mp[1000100]; void update(vector<int>&tree, int node, int start, int end, int index, int val) { if (index <start || index > end) return; if (start == end) { tree[node] = val; return; } update(tree, node * 2, start, (start + end) / 2, index, val); update(tree, node * 2 + 1, (start + end) / 2 + 1, end, index, val); tree[node] = tree[node * 2] + tree[node * 2 + 1]; } int query(vector<int>&tree, int node, int start, int end, int i, int j) { if (j<start || i>end) return 0; if (i <= start && end <= j) return tree[node]; return query(tree, node * 2, start, (start + end) / 2, i, j) + query(tree, node * 2 + 1, (start + end) / 2 + 1, end, i, j); } int main() { scanf(" %d", &n); int h = (int)ceil(log2(n)); int tree_size = (1 << (h + 1)); vector<int> a(n); vector<int> tree(tree_size); for (int i = 0; i < n; i++) scanf(" %d", &a[i]); for (int i = 0; i < n; i++) { int x; scanf(" %d", &x); mp[x] = i; } ll ans = 0; for (int i = 0; i < n; i++) { ans += (ll)query(tree, 1, 0, n - 1, mp[a[i]], n - 1); update(tree, 1, 0, n - 1, mp[a[i]], 1); } printf("%lld\n", ans); }

cs