UVa 11402 런타임 오류

Question

UVa Online Judge에서 11402- Ahoy Pirates 문제를 해결하려고합니다. 이 코드는 특정 정보에 세그먼트 트리를 작성하고 업데이트 또는 쿼리 작업을 수행합니다. 내 C++ 코드가 내 시스템에서 제대로 실행됩니다. 하지만 제출시 런타임 오류가 발생합니다. 배열 크기가 ~ 3000000 개 요소까지 올라갈 수 있기 때문에 이러한 큰 크기의 배열로 인해 런타임 오류가 발생할 수 있는지 궁금합니다. 어떤 아이디어?

#include <algorithm> 
#include <cctype> 
#include <cmath> 
#include <cstdio> 
#include <cstdlib> 
#include <cstring> 
#include <iostream> 
#include <map> 
#include <queue> 
#include <set> 
#include <sstream> 
#include <stack> 
#include <string> 
#include <vector> 

using namespace std; 
typedef long long ll; 

struct Node{ 
    char upd; 
    // 0 - Buccaneer pirates 
    // 1 - Barbary pirates 
    int p[2]; 
    Node(){ 
     p[0] = 0; 
    p[1] = 0; 
     upd = ' '; 
    } 
    void update(char cmd){ 
     if (cmd == 'I'){ 
      switch(upd){ 
       case ' ': upd = 'I';break; 
       case 'I': upd = ' ';break; 
       case 'E': upd = 'F';break; 
       case 'F': upd = 'E';break; 
      } 
     } 
     else if (cmd != ' '){ 
      upd = cmd; 
     } 
    } 
    void S(){ 
     int temp; 
     switch(upd){ 
      case 'I': temp=p[0]; p[0]=p[1]; p[1]=temp; break; 
      case 'E': p[1]+=p[0]; p[0]=0; break; 
      case 'F': p[0]+=p[1]; p[1]=0; break; 
     } 
     upd = ' '; 
    } 
}; 

Node tree[4028000]; 
char pirates[1024010]; 

void buildTree(int index, int i, int j){ 
    if (i>j) 
     return; 
    if (i==j){ 
     if (pirates[i] == '0'){ 
      tree[index].p[1] = 1; 
      tree[index].p[0] = 0; 
     } 
     else{ 
      tree[index].p[0] = 1; 
      tree[index].p[1] = 0; 
     } 
     tree[index].upd = ' '; 
     return; 
    } 
    int mid = (i+j)/2; 
    buildTree(2*index+1,i,mid); 
    buildTree(2*index+2,mid+1,j); 
    tree[index].p[0] = tree[2*index+1].p[0] + tree[2*index+2].p[0]; 
    tree[index].p[1] = tree[2*index+1].p[1] + tree[2*index+2].p[1]; 
    tree[index].upd = ' '; 
} 

void update(int index,int i,int j,int l,int r,char c){ 
    if (i == l && j == r){ 
     tree[index].update(c); 
    } 
    tree[2*index+1].update(tree[index].upd); 
    tree[2*index+2].update(tree[index].upd); 
    tree[index].S(); 
    if (i == l && j ==r) 
     return; 
    if (l>j || r<i || l > r) 
     return; 
    int mid = (i+j)/2; 
    update(2*index+1,i,mid,l,min(r,mid),c); 
    update(2*index+2,mid+1,j,max(l,mid+1),r,c); 
    tree[index].p[0] = tree[2*index+1].p[0] + tree[2*index+2].p[0]; 
    tree[index].p[1] = tree[2*index+1].p[1] + tree[2*index+2].p[1]; 
} 

int query(int index,int i,int j,int l,int r){ 
    if (l>j || r<i) 
     return 0; 
    tree[2*index+1].update(tree[index].upd); 
    tree[2*index+2].update(tree[index].upd); 
    tree[index].S(); 
    if (i == l && j == r){ 
     return tree[index].p[0]; 
    } 
    int mid = (i+j)/2; 
    int b1 = query(2*index+1,i,mid,l,min(mid,r)); 
    int b2 = query(2*index+2,mid+1,j,max(mid+1,l),r); 
    return b1+b2; 
} 

int main(void){ 
    int t; 
    scanf("%d",&t); 
    for(int z=0; z<t; z++){ 
     int m,len=0,T,q,querycnt=1; 
     char str[64]; 
     scanf("%d",&m); 
     for(int i=0; i<m; i++){ 
      scanf("%d %s",&T,str); 
      for(int j=0; j<T; j++){ 
       int length = strlen(str); 
       for(int k=0; k<length; k++){ 
        pirates[len] = str[k]; 
        len++; 
       } 
      } 
     } 
     buildTree(0,0,len-1); 
    scanf("%d",&q); 
     printf("Case %d:\n",z+1); 
     for(int i=0; i<q; i++){ 
      char cmd; 
      int l,r; 
     scanf(" %c %d %d", &cmd, &l, &r); 
      if (cmd == 'S'){ 
       int ans = query(0,0,len-1,l,r); 
       printf("Q%d: %d\n",querycnt++,ans); 
      } 
      else{ 
       update(0,0,len-1,l,r,cmd); 
      } 
     } 
    } 
    return 0; 
} 

Answer 1

해결책의 문제점은 다음 두 문장 기재된 내용에 모두

tree[2*index+1].update(tree[index].upd); 
tree[2*index+2].update(tree[index].upd); 

에 놓여 어레이 트리 인덱스가 2 * (2 * N + 1) (개까지 도달 할 오버플로 연산) 여기서 N은 입력의 최대 크기입니다. 위의 질문에서 N = 1024000입니다. 배열 트리의 크기가 4 * N보다 작기 때문에 프로그램은 거대한 입력의 경우 세그먼트 오류를 ​​생성합니다. 위의 문제에 대한 해결책은 배열에 액세스하기 전에 색인의 경계를 검사하거나 모든 오버플로 업데이트 작업을 처리 할만큼 배열을 충분히 크게 만들 수 있습니다.