BOJ 22878(간단한 문제)풀이

이미지를 누르면 문제로 이동합니다

문제 설명이 이게 다인 문제 설명은 간단한 문제이다. 이 문제를 처음 볼 때 이상한 수학으로 풀어야 되는 건가 싶을 수 있지만 사실 세그를 사용해서 풀 수 있다.  일단 |p [i]-p [j]| 를 1번이라고 하고 |q [i]-q [j]|  를 2번이라고 하겠다.

이 문제는 1번과 2번 중 작은 값을 골라야 하기 때문에 1번이 작은 경우와 2번이 작은 경우 이렇게 2개로 나눌 수 있다.

1번이 작거나 같은 경우부터 생각해보자. 1번이 작거나 같을려면 (j < i)

 

p[i] >= p[j] 일때	p[i] < p[j] 일때
p[i]-p[j] <= q[i]-q[j]	p[j]-p[i] <= q[i]-q[j]
p[i]-p[j] <= q[j]-q[i]	p[j]-p[i] <= q[j]-q[i]

이렇게 4가지의 경우가 생긴다. 이때 p를 정렬한다면 어떻게 될까? p를 정렬한다면 p [i] >= p [j]만 존재하게 된다. 그러므로 p [i] < p [j]는 없어져서 2가지 조건만 남게 된다. 이제 조금 더 나아가 보자.

 

p [i]-p [j] <= q [i]-q [j]라는 식을 적절히 이항 시켜주면 p [i]-q [i] <= p [j]-q [j]가 된다. 또 p [i]-p [j] <= q [j]-q [i] 도 이항 시켜주면 p [i]+q[i] <= p[j]+q[j] 가 된다. 이때 여기서 무언가 보인다는걸 알 수 있다. p[i] 와 q[i]는 i라는 같은 위치에 있는 것이고 p[j] 와 q[j] 도 맞찬가지다. 그러면 p를 정렬할 때 q는 처음에 입력받았을 때 같은 위치에 있는 p[i]와 이어준 다음 정렬을 해주게 되면 반복을 하면서 i번째가 되면 p[i], q[j] 모두 알게되는 것이다. 또 위에서 j가 더 작다고 했기 때문에 이미 i가 되기 전에 탐색을 한 것이다. i 번째에선 0 ~ i-1 위치랑 비교했을 때 p[i] - q[i]가 작은 것들을 찾으면 되기 때문에 j 번째 값을 빠르게 불러와 탐색을 할 수 있다면 이 문제를 풀 수 있게 되는것이다. 이때 세그를 사용하면 j번째 값들을 구할 수 있다.

일단 처음에 2개의 세그를 만들고 각각 세그에 개수를 저장하는 노드와 합을 저장하는 노드를 만들어 준다. p를 기준으로 정렬을 한 뒤 반복을 하면서 합 노드에 p [i] - q [i] 와 p[i] + q[i] 위치에 p[i] 를 더해준다. 그리고 같은 위치에 개수 노드에는 1을 더해준다. p[i]를 더해주는 이유는 조금 뒤에 알게 될 것이다.

값을 더해주는 코드 앞에 p [i] - q[i] 보다 같거나 큰 위치의 값을 모두 더해주는 코드를 작성해준다. 위에서 썼던거 처럼 p [i]-q [i] <= p [j]-q [j] 를 만족해야되고 위에서 p[j]-q[j] 위치에 p[j]를 더해주고 있으니 p[i]-q[i] 보다 같거나 큰 위치들에서의 합을 구해주게 되면 위 식을 만족하는 p[j]를 구할 수 있다. 이때 p[j]를 구해주는 이유는 |p [i]-p [j]|를 구해줘야되는 것이고 정렬을 해줬기 때문에 p[i] >= p[j]는 언제나 성립한다. 그러므로 |p[i]-p[j]| 이 값을 모두 더해줄때 |p[i]-p[j_1]|+|p[i]-p[j_2]|+|p[i]-p[j_3]| .... 이렇게 되는데 이 식을 풀어주면 p[i]*(p[j]의 개수)-(p[j]의 합) 이 된다. 그러므로 p[j]의 합과 개수를 구해주게 되면 p[i]-q[i] <= p[j]-q[j] 이 식을 만족하는 |p[i]-p[j]|를 구할 수 있다. 위와 같은 방법으로 p [i]+q [i]도 다른 세그에서 똑같은 방법으로 구해주는 것을 반복하면 1번이 작거나 같은 경우의 합을 구할 수 있게 된다.

 

이제 2번이 작은 경우를 구해줘야 되는데 이것도 위와 같은 방법으로 해주는데 이때는 같거나 작은 경우가 아닌 작은 경우만 구해줘야 되기 때문에 위와 같은 방법이지만 위치에 +1을 해준 다음 값을 구해주면 된다.

 

이렇게 값을 구해준 뒤 두 값을 더한 뒤 *2를 해주면 된다.(*2를 해주는 이유는 i와 j가 반대로 됐을 때도 절댓값이 쓰여있기 때문에 같은 값이 나오기 때문에 마지막에 *2를 해주는 것이다.)

 

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct nd{
    ll cnt,v;
};
vector<nd>t(8000020);
vector<nd>mt(8000020);
ll p[1000001],q[1000001];
pair<ll,ll>st[1000001];
void seg(ll n,ll s,ll e){
    t[n]={0,0};
    mt[n]={0,0};
    if(s==e)return;
    seg(n*2,s,(s+e)/2);
    seg(n*2+1,(s+e)/2+1,e);
}
nd S(ll n,ll s,ll e,ll left,ll right){
    if(left>e||right<s){return {0,0};}
    if(left<=s&&e<=right){return t[n];}
    nd Left=S(n*2,s,(s+e)/2,left,right);
    nd Right=S(n*2+1,(s+e)/2+1,e,left,right);
    return{Left.cnt+Right.cnt,Left.v+Right.v};
}
void c(ll n,ll s,ll e,ll i,ll f){
    if(i<s||i>e){return;}
    t[n].cnt++;
    t[n].v+=f;
    if(s!=e){c(n*2,s,(s+e)/2,i,f);c(n*2+1,(s+e)/2+1,e,i,f);}
}
nd ms(ll n,ll s,ll e,ll left,ll right){
    if(left>e||right<s){return {0,0};}
    if(left<=s&&e<=right){return mt[n];}
    nd Left=ms(n*2,s,(s+e)/2,left,right);
    nd Right=ms(n*2+1,(s+e)/2+1,e,left,right);
    return{Left.cnt+Right.cnt,Left.v+Right.v};
}
void mc(ll n,ll s,ll e,ll i,ll f){
    if(i<s||i>e){return;}
    mt[n].v+=f;
    mt[n].cnt++;
    if(s!=e){mc(n*2,s,(s+e)/2,i,f);mc(n*2+1,(s+e)/2+1,e,i,f);}
}
int main()
{
    ll a,ans1=0,ans2=0,C,V,P,Q,C1,V1;
    nd T,T1;
    scanf("%lld",&a);
    for(int i=0;i<a;i++)scanf("%lld ",&p[i]);
    for(int i=0;i<a;i++)scanf("%lld ",&q[i]);
    for(int i=0;i<a;i++){st[i].first=p[i];st[i].second=q[i];}
    sort(st,st+a);
    seg(1,1,2000001);
    for(int i=0;i<a;i++){
        P=st[i].first;
        Q=st[i].second;
        T=S(1,1,2000001,P-Q+1000000,2000001);
        C=T.cnt;
        V=T.v;
        T1=ms(1,1,2000001,P+Q,2000001);
        C1=T1.cnt;
        V1=T1.v;
        ans1+=(C+C1)*P-V-V1;
        c(1,1,2000001,P-Q+1000000,P);
        mc(1,1,2000001,P+Q,P);
    }
    for(int i=0;i<a;i++){st[i].first=q[i];st[i].second=p[i];}
    sort(st,st+a);
    seg(1,1,2000001);
    for(int i=0;i<a;i++){
        Q=st[i].first;
        P=st[i].second;
        T=S(1,1,2000001,Q-P+1000001,2000001);
        C=T.cnt;
        V=T.v;
        T1=ms(1,1,2000001,Q+P+1,2000001);
        C1=T1.cnt;
        V1=T1.v;
        ans2+=(C+C1)*Q-V-V1;
        c(1,1,2000001,Q-P+1000000,Q);
        mc(1,1,2000001,Q+P,Q);
    }
    printf("%lld\n",(ans1+ans2)*2);
}