UVa OJ 1455 - Kingdom

문제 링크

\(1\leq{N}\leq{10^5}\)

\(1\leq{M}\leq{2\cdot{10^5}}\)

\(1\leq{x,y}\leq{10^6}\)

2차원 좌표평면상에 도시의 개수 N이 주어지고 N개의 줄에 각 도시의 x,y 좌표가 주어진다.

그리고 쿼리의 수 M이 주어지는데 각 쿼리의 동작은 두가지다.

road a b : 도시 a와 b 사이에 직선 도로를 이어 하나의 state 로 만든다.

line c : x축에 평행하게 y = c 직선을 그어 한 도로라도 이 직선에 교차되는 state 들의 수와

그 state 들의 도시 수의 합을 출력한다.

c는 무조건 1.5, 5.5 등 ~~.5 의 형태이며 도로들은 서로 교차하지 않는다. \(0\lt{c}\lt{10^6}\)

서로다른 state 가 도로에 의해 하나의 state 로 묶이는 것을 서로 다른 두 set이 합쳐져 하나의 set을

이루는 것과 닮았다. 우선 유니온 파인드로 각 state에 속한 도시의 수를 나타낼 수가 있다.

그리고 line c 에 의해 계산이 고려되어야 하는 state 들의 핵심 조건은 무엇일까? 

도로로 연결되어있는 state 를 y축에 정사영 시킨다고 생각해보자. 아니, y축에 서서 x축에 평행하게 

바라본다고 생각해보자. 그러면 특정 state의 도시들중 가장 y값이 큰 도시부터 가장 y값이 작은 도시사이엔

모두 도로가 보일 것이고, 그 사이에 line 을 그으면 그 state는 계산이 고려되어야 할 것이다.

즉 각각의 state의 가장작은 y값과 가장큰 y값을 저장하고있어야한다. 그리고 두 state A, B를 합쳐

새로운 state C를 만든다고 할 때

miny[C] = min(miny[A],miny[B]) 이며

maxy[C] = max(maxy[A],maxy[B]) 가 됨을 쉽게 알 수가 있다.

그러면 과연 이제 line c 에 대해 고려되어야할 모든 state의 수와 이 state 들에 포함된 도시의 수의 합을

어떻게 빠른 시간안에 구할 것인가만 해결되면 된다.

조금만 생각해 보면 x좌표는 결국 필요가 없다는 것을 알게된다. 그러면 y좌표를 인덱스로 하는 세그먼트 트리를

두개 생각해 보자. 1번 세그트리는 구간에 line을 쏠 때 만나게 되는 state의 수를 저장하며, 2번 세그트리는

구간에 line을 쏠 때 만나게 되는 state 들의 도시의 수의 합을 저장한다.

그럼 두 state A, B가 합쳐질 때에는 A와 B 각각에 대한 정보를 두 세그트리에서 삭제 업데이트하고

A, B를 merge 하고 miny, maxy 를 새로 갱신해준뒤 세그트리를 추가 업데이트 하면 될 것이다.

하지만 이렇게 되면 구간 업데이트가 필요하다는 뜻이 된다. 왜냐하면 miny~maxy 사이에 line 을 쏠 때

해당 state가 모두 계산의 대상이 되어야하기 때문이다. 그런데 잘 보면 query 는 index가 c일 때만 딱 구하면

된다. 그럼 굳이 lazy propagation을 사용할 것 없이 펜윅트리의 range update, point query 로 해결이 가능하다. 

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;
const int INF = 0x3c3c3c3c;
const long long INFL = 0x3c3c3c3c3c3c3c3c;
 
int T;
int N,M;
int par[100003];
int size[100003];
int t1[1000003]; // 노드수
int t2[1000003]; // states 수
int ymin[100003];
int ymax[100003];
 
void update(int x, int v, int *t){
    while(x < 100003){
        t[x] += v;
        x += x & -x;
    }
}
int query(int x, int *t){
    int ret = 0;
    while(x > 0){
        ret += t[x];
        x -= x & -x;
    }
    return ret;
}
void addrmv(int u, int addrm){
    update(ymin[u],addrm,t1);
    update(ymax[u],-addrm,t1);
    update(ymin[u],size[u]*addrm,t2);
    update(ymax[u],-size[u]*addrm,t2);
}
int find(int u){
    return u == par[u] ? u : par[u] = find(par[u]);
}
void merge(int u , int v){
    u = find(u), v = find(v);
    if(u==v) return;
    addrmv(u,-1);
    addrmv(v,-1);
    par[u] = v;
    size[v] += size[u];
    ymin[v] = min(ymin[v], ymin[u]);
    ymax[v] = max(ymax[v], ymax[u]);
    addrmv(v,1);
}
int main() {
    scanf("%d",&T);
    while(T--){
        memset(t1,0,sizeof(t1));
        memset(t2,0,sizeof(t2));
        for(int i = 0 ; i < 100003; i++) par[i] = i, size[i] = 1;
 
        set<int> st;
        scanf("%d",&N);
        for(int i = 0 ; i < N; i++){
            int yy;
            scanf("%*d%d",&yy);
            ymin[i] = ymax[i] = yy + 1;
        }
 
        scanf("%d",&M);
        for(int i = 0 ; i < M; i++){
            char str[10];
            scanf("%s",str);
            if(str[0] == 'r'){
                int a, b;
                scanf("%d%d",&a,&b);
                merge(a, b);
            }
            else if(str[0] == 'l'){
                double af;
                scanf("%lf",&af);
                int a = (int)(af - 0.5) + 1;
                int a1 = query(a, t1);
                int a2 = query(a, t2);
                printf("%d %d\n",a1, a2);
            }
        }
    }
    return 0;
}