UVa 11402 Ошибка выполнения

Question

Я пытаюсь решить проблему 11402- Ahoy Pirates на судне UVa Online. Предполагается, что код должен построить дерево сегментов по определенной информации и выполнить операции обновления или запроса. Мой код 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, программа будет генерировать ошибку сегментации в случае огромных входов. Решение вышеуказанной проблемы могло проверить границы индекса перед доступом к массиву или сделать массив достаточно большим, чтобы обрабатывать все операции обновления переполнения.