글 읽기 - 세그먼트트리 시간초과

kdhsong 7년 전 0

맞게짠거같은데

시간초과가뜨는데 이유를알수있을까요

펜윅트리로 짜야하나요 ?ㅠ

#include <stdio.h>
#define MIN(a,b)    a<b?a:b
#define MAX(a,b)    a>b?a:b
  
int n,m,minArr[3*100005],maxArr[3*100005],arr[100005];
  
  
int minInit(int s,int e,int index){
    if(s > e)    return 2100000000;
    if(s == e)      return minArr[index] = arr[s];
    return minArr[index] = MIN(minInit(s, (s+e)/2, index*2), minInit((s+e)/2+1,e, index*2+1));
}
  
int maxInit(int s,int e,int index){
    if(s > e)        return 0;
    if(s == e)      return maxArr[index] = arr[s];
    return maxArr[index] = MAX(maxInit(s, (s+e)/2, index*2), maxInit((s+e)/2+1,e, index*2+1));
}
  
  
int minFind(int s,int e,int pa,int pb,int index){
      
    if(s > pb || e < pa)        return 2100000000;
    if(pa <= s && pb >= e)        return minArr[index];
     
   
    return MIN(minFind(s,(s+e)/2, pa, pb, index*2), minFind((s+e)/2+1, e, pa, pb, index*2+1));
}
  
int maxFind(int s,int e,int l,int r,int index){
     
    if(s > r || e < l)        return -1;
    if(l <= s && r >= e)      return maxArr[index];
      
    return MAX(maxFind(s,(s+e)/2, l, r, index*2), maxFind((s+e)/2+1, e, l, r, index*2+1));
}
  
int main(){
    scanf("%d %d",&n,&m);
  
    for(int i = 0; i < n; i++){
        scanf("%d",&arr[i]);
    }
      
    minInit(0,n-1,1);
    maxInit(0,n-1,1);
 
    for(int i = 0; i < m; i++){
        int a,b;
        scanf("%d %d",&a,&b);
        a--,b--;
        printf("%d %d\n",minFind(0,n-1,a,b,1),maxFind(0,n-1,a,b,1));
    }
}

plzrun 7년 전 1

네 맞게 짜셨는데요,

제가 문제를 보지 않았는데 좀 아닌거 같은 부분이 있어서 그 부분만 수정했더니 맞았습니다.

먼저 MIN, MAX를 매크로로 쓰셨는데,

여기서 매크로 쓰시면 주의해야할 점이 절대 함수값을 파라미터로 넘겨주면 안됩니다.

할 때마다 호출하거든요. (그니까 함수의 값이 넘어가서 min, max를 계산하는게 아니라 min, max한번 할때마다 함수를 계속 호출하기 때문에 min max 매크로는 지양하는 편이 좋습니다.)

그래서 원래 std::min, std::max를 썼습니다.

그리고 부분합이 아닌문제에 펜윅을 적용할 수 있는지는 모르겠습니다.

아마 안되는게 아닌가.. 로 생각됩니다.

#include <stdio.h>
#include <algorithm>
using namespace std;
   
int n,m,minArr[3*100005],maxArr[3*100005],arr[100005];
   
   
int minInit(int s,int e,int index){
    if(s > e)    return 2100000000;
    if(s == e)      return minArr[index] = arr[s];
    return minArr[index] = min(minInit(s, (s+e)/2, index*2), minInit((s+e)/2+1,e, index*2+1));
}
   
int maxInit(int s,int e,int index){
    if(s > e)        return 0;
    if(s == e)      return maxArr[index] = arr[s];
    return maxArr[index] = max(maxInit(s, (s+e)/2, index*2), maxInit((s+e)/2+1,e, index*2+1));
}
   
   
int minFind(int s,int e,int pa,int pb,int index){
       
    if(s > pb || e < pa)        return 2100000000;
    if(pa <= s && pb >= e)        return minArr[index];
      
    
    return min(minFind(s,(s+e)/2, pa, pb, index*2), minFind((s+e)/2+1, e, pa, pb, index*2+1));
}
   
int maxFind(int s,int e,int l,int r,int index){
      
    if(s > r || e < l)        return -1;
    if(l <= s && r >= e)      return maxArr[index];
       
    return max(maxFind(s,(s+e)/2, l, r, index*2), maxFind((s+e)/2+1, e, l, r, index*2+1));
}
   
int main(){
    scanf("%d %d",&n,&m);
   
    for(int i = 0; i < n; i++){
        scanf("%d",&arr[i]);
    }
       
    minInit(0,n-1,1);
    maxInit(0,n-1,1);
  
    for(int i = 0; i < m; i++){
        int a,b;
        scanf("%d %d",&a,&b);
        a--,b--;
        printf("%d %d\n",minFind(0,n-1,a,b,1),maxFind(0,n-1,a,b,1));
    }
}

plzrun 7년 전 0

그리고 배열 크기 3배만 곱해도 맞았다고 뜨네요?

전에 종만북에서 4배는 해야한다고 배웠었는데.. 잘 모르겠네용

계산해보니까 26만 3천정도 잡으면 되긴하는데..

아.. 이게 10만이라서 그렇구나.. 2^N에 가까워진 경우에는 4배를 해야겠네요 ! :ㅇ

ㅎㅎ

rhs0266 7년 전 0

펜윅트리 두개 쓰면 세그먼트트리를 흉내낼 수 있습니다.

펜윅은 2N 만 잡아도 되는데, 세그먼트도 마찬가지일 것 같네여.

plzrun 7년 전 0

@rhs0266

ㅇㅇㅏ 그렇군요 ㅎ

가만히 생각해보니 펜윅으로 최대, 최소 구하는 것도 그냥 부분합이 아닌 그 구간의 최대 최소만 가지고 있으면 되니까 가능할거라고 생각이 되는데, 왜 2개를 써야하는 건가요??

그리고 공간의 경우에는 세그트리가 4N이 맞다고 생각이 드는데요. 펜윅이 세그보다 공간이 반만 필요하잖아요? 아닌가요??

kdhsong 7년 전 0

너무너무감사드립니다!!!

rhs0266 7년 전 0

아 부분합에 대한 말이었습니당

흠... 동적으로 결국 단말노드에는 (i,i) 만 있고 위로 올라가면서 합치면 될 것 같았어요

펜윅이랑 노드가 관할하는 구간의 정의가 비슷하니까..? 정확한 건 아니네요 ㅜㅜ

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

문제

문제

출처

ICPC

세그먼트트리 시간초과

kdhsong 7년 전 0

plzrun 7년 전 1

plzrun 7년 전 0

rhs0266 7년 전 0

plzrun 7년 전 0

kdhsong 7년 전 0

rhs0266 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말