[백준] 공장(7578)

문제 링크 : [백준] 공장(7578)

문제 설명

두 개의 라인(위, 아래)이 있고, 위 라인과 아래 라인에 서로 짝이 이어지는 장비들이 N개 존재합니다.
짝을 이루는 장비는 서로 같은 번호를 가집니다.
짝을 이루는 장비들을 서로 연결하였을 때, 교차하는 지점의 갯수를 구하세요.

입력

N(장비의 갯수, 1<=N<=500,000)
U_i(윗 라인의 장비 배치, 0<=U_i<=1,000,000)
D_i(아래 라인의 장비 배치, 0<=D_i<=1,000,000)

5
132 392 311 351 231
392 351 132 311 231

출력

3

카테고리

#펜윅트리, #세그먼트트리

시간 복잡도 상한

O(NlogN)까지 가능합니다.

해결 방법

1. 한 장비를 연결하는데 몇 개의 선을 가로지르는지를 파악해야합니다.
2. 위 라인에서는 장비_i보다 왼쪽에 있었으나, 아래 라인에서 장비_i보다 오른쪽에 있는 경우, 장비_i와 교차하게 됩니다.
3. 2에 의해서, 위 라인의 장비를 왼쪽에서 오른쪽 방향으로 검사한다면, 장비_i와 교체하는 장비는 아래와 같은 조건의 장비들입니다.
   3-1. 위 라인에서는 장비_i보다 먼저 나타났지만
   3-2. 아래 라인에서 장비_i보다 오른쪽에 있는 장비
4. 위 라인을 기준으로, 왼쪽에서 오른쪽으로 진행하면서, 3의 기준에 맞는 장비의 갯수를 세기 위해서는 아래와 같이 진행합니다.
   4-1. 장비_i의 아래 라인의 위치 ~ 끝까지 이미 나타난 장비의 갯수를 세어줌
   4-2. 장비_i의 아래 라인의 위치에 현재 장비가 나타났다는 표시를 해줌
5. 특정 인덱스의 값을 변경, 구간의 합을 반복적으로 구해주는 로직이므로 펜윅 트리나, 세그먼트 트리를 이용하면 빠르게 구할 수 있습니다.

• 주의) 각 장비의 번호를 인덱스로만 주었으면 좀 간단했을텐데, 임의의 숫자로 주어 장비의 번호를 새로 인덱싱해야 합니다.

시간복잡도

O(NlogN)

코드

#include<iostream>
#define f for(i=1;i<=n;i++)
using namespace std;
int n,a[500001],b[1000001],c[500001],t,i;
long long s;
void u(int p){
    while(p<=n)c[p]+=1,p+=p&-p;
}
int q(int p){
    int r=0;
    while(p)r+=c[p],p-=p&-p;
    return r;
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    f cin>>a[i];
    f cin>>t,b[t]=i;
    f s+=q(n)-q(b[a[i]]),u(b[a[i]]);
    printf("%lld",s);
}