백준(BOJ) 3392 화성지도 ***

# 세그먼트 트리

변형된 세그먼트 트리가 사용된다.

새로운 알고리즘 이라기 보다는 변형된 방식에 대한 어느정도 이해가 필요할 것 같다.

 

#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <math.h>
#include <queue>
#include <set>
#include <map>
#include <list>
#include <utility>
#include <climits>
#include <functional>
#define MAX 30000
#define INF 987654321
#define MOD 1000000
#pragma warning(disable:4996)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<float, float> pf;

struct st
{
    int x,y1,y2,cnt;
};

bool cmp(st s1,st s2)
{return s1.x<s2.x;}

st arr[20005];
int n,a,b,c,d,pre=0,ans=0,mem[2][MAX*4];

void update(int cy1,int cy2, int ty1, int ty2, int node, int in)
{
    if(cy2<ty1||ty2<cy1)
        return ;
    if(ty1<=cy1&&cy2<=ty2)
        mem[1][node]+=in;
    else
    {
        int mid=(cy1+cy2)/2;
        update(cy1,mid,ty1,ty2,node*2,in);
        update(mid+1,cy2,ty1,ty2,node*2+1,in);
    }
    if(mem[1][node])
    {
        mem[0][node]=cy2-cy1+1;
    }
    else
        mem[0][node]=cy1==cy2?0:mem[0][node*2]+mem[0][node*2+1];
}

int main() {
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d%d%d%d",&a,&b,&c,&d);
        arr[i]={a,b,d-1,1};
        arr[i+n]={c,b,d-1,-1};
    }
    sort(arr,arr+2*n,cmp);
    for(int i=0;i<2*n;i++)
    {
        if(i>0)
        {
            int tmp = arr[i].x-pre;
            ans+=tmp*mem[0][1];
        }
        update(0,MAX,arr[i].y1,arr[i].y2,1,arr[i].cnt);
        pre=arr[i].x;
    }
    printf("%d",ans);
    return 0;
}