제5회 kriiicon 연습 세션 D번 구간들

https://oj.uz/problem/view/KRIII5P_3

\(1\leq{N}\leq{10^5},\,0\leq{s_{i},\,e_{i}}\leq{10^9}\)

N개의 구간 \([s_{i},\,e_{i}]\) 가 입력으로 주어질 때(\(s_i\gt{e_i}\) 면 공집합)

구간들의 교집합이란 \([max(s_1,\,s_2,\,\cdots,\,s_k),\,min(e_1,\,e_2,\,\cdots,\,e_k)]\)

구간의 길이는 \(max(0,\,e_{i}-s_{i})\) 으로 정의 될 때

선택된 구간들의 교집합의 길이가 1이상이도록 구간들을 선택할 때

그 선택하는 방법의 수와 그 각각의 방법에서 교집합의 길이들의 합을 구하는 문제이다.

우선 방법의 수는 라인 스위핑으로도 풀 수 있고, 좌표압축+펜윅트리로도 풀 수가 있다.

그리고 길이의 합은 라인 스위핑으로 풀 수가 있다.

우선 모든 풀이에 공통적으로 사용되는 것이 있으니 이것을 구하고 넘어가자.

가능한 모든 k에 대해  \(2^k\pmod {1e7}\) 를 구해놓자. O(N) 이 걸릴 것이다.

우선 라인 스위핑으로 둘다 구해보자.

길이의 합을 구하는 트릭은

각각의 선택 방법에 대해 길이를 구해 누적하는 식으로 하는 것이아니라

각각의 세부 구간 단위로 잘게 나눠 이 세부 구간이 몇 개의 선택 방법에 포함이 되는지를 보는 것이다.

예를들어

이런 구간이 있다고 치면 [1,2],[2,3],[3,4],[4,5],[5,6] 구간 각각이 몇개의 선택 방법에 포함이 되는지 세는 것이다.

그럼 라인 스위핑에서 시작점과 끝점을 1과 -1로 표시해 주고 어떤 점을 지날 때 그 값을 더해주면

현재 겹쳐있는 구간의 수 x가 나올테니 \(2^x-1\) 을 하면 그 세부 구간을 포함하는 선택 방법의 수가 나온다.

(아무 구간도 택하지 않으면 포함될 수 없으므로 1을 빼야한다.)

이 것을 모든 세부 구간에 대해 하면 O(N) 이 나온다. 물론 처음에 정렬할 때 O(NlgN) 이므로 전체 복잡도는 O(NlgN).

라인스위핑으로 가짓수를 구해보자.

이게 말로 설명하기가 좀 힘든데, 일단 해봐야겠다.

prev 와 cur 라는 변수를 둔다.

2N개의 점들을 보는데 각 점은 어떤 구간의 시작점이거나 끝점일 것이다.

그렇다면 좌표로 오름차순 정렬되어있는 2N개의 점들은 시작점과 끝점이 반복될 것인데

시작점이 연속해서 나온다면 그 횟수만큼 cur++을 해주고

시작점이 계속 나오다가 끝점이 나오는 순간 \(2^{prev}*(2^{cur}-1)\) 를 답에 누적해주고 cur를 prev에 누적해준다.

끝점이 연속해서 나온다면 그 횟수만큼 prev--을 해준다.

이렇게 하는 이유는 겹치는 구간의 수가 증가했다 감소했다 할텐데  이것을 그래프로 그렸을 때

피크를 찍는 지점만 계산을 해서 중복을 피하고자 함이다. 그리고 한번 계산을 했지만

아직 e를 지나지 않은, 즉 겹쳐있는 구간들의 수는 prev에 아직 계산하지 않으면서 겹쳐있는 구간들의 수 cur에

따로 관리함으로써 중복을 피하는 것이다. 아직 계산하지 않은 구간들 중에서는 최소한 1개는 골라야 중복이 안생기므로

\(2^{cur}-1\) 을 한것이고 이미 계산한 구간들은 어차피 아직 계산하지 않은 구간들이 새롭게 1개 이상 선택되므로

선택하거나 안하거나 상관없이 새로운 선택 방법이 계산되는 것이기 때문에 \(2^{prev}\) 를 하여 두개를 곱하는 것이다.

이것을 누적시키면서 2N개의 지점에 대해 반복하면 답이 나온다.

#include <bits/stdc++.h>
#define REP(i,a,b) for(int i=a;i<=b;++i)
#define FOR(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define sz(v) ((int)(v).size())
#define inp1(a) scanf("%d",&a)
#define inp2(a,b) scanf("%d%d",&a,&b)
#define inp3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define inp4(a,b,c,d) scanf("%d%d%d%d",&a,&b,&c,&d)
#define inp5(a,b,c,d,e) scanf("%d%d%d%d%d",&a,&b,&c,&d,&e)
#define fastio() ios_base::sync_with_stdio(false),cin.tie(NULL)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<int> vi;    
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<vector<int> > vvi;
typedef pair<int,pair<int,int> > piii;
typedef vector<piii> viii;
const double EPSILON = 1e-9;
const double PI = acos(-1);
const int MOD = 1e9+7;
const int INF = 0x3c3c3c3c;
const long long INFL = 0x3c3c3c3c3c3c3c3c;
const int MAX_N = 102;
 
int N;
ll pow2[100003];
vll v;
 
int main() {
    inp1(N);
    int cnt = 0;
    FOR(i,N){
        ll a,b;
        scanf("%lld%lld",&a,&b);
        if(a>=b) {
            cnt++;
            continue;
        }
        v.pb({a,1});
        v.pb({b,-1});
    }
    N-=cnt;
 
    sort(all(v));
 
    pow2[0] = 1;
    FOR(i,100001) pow2[i+1] = (pow2[i] * 2) % MOD;
 
    ll sum = 0;
    int on = 0;
    
    FOR(i,sz(v)){
        on += v[i].second;
        if(!on) continue;
        if(i!=sz(v)-1) sum = (sum + (v[i+1].first-v[i].first)*(pow2[on]-1)) % MOD;;
    }
 
    int prev = 0;
    int cur = 0;
    ll ans = 0;
    on = 0;
    FOR(i,sz(v)){
        on += v[i].second;
        if(v[i].second == 1 && (i == sz(v)-1 || v[i+1].second == -1)){
            cur++;
            ans = (ans + pow2[prev]*(pow2[cur]-1)) % MOD;
            prev += cur;
            cur = 0;
        }
        if(v[i].second == 1 && (i < sz(v)-1 && v[i+1].second == 1)) cur++;
        if(v[i].second == -1) prev--;
    }
 
 
    printf("%lld %lld",sum, ans);
    return 0;
}
 

교집합의 길이가 1이상인 선택 방법들의 가짓수를 좌표압축+펜윅트리로 구하는 방법은

우선 좌표 압축을 하여 모든 좌표가 2*N 이하가 되도록 만든다.

그리고 N개의 구간에 대해 구간의 시작 좌표 s 를 인덱스로 펜윅트리에 업데이트한다.

즉, query(x) 는 현재 구간의 시작 s가 x이하인 구간들의 수가 되도록 한다.

그리고 N개의 구간을 구간의 끝 좌표 e 로 오름차순 정렬한다.

이제 N개의 구간을 차례대로 보는데 조금만 생각해보면 한가지 알 수 있는 사실이 뭐냐면

N개중에 일부 구간을 선택 했을 때, 그 교집합의 길이가 1 이상이려면 선택한 구간들을 구간의 끝 e로 정렬했을 때

맨 앞에 오는 구간의 e가 나머지 모든 구간의 s보다 크다는 사실이다.

그렇기 때문에 N개의 구간을 차례대로 보면서

'이 구간을 맨처음으로 선택한다고 가정했을 때 e가 이 구간의 e보다 크거나 같으면서, s가 이 구간의 e보다 작은 구간'들의

수 x를 알 수 있다면 \(2^x\) 가 되므로 이것을 누적해주면 된다.

그런데 우리는 처음에 e로 오름차순 정렬했기 때문에 아직 보지않은 뒤쪽 구간들은

무조건 e가 현재 보고있는 구간의 e보다 크거나 같다는 사실을 알 수가 있다. 그렇기 때문에 각 구간을 볼 때

펜윅 트리에서 현재 보고있는 구간의 s를 인덱스로 -1 만큼 업데이트 시켜주고 query(e-1) 를 날리면

'e가 지금 보는 구간의 e보다 크거나 같으면서, s가 이 구간의 e보다 작은 구간'들의 수 x가 나올 것이다.

그러면 이것으로 \(2^x\) 을 누적해주면서 N개의 구간에 대해 반복하면 끝이다.

#include <bits/stdc++.h>
#define REP(i,a,b) for(int i=a;i<=b;++i)
#define FOR(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define sz(v) ((int)(v).size())
#define inp1(a) scanf("%d",&a)
#define inp2(a,b) scanf("%d%d",&a,&b)
#define inp3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define inp4(a,b,c,d) scanf("%d%d%d%d",&a,&b,&c,&d)
#define inp5(a,b,c,d,e) scanf("%d%d%d%d%d",&a,&b,&c,&d,&e)
#define fastio() ios_base::sync_with_stdio(false),cin.tie(NULL)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<int> vi;    
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<vector<int> > vvi;
typedef pair<int,pair<int,int> > piii;
typedef vector<piii> viii;
const double EPSILON = 1e-9;
const double PI = acos(-1);
const int MOD = 1e9+7;
const int INF = 0x3c3c3c3c;
const long long INFL = 0x3c3c3c3c3c3c3c3c;
const int MAX_N = 102;
 
int N;
set<ll> st;
vll range;
vl comp;
ll t[800003];
ll pow2[100003];
int size;
vll v;
void update(int pos, int v){
    while(pos <= size){
        t[pos] += v;
        pos += pos&-pos;
    }
}
 
ll query(int pos){
    ll ret = 0;
    while(pos > 0){
        ret += t[pos];
        pos -= pos&-pos;
    }
    return ret;
}
 
bool cmp(pll& A, pll& B){
    return A.second < B.second;
}
 
int main() {
    inp1(N);
    int cnt = 0;
    FOR(i,N){
        ll a,b;
        scanf("%lld%lld",&a,&b);
        if(a>=b) {
            cnt++;
            continue;
        }
        st.insert(a), st.insert(b);
        range.pb({a,b});
    }
    N-=cnt;
    for(auto it = st.begin() ; it != st.end(); it++){
        comp.pb((*it));
    }
    size = sz(comp);
 
    FOR(i,N){
        ll& a = range[i].first;
        ll& b = range[i].second;
        v.pb({a,1});
        v.pb({b,-1});
        a = lower_bound(all(comp),a) - comp.begin() + 1;
        b = lower_bound(all(comp),b) - comp.begin() + 1;
    }
    sort(all(v));
    sort(all(range),cmp);
 
    pow2[0] = 1;
    FOR(i,100001) pow2[i+1] = (pow2[i] * 2) % MOD;
 
    ll sum = 0;
    int on = 0;
    FOR(i,sz(v)){
        on += v[i].second;
        if(!on) continue;
        if(i!=sz(v)-1) sum = (sum + (v[i+1].first-v[i].first)*(pow2[on]-1)) % MOD;;
    }
 
    FOR(i,N) {
        update(range[i].first,1);
    }
 
    ll ans = 0;
 
    FOR(i,N){
        update(range[i].first,-1);
        ans = (ans + pow2[query(range[i].second-1)]) % MOD;
    }
    
    printf("%lld %lld",sum, ans);
    return 0;
}