Codeforces Round #439 (Div. 2) E. The Untended Antiquity

E. The Untended Antiquity

http://codeforces.com/contest/869/problem/E

div2이지만 무려 E번 문제다.

근데 E번 문제치고는 쉽게 풀 수 있었던 것 같다.

2D Fenwick + 적절한 random값으로 풀 수 있었다.

일단 문제는 직사각형 평면에 사각형을 그리고 지우는 것을 반복하다가 틈틈이 쿼리가 들어온다.

쿼리는 두점을 찍고 두점을 연결할 때 평면에 그린 사각형들의 모서리를 지나지 않고 연결할 수 있으면 Yes, 아니면 No를 출력해야 하는 문제였다.

일단 아래의 입력을 예제로 한번 더 설명하자면,

Examples

input

5 6 5
1 2 2 4 5
1 3 3 3 3
3 4 4 1 1
2 2 2 4 5
3 1 1 4 4

output

No
Yes

맨 위의 3개의 숫자는 n,m,q인데 n x m 사이즈의 평면과 q개의 쿼리가 주어진다는 뜻이다.

그 아래에는 q개의 쿼리가 주어진다.

각 쿼리는 한줄로 구성되고 각각을 t, x1, y1, x2, y2라고 하면,

t는 쿼리의 타입이다. 1이면 사각형을 추가하고 2면 사각형을 없애는 거고

없는 사각형을 없애라는 인풋은 안들어온다고 한다.

또 사각형이 추가될 땐 모서리가 겹치는 경우는 들어오지 않는다고 한다. (cross되지 않음)

x1,y1,x2,y2는 사각형 좌표를 의미한다. (대각선으로 양 끝점)

위의 예제를 그림으로 표현하면 아래와 같다.

나머지 제약조건이 궁금한건.. 그냥 코포 사이트가서 보시길...ㅋㅋ

다른 예제는 다음과 같다.

input

2500 2500 8
1 549 1279 1263 2189
1 303 795 1888 2432
1 2227 622 2418 1161
3 771 2492 1335 1433
1 2017 2100 2408 2160
3 48 60 798 729
1 347 708 1868 792
3 1940 2080 377 1546

output

No
Yes
No

그럼 이 문제는 어떻게 푸냐면,

사각형을 만들때 해당 사각형안의 모든 칸에 x값을 더한다.

그 다음 사각형이 만들어지면 그 사각형 안의 모든 칸에 y값을 더한다.

만약 y로 채운 사각형을 지울 때는 당연히 그 부분의 모든칸에 y값을 빼면 된다.

x가 1이고 y가 2인데 두 사각형이 서로 포개져있고, 두 사각형과 완전 동떨어진 곳에 3짜리 사각형이 만들어지면?

.....

그래서 그냥 랜덤값을 만들어서 간단하게 해결할 수 있다.

문제에서 쿼리의 최대 개수는 10만개라고 했으므로 사각형은 최대 10만개 만들어질 것이다.

그러므로 int범위 안에서 랜덤값을 만들어내도 사실 충분하다.

그럼 사각형 안의 값은 어떻게 멀쩡한(?) 시간안에 채울까? ㅋㅋㅋㅋㅋㅋㅋㅋㅋ

그건 2D 세그먼트 트리(쿼드트리)나 2D 펜윅트리로 해결하면 된다.

코드는 아래와 같다.

#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<pii,pii> piipii;
ll fen[2502][2502];
map<piipii,ll> mp;
int n,m;
void update(int x, int y, ll by) {
    for(int i=x; i<=n; i+=i&-i) {
        for(int j=y; j<=m; j+=j&-j) {
            fen[i][j] += by;
        }
    }
}
ll query(int x, int y) {
    ll ret = 0;
    for(int i=x; i; i-=i&-i) {
        for(int j=y; j; j-=j&-j) {
            ret += fen[i][j];
        }
    }
    return ret;
}
int main() {
    int q; scanf("%d%d%d", &n,&m,&q);
    for(int i=0; i<q; i++) {
        int t,x1,y1,x2,y2;
        scanf("%d%d%d%d%d",&t,&x1,&y1,&x2,&y2);
        if(t == 1) {
            int val = (rand()<<15) | rand();
            mp[piipii(pii(x1,y1),pii(x2,y2))] = val;
            update(x1,y1,val);
            update(x1,y2+1,-val);
            update(x2+1,y1,-val);
            update(x2+1,y2+1,val);
        } else if(t == 2) {
            int val = mp[piipii(pii(x1,y1),pii(x2,y2))];
            update(x1,y1,-val);
            update(x1,y2+1,val);
            update(x2+1,y1,val);
            update(x2+1,y2+1,-val);
        } else {
            if(query(x1,y1) == query(x2,y2)) puts("Yes");
            else puts("No");
        }
    }
    return 0;
}
 

.... 아무래도 난 글쓰는거에 소질이 없는듯 하다 ....

그럼 이만,