백준 7578번 공장

문제 링크입니다: https://www.acmicpc.net/problem/7578

유형은 다르지만 백준 6549번 히스토그램에서 가장 큰 직사각형(http://jaimemin.tistory.com/705)처럼 세그멘트 트리를 응용해서 푸는 문제였습니다.

알고리즘은 아래와 같습니다.

1. A열에 위치한 기계를 입력받은 뒤 B 배열에는 입력받은 기계 번호를 index, 인덱스를 value로 저장합니다.

-> STL map을 이용할 경우 TLE 발생

2. A열에서 순차적으로 교차하는 케이블 쌍의 개수를 구하는데 이는 1 ~ B[A[i]]까지 누적합을 구하면 됩니다.

3. 2번 과정이 끝나면 해당 B[A[i]]를 1로 표시하고 누적합을 업데이트합니다.

4. A열의 모든 기계에 대해 2, 3번 과정을 반복합니다.

#include <iostream>

#include <vector>

#include <algorithm>

#include <map>

#include <cmath>

using namespace std;

 

const int MAX = 1000000 + 1;

 

int N;

//map<int, int> B;

int B[MAX]; //B에서 A[i]의 인덱스 저장

 

void update(vector<long long> &tree, int start, int end, int node, int idx)

{

        if (idx < start || end < idx)

                 return;

        if (start == end)

        {

                 tree[node] = 1;

                 return;

        }

       

        int mid = (start + end) / 2;

        update(tree, start, mid, node * 2, idx);

        update(tree, mid + 1, end, node * 2 + 1, idx);

       

        tree[node] = tree[node * 2] + tree[node * 2 + 1];

}

 

//구간 합

long long query(vector<long long> &tree, int start, int end, int node, int i, int j)

{

        if (j < start || end < i)

                 return 0;

        if (i <= start && end <= j)

                 return tree[node];

 

        int mid = (start + end) / 2;

        return query(tree, start, mid, node * 2, i, j) + query(tree, mid + 1, end, node * 2 + 1, i, j);

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0); //cin 속도 향상

        cin >> N;

 

        vector<long long> A(N + 1);

        //세그먼트 트리 크기

        int height = (int)ceil(log2(N));

        int tree_size = (1 << (height + 1));

 

        vector<long long> tree(tree_size);

        for (int i = 1; i <= N; i++)

                 cin >> A[i];

        for (int i = 1; i <= N; i++)

        {

                 int temp;

                 cin >> temp;

 

                 B[temp] = i;

        }

 

        long long result = 0;

        for (int i = 1; i <= N; i++)

        {

                 //B[A[i]] ~ N까지 누적합을 더한다

                result += query(tree, 1, N, 1, B[A[i]], N);

                 //B[A[i]] 표시하고 누적합 업데이트

                 update(tree, 1, N, 1, B[A[i]]);

        }

 

        cout << result << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~