[백준] 17131 - 여우가 정보섬에 올라온 이유 (c++)

https://www.acmicpc.net/problem/17131

 

문제 요약

좌표 평면에 점 N개가 주어진다. 세점 s,t,u가  s.x<t.x<u.x이고 s.y>t.y<u.y를 만족하는 경우의 수를 구해라.

 

풀이 1 (NlogY) 

• 세그먼트 트리
• 스위핑

처음에 떠오른 펜윅 두개를 관리하며 x축 스위핑을 하는 방법이다.

펜윅 하나는 y에 대해 y보다 큰 점의 개수를 관리하고 다른 하나는 t.y가 y보다 작은 s,t 쌍의 개수를 관리한다. 그럼 현재 점이 u일때 s,t,u 쌍의 개수를 구할 수 있다. x좌표가 겹치면 안되기 때문에 x좌표가 같은 점끼리 묶어서 처리해야 한다.

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N =4e5+5,mod=1e9+7;

ll up[N],down[N];
void uupdate(int x,int a) {
    x+=2e5+1;
    for(int i=x;i;i-=i&-i)
        up[i]+=a;
}
ll usum(int x) {
    x+=2e5+1;
    ll ret=0;
    for(int i=x;i<=N;i+=i&-i)
        ret+=up[i];
    return ret;
}
void dupdate(int x,int a) {
    x+=2e5+1;
    for(int i=x;i<=N;i+=i&-i)
        down[i]+=a;
}
ll dsum(int x) {
    x+=2e5+1;
    ll ret=0;
    for(int i=x;i;i-=i&-i)
        ret+=down[i];
    return ret;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n;cin>>n;
    vector<array<int,2>> v(n);
    for(auto& [x,y]:v) cin>>x>>y;
    sort(v.begin(),v.end());
    ll ans=0;
    for(int i=0;i<v.size();) {
        //cout<<i<<'\n';
        vector<array<int,2>> sx;
        while(sx.empty()||(i<v.size()&&sx[0][0]==v[i][0]))
            sx.push_back(v[i]),i++;
        for(auto [x,y]:sx) 
            ans+=dsum(y),ans%=mod;
        for(auto [x,y]:sx)
            dupdate(y+1,usum(y));
        for(auto [x,y]:sx)
            uupdate(y-1,1);
    }
    cout<<ans;
}

 

풀이 2 (NlogX) 

• 세그먼트 트리
• 스위핑

y축 스위핑을 하면 펜윅하나로도 풀 수 있다. 오름차순으로 스위핑하며 현재 점을 t로 두고 s의 개수*u의 개수를 구해주면 된다.

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N =4e5+5,mod=1e9+7;

ll bit[N];
void update(int x,int a) {
    x+=2e5+1;
    for(int i=x;i;i-=i&-i)
        bit[i]+=a;
}
ll sum(int x) {
    x+=2e5+1;
    ll ret=0;
    for(int i=x;i<=N;i+=i&-i)
        ret+=bit[i];
    return ret;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n;cin>>n;
    vector<array<int,2>> v(n);
    for(auto& [y,x]:v) cin>>x>>y;
    sort(v.rbegin(),v.rend());
    ll ans=0;
    for(int i=0;i<v.size();) {
        vector<array<int,2>> sy;
        while(sy.empty()||(i<v.size()&&sy[0][0]==v[i][0]))
            sy.push_back(v[i]),i++;
        for(auto [y,x]:sy) 
            ans+=sum(x+1)*(sum(-2e5)-sum(x)),ans%=mod;
        for(auto [y,x]:sy)
            update(x,1);
    }
    cout<<ans;
}