글 읽기 - 세그먼트 트리 관련해서 질문드립니다. ㅠ

smu201111192 6년 전 0

요문제를 세그먼트 트리를 이용해서 풀어봤는데요.

세그먼트 만들 때 데이터크기에 4배 정도로 트리 공간을 잡으면 되는걸로 알고있습니다.

근데 요문제는 4배~6배로 잡으면 틀리고 7배이상으로 잡아줘야 맞습니다.

왜그럴까요? ㅠ

#include <iostream>
#include <cstdio>
#include <cassert>
#include <string>
#include <sstream>
#include <algorithm>
#include <set>
#include <numeric>
#include <cmath>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <cstring>
#include <queue>
#include <numeric>
#include <iomanip>
#define ll long long
#define open 1
#define close 0
using namespace std;
const ll MAXN=1200005;
struct Rect{
    ll x1,y1,x2,y2;
}r[MAXN];
int cov[MAXN*4],tree[MAXN*4];  //----->7배 안 하면 틀립니다. ㅠ
vector<pair<ll,pair<ll,ll> > > event;
void update(ll pos,ll st,ll ed,ll l,ll r,ll v){  //각노드는 st~ed+1 사이의 구간을 관리함
    if(st > r || ed < l )return;
    if(st >= l && ed <= r){
        cov[pos]+=v;
        if(cov[pos]>=1)tree[pos]=(ed+1-st);  //만약에 좌표압축을 했다면 len(ed+1)-len(st)가 됨
        else tree[pos]=tree[pos*2]+tree[pos*2+1];
        return;
    }
    update(pos*2,st,(st+ed)/2,l,r,v);
    update(pos*2+1,(st+ed)/2+1,ed,l,r,v);
    
    if(cov[pos]>=1)tree[pos]=(ed+1-st);
    else tree[pos]=tree[pos*2]+tree[pos*2+1];
    
    return;
}
int main(){
    
    int T; scanf("%d",&T);
    while(T--){
        event.clear();
        int n; scanf("%d",&n);
        ll mx=0;
        for(ll i=1;i<=n;i++){
            scanf("%lld %lld %lld %lld",&r[i].x1, & r[i].y1, &r[i].x2 , &r[i].y2);
            r[i].x1++, r[i].x2++ ,r[i].y1++ , r[i].y2++;
            //만약에 0부터 입력받는다면 조심하자 +1 해주자 세그트리는 노드를 1부터 쓰니말이다
            //좌표압축을한다면 상관이없음 0->1로 매핑시켜주면 됨
            if(r[i].x1 > r[i].x2)swap(r[i].x1 , r[i].x2);
            if(r[i].y1 > r[i].y2)swap(r[i].y1 , r[i].y2);
            mx=max(r[i].y2+1,mx);
            assert(r[i].x2<=1000001);
            assert(r[i].y2<=1000001);
            event.push_back({r[i].x1,{open,i}});
            event.push_back({r[i].x2,{close,i}});
        }
        sort(event.begin(),event.end());
        ll before=0;
        ll ans=0;
        for(ll i=0;i<event.size();i++){
            ll x = event[i].first;
            ll type = event[i].second.first;
            ll idx=event[i].second.second;
            ll y1=r[idx].y1;
            ll y2=r[idx].y2;
            if(type == open){
                ans+=(x-before)*tree[1];
                update(1,1,1200000,y1,y2-1,1); //오른쪽 좌표는 범위보다 좀더 크게 압축하면 직사각형 사이즈가 커지니 조심
            }
            if(type == close){
                ans+=(x-before)*tree[1];
                update(1,1,1200000,y1,y2-1,-1);
            }
            before=x;
        }
        cout<<ans<<"\n";
        //      printf("%lld\n",ans);
    }
    
    return 0;
}

yukariko 6년 전 0

간단하게 아래 코드로 테스트하니 pos의 값이 최대 4 N 근처가 나오네요

거기에 코드의 pos * 2를 인덱스로 접근하니 8N의 범위까지 가게 될것 같습니다.

#include <bits/stdc++.h>

using namespace std;

int m;

void update(int pos, int st, int ed)
{
	m = max(m, pos);
	if(st >= ed)
		return;
	
	update(pos * 2, st, (st + ed) / 2);
	update(pos * 2 + 1, (st +ed) / 2 +1 , ed);
}

int main()
{
	update(1,1,1200000);
	printf("%d", m);
	return 0;
}

yukariko 6년 전 1

코드를 이렇게 하니 4N으로도 풀리긴하네요

#include <iostream>
#include <cstdio>
#include <cassert>
#include <string>
#include <sstream>
#include <algorithm>
#include <set>
#include <numeric>
#include <cmath>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <cstring>
#include <queue>
#include <numeric>
#include <iomanip>
#define ll long long
#define open 1
#define close 0
using namespace std;
const ll MAXN=1200005;
struct Rect{
    ll x1,y1,x2,y2;
}r[MAXN];
int cov[MAXN*4],tree[MAXN*4];  //----->7배 안 하면 틀립니다. ㅠ
vector<pair<ll,pair<ll,ll> > > event;
void update(ll pos,ll st,ll ed,ll l,ll r,ll v){  //각노드는 st~ed+1 사이의 구간을 관리함
    if(st > r || ed < l || st > ed)return;
    if(st >= l && ed <= r){
        cov[pos]+=v;
        if(cov[pos]>=1)tree[pos]=(ed+1-st);  //만약에 좌표압축을 했다면 len(ed+1)-len(st)가 됨
        else tree[pos]=tree[pos*2]+tree[pos*2+1];
        return;
    }
    update(pos*2,st,(st+ed)/2,l,r,v);
    update(pos*2+1,(st+ed)/2+1,ed,l,r,v);
    
    if(cov[pos]>=1)tree[pos]=(ed+1-st);
    else tree[pos]=tree[pos*2]+tree[pos*2+1];
    
    return;
}
int main(){
    
    int T; scanf("%d",&T);
    while(T--){
        event.clear();
        int n; scanf("%d",&n);
        ll mx=0;
        for(ll i=1;i<=n;i++){
            scanf("%lld %lld %lld %lld",&r[i].x1, & r[i].y1, &r[i].x2 , &r[i].y2);
            r[i].x1++, r[i].x2++ ,r[i].y1++ , r[i].y2++;
            //만약에 0부터 입력받는다면 조심하자 +1 해주자 세그트리는 노드를 1부터 쓰니말이다
            //좌표압축을한다면 상관이없음 0->1로 매핑시켜주면 됨
            if(r[i].x1 > r[i].x2)swap(r[i].x1 , r[i].x2);
            if(r[i].y1 > r[i].y2)swap(r[i].y1 , r[i].y2);
            mx=max(r[i].y2+1,mx);
            assert(r[i].x2<=1000001);
            assert(r[i].y2<=1000001);
            event.push_back({r[i].x1,{open,i}});
            event.push_back({r[i].x2,{close,i}});
        }
        sort(event.begin(),event.end());
        ll before=0;
        ll ans=0;
        for(ll i=0;i<event.size();i++){
            ll x = event[i].first;
            ll type = event[i].second.first;
            ll idx=event[i].second.second;
            ll y1=r[idx].y1;
            ll y2=r[idx].y2;
            if(type == open){
                ans+=(x-before)*tree[1];
                update(1,1,1000005,y1,y2-1,1); //오른쪽 좌표는 범위보다 좀더 크게 압축하면 직사각형 사이즈가 커지니 조심
            }
            if(type == close){
                ans+=(x-before)*tree[1];
                update(1,1,1000005,y1,y2-1,-1);
            }
            before=x;
        }
        cout<<ans<<"\n";
        //      printf("%lld\n",ans);
    }
    
    return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

세그먼트 트리 관련해서 질문드립니다. ㅠ

smu201111192 6년 전 0

yukariko 6년 전 0

yukariko 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말