BOJ 18721 - clique

문제 링크 : https://www.acmicpc.net/problem/18721

문제 태그 

세그먼트 트리

문제 풀이

와... 미친 아이디어 문제이다. 솔직히 자력으로는 정말 풀기 힘든 문제라고 생각한다. 어쩌면 수올러들이 생각할 확률이 더 높을 수 있다. 그런 느낌의 풀이이다. 

왠만하면 오래 고민해보고 이 글을 읽는 것을 추천드리며, 이 글을 읽을 때도 풀이의 일부씩만 보고 다음 직접 풀이를 완성하면 훨씬 좋을 것 같다. 

처음에 1주일동안 생각했다가 도저히 떠오르지 않아서 풀이의 첫줄을 보았다. 
"한 호를 잡아 정답이 되는 세트의 가장 작은 호라고 생각해보자"

이 문장에 대해서 곰곰히 생각해 보니까 풀이가 서서히 확장되기 시작했다. 이 글과 같이 분석을 해보면 지정한 호와 다른 호들의 관계를 분류할 수 있다. 이 중에서 지정한 호가 포함하는 호, 만나지 않는 호는 절대 답에 포함되지 않으며, 지정한 호를 포함하는 호, 양쪽 모두 만나는 호는 무조건 답에 포함된다. 

따라서 지정한 호에 대해서 왼쪽으로만 만나는 호 들과 오른쪽으로만 만나는 호 들에 대해서만 생각할 수 있다. 이렇게 되면 각 그룹 내에서는 무조건 임의의 두 호를 골라도 만난다는 것을 알 수 있다.
※편의상 왼쪽에서만 만나는 그룹을 a그룹, 오른쪽에서만 만나는 그룹을 b그룹이라고 하자. 

이제 문제는 대략 $O(N^2)$ 미만의 시간복잡도로 두 그룹에서 적당히 호들을 뽑아내어 임의의 어떤 서로 다른 그룹에서 뽑아낸 호도 겹치게 하는 뽑아낼 수 있는 호의 최대 수를 알아내는 문제로 변환시켰다.

여기서 한 가지 작은 관찰을 해야한다. a그룹의 호와 b그룹의 호는, 맨 처음 설정했던 기준호 안쪽에서 만나거나 바깥쪽에서 만나면 된다.
이를 살짝만 더 생각해보면, 두 호가 기준 호 안쪽으로 삐져나온 길이가 기준 호 길이 이상이거나, 기준 호 바깥 쪽으로 삐져나온 길이가 바깥쪽의 길이 이상이면 만난다.

그렇다면 우리는 (안쪽으로 삐져나온 길이, 바깥쪽으로 삐져나온 길이)의 순서 쌍을 생각할 수 있고, 이는 자연스럽게 좌표에 대한 아이디어로 이어진다. 

여기서 한 번더 발전시키자. A그룹은 위와 같은 순서 쌍의 좌표를 가지게 되지만, B그룹에 대한 호들은 순서 쌍의 값을 (이 호와 만나기 위해 안쪽으로 삐져나와야 하는 길이, 바깥쪽으로 삐져나와야 하는 길이) 로 바꾸자. 
이러한 점들을 격자점에 찍는다. 그러면 문제는 임의의 B점 좌하단에 A점이 없도록하는 점 그룹의 최대 크기를 구하는 문제가 된다.
이 문제는 고민을 좀 해보면 x좌표가 큰 순서 - y좌표가 큰 순서대로 정렬하고, A점 혹은 B점을 만날 때마다 segment tree에 알맞는 행동을 취해주면 $O(NlgN)$에 해결할 수 있다는 것을 알 수 있다.

따라서 전체 문제는 $O(N^2lgN)$에 해결할 수 있다

코드

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pii;
#define ff first
#define ss second
#define ep emplace_back
#define eb emplace
#define pb push_back
 
pii arr[101010];
ll bet[3030][3030];
 
struct poi{
    ll t,x,y;
};
 
struct nod{
    ll val,laz;
};
 
poi pp[101010];
nod tree[101010];
ll yval[10101];
 
void lz(ll s,ll e,ll nod){
    if(tree[nod].laz){
        tree[nod].val+=tree[nod].laz;
        if(s!=e){
            tree[nod*2].laz+=tree[nod].laz;
            tree[nod*2+1].laz+=tree[nod].laz;
        }
        tree[nod].laz=0;
    }
}
 
ll uptr(ll l,ll r,ll s,ll e,ll nod){
    //printf("uptr %lld %lld %lld %lld %lld\n",l,r,s,e,nod );
    lz(s,e,nod);
    if(e<l||r<s) return tree[nod].val;
    if(l<=s&&e<=r) {
        tree[nod].laz++;
        lz(s,e,nod);
        return tree[nod].val;
    }
    return tree[nod].val=max(uptr(l,r,s,(s+e)/2,nod*2),uptr(l,r,(s+e)/2+1,e,nod*2+1));
}
 
ll upt(ll idx,ll val,ll s,ll e,ll nod){
 
    lz(s,e,nod);
    //printf("upt %lld %lld %lld %lld %lld\n",idx,val,s,e,nod );
    if(idx<s||idx>e) return tree[nod].val;
    if(s==e) return  tree[nod].val=max(tree[nod].val,val);
    return tree[nod].val=max(upt(idx,val,s,(s+e)/2,nod*2),
    upt(idx,val,(s+e)/2+1,e,nod*2+1));
}
 
ll sol(ll l,ll r,ll s,ll e,ll nod){
 
    //printf("sol %lld %lld %lld %lld %lld\n",l,r,s,e,nod );
 
    lz(s,e,nod);
    if(e<l||r<s) return 0;
    if(l<=s&&e<=r) return tree[nod].val;
    return max(sol(l,r,s,(s+e)/2,nod*2),sol(l,r,(s+e)/2+1,e,nod*2+1));
}
 
bool sf(poi a,poi b){
    if(a.x==b.x&&a.y==b.y) return a.t<b.t;
    if(a.x==b.x) return a.y>b.y;
    return a.x>b.x;
}
 
ll nn=1e6;
ll mat(pii a,pii b){
    ll p=a.ff;
    a.ff=(a.ff+nn-p)%nn;
    a.ss=(a.ss+nn-p)%nn;
    b.ff=(b.ff+nn-p)%nn;
    b.ss=(b.ss+nn-p)%nn;
    //printf("%lld %lld %lld %lld\n",a.ff,a.ss,b.ff,b.ss);
    if(b.ff==0){
        if(b.ss<a.ss) return 0;
        else return 3;
    }
    if(b.ff>b.ss){
        if(b.ff<=a.ss) return 4;
        if(a.ss<=b.ss) return 3;
        else return 1;
    }
    if(a.ss<b.ff) return -1;
    if(b.ss<=a.ss) return 0;
    return 2;
}
 
int main(){
    ll t;
    scanf("%lld",&t);
    while(t--){
        ll i,j,k,l,m=6030,n;
        scanf("%lld",&n);
        for(i=1;i<=n;i++){
            scanf("%lld %lld",&arr[i].ff,&arr[i].ss);
            arr[i].ff--;
            arr[i].ss--;
        }
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                if(i!=j){
                    //printf("%lld %lld\n",i,j);
                    bet[i][j]=mat(arr[i],arr[j]);
                }
/*
        for(i=1;i<=n;i++){
            for(j=1;j<=n;j++)
                printf("%lld ",bet[i][j]);
            printf("\n");
        }
*/
        ll ret=0;
        for(i=1;i<=n;i++){
            ll ans=1;
            ll cnt=0;
            ll sz=(arr[i].ss-arr[i].ff+nn)%nn;
            for(j=0;j<=20000;j++) tree[j].val=tree[j].laz=0;
            for(j=1;j<=n;j++){
                if(bet[i][j]==3||bet[i][j]==4) ans++;
                if(bet[i][j]==2){
                    cnt++;
                    pp[cnt].t=2;
                    pp[cnt].x=(arr[i].ss-arr[j].ff+nn)%nn;
                    pp[cnt].y=(arr[j].ss-arr[i].ss+nn)%nn;
                    yval[cnt]=pp[cnt].y;
                }
                if(bet[i][j]==1){
                    cnt++;
                    pp[cnt].t=1;
                    pp[cnt].x=(arr[j].ss-arr[i].ff+nn)%nn;
                    pp[cnt].y=(arr[i].ff-arr[j].ff+nn)%nn;
                    //printf("qwer %lld %lld %lld %lld %lld %lld %lld\n",arr[i].ff,arr[i].ss,arr[j].ff,arr[j].ss,sz,pp[cnt].x,pp[cnt].y);
                    pp[cnt].x=sz-pp[cnt].x-1;
                    pp[cnt].y=nn-sz-pp[cnt].y-1;
                    yval[cnt]=pp[cnt].y;
                }
            }
 
            sort(yval+1,yval+1+cnt);
 
            sort(pp+1,pp+1+cnt,sf);
            ll mx=0;
            for(j=1;j<=cnt;j++){
                //printf("%lld %lld %lld %lld %lld %lld\n",i,j,pp[j].t,pp[j].x,pp[j].y,lower_bound(yval+1,yval+1+cnt,pp[j].y)-yval);
                pp[j].y=lower_bound(yval+1,yval+1+cnt,pp[j].y)-yval;
                if(pp[j].t==2){
                    uptr(0,pp[j].y-1,0,cnt,1);
                }
                else{
                    uptr(pp[j].y+1,cnt,0,cnt,1);
                    ll qw=sol(0,pp[j].y,0,cnt,1);
                    upt(pp[j].y,qw+1,0,cnt,1);
                }
            }
            ll vval=sol(0,cnt,0,cnt,1);
            ans+=vval;
            ret=max(ret,ans);
        }
 
        printf("%lld\n",ret);
    }
 
}