백준(BOJ) 9463 순열 그래프 **

#세그먼트 트리

아이디어는 내가 간단하다 내가 이번에 이을 숫자 쌍 뒤로 몇개의 숫자가 존재하냐를 묻는 문제이다.

여기서 "뒤로 몇개의 숫자가 존재하냐"를 세그먼트 트리로 구현 해주면된다.

# 실수 했던 점

세그먼트 트리를 오랜만에 풀었더니 퀴리함수에서 탈출조건을 잘못써서 시간초과가 한번났다.

정답은 long long형 이여야 한다.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#define MAX 100005
#define INF 987654321
#define MOD 1000000
#pragma warning(disable:4996)
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;

int t,n,m,loc[MAX],arr[MAX],seg[MAX*4];

int update(int val,int pos,int x,int y)
{
    if(!(x<=val&&val<=y))
        return seg[pos];
    if(x==y)
        return seg[pos]=1;
    return seg[pos]=update(val,pos*2,x,(x+y)/2)+update(val,pos*2+1,(x+y)/2+1,y);
}
int query(int pos,int l,int r,int x, int y)
{
    if(y<l||r<x)
        return 0;
    if(l<=x&&y<=r)
        return seg[pos];
    return  query(pos*2,l,r,x,(x+y)/2)+query(pos*2+1,l,r,(x+y)/2+1,y);
}
int main() {
    scanf("%d", &t);
    for(int i=0;i<t;i++)
    {
        ll ans=0;
        fill_n(&seg[0],MAX*4,0);
        scanf("%d",&n);
        for(int k=1;k<=n;k++)
        {
            scanf("%d",&m);
            loc[m]=k;
        }
        for(int k=1;k<=n;k++)
        {
            scanf("%d",&m);
            arr[k]=loc[m];
        }
        for(int k=1;k<=n;k++)
        {
            ans+=(ll)query(1,arr[k],n,1,n);
            update(arr[k],1,1,n);
        }
        printf("%lld\n",ans);
    }
    return 0;
}