c - C の Quadrant クエリでセグメンテーション違反が発生する

Question

質問については、QUESTION を参照してください。遅延伝播によるセグメントツリーを使用して、Interviewstreet の象限クエリの問題をほぼ解決しましたが、セグメンテーションエラーが発生しています。そのため、コードをレビューして助けてくれる人が必要です。

これが私のコードです

#include<stdio.h>

struct node {
int count[4],min,max,quadrant;
};

int count[4]={0};

void set_maxmin(struct node nodes[],int n,int index,int min,int max){
int mid=(min+max)/2;
nodes[index].min=min;
nodes[index].max=max;
nodes[index].count[0]=0;
nodes[index].count[1]=0;
nodes[index].count[2]=0;
nodes[index].count[3]=0;
if(max==min+1){
    set_maxmin(nodes,n,2*index+1,min,min);
    set_maxmin(nodes,n,2*index+2,max,max);
} else if(max>min+1){
    set_maxmin(nodes,n,2*index+1,min,mid);
    set_maxmin(nodes,n,2*index+2,mid+1,max);
}
}

void tree_insert(struct node nodes[],int n,int index,int quad){
int i=0;
while(1){
    if(index<(nodes[i].max+nodes[i].min)/2){
        if(2*i+1<n) i=2*i+1;
        else break;
    } else if(index>(nodes[i].max+nodes[i].min)/2){
        if(2*i+2<n) i=2*i+2;
        else break;
    } else if(index==nodes[i].max && index!=nodes[i].min)
        i=2*i+2;
    else if(index!=nodes[i].max && index==nodes[i].min)
        i=2*i+1;
    else if(index!=nodes[i].max && index!=nodes[i].min)
        i=2*i+1;
    else
        break;
}
nodes[i].quadrant=quad;

nodes[i].count[0]=0;
nodes[i].count[1]=0;
nodes[i].count[2]=0;
nodes[i].count[3]=0;
nodes[i].count[quad-1]++;
while(i!=0){
    i=(i-1)/2;
    nodes[i].count[quad-1]++;
}
}

void change_x(struct node nodes[],int n,int index){
int i=0,quad;
while(1){
    if(index<(nodes[i].max+nodes[i].min)/2){
        if(2*i+1<n) i=2*i+1;
        else break;
    } else if(index>(nodes[i].max+nodes[i].min)/2){
        if(2*i+2<n) i=2*i+2;
        else break;
    } else if(index==nodes[i].max && index!=nodes[i].min)
        i=2*i+2;
    else if(index!=nodes[i].max && index==nodes[i].min)
        i=2*i+1;
    else if(index!=nodes[i].max && index!=nodes[i].min)
        i=2*i+1;
    else
        break;
}
quad=nodes[i].quadrant;
nodes[i].count[quad-1]--;
nodes[i].count[5-quad-1]++;
nodes[i].quadrant=5-nodes[i].quadrant;
while(i!=0){
    i=(i-1)/2;
    nodes[i].count[quad-1]--;
    nodes[i].count[5-quad-1]++;
}
}

void change_x_range(struct node nodes[],int n,int i,int j){
int k;
for(k=i;k<=j;k++)
    change_x(nodes,2*n-1,k);
}

void change_y(struct node nodes[],int n,int index){
int i=0,quad,quad2;
while(1){
    if(index<(nodes[i].max+nodes[i].min)/2){
        if(2*i+1<n) i=2*i+1;
        else break;
    } else if(index>(nodes[i].max+nodes[i].min)/2){
        if(2*i+2<n) i=2*i+2;
        else break;
    } else if(index==nodes[i].max && index!=nodes[i].min)
        i=2*i+2;
    else if(index!=nodes[i].max && index==nodes[i].min)
        i=2*i+1;
    else if(index!=nodes[i].max && index!=nodes[i].min)
        i=2*i+1;
    else
        break;
}
quad=nodes[i].quadrant;
nodes[i].count[quad-1]--;
if(quad==1 || quad==3)
    nodes[i].quadrant++;
else
    nodes[i].quadrant--;
quad2=nodes[i].quadrant;
nodes[i].count[quad2-1]++;
while(i!=0){
    i=(i-1)/2;
    nodes[i].count[quad-1]--;
    nodes[i].count[quad2-1]++;
}
}

void change_y_range(struct node nodes[],int n,int i,int j){
int k;
for(k=i;k<=j;k++)
    change_y(nodes,2*n-1,k);
}

int * count_nums(struct node nodes[],int n,int min,int max){
int i=0,*count1,*count2,*count3,k,mid;
while(1){
    mid=(nodes[i].min+nodes[i].max)/2;
    if(min==nodes[i].min && max==nodes[i].max){
        return nodes[i].count;
    } else if(min==nodes[i].min && max!=nodes[i].max){
        if(max>nodes[i].max){
            count1=nodes[i].count;
            count2=count_nums(nodes,n,nodes[i].max+1,max);
            for(k=0;k<4;k++)
                count[k]=count1[k]+count2[k];
            return count;
        } else if(2*i+1<n) i=2*i+1;
        else break;
    } else if(min!=nodes[i].min && max==nodes[i].max){
        if(min<nodes[i].min){
            count1=count_nums(nodes,n,min,nodes[i].min-1);
            count2=nodes[i].count;
            for(k=0;k<4;k++)
                count[k]=count1[k]+count2[k];
            return count;
        } else if(2*i+2<n) i=2*i+2;
        else break;
    } else if(min<=mid && max<=mid){
        if(2*i+1<n) i=2*i+1;
        else break;
    } else if(min>=mid && max>=mid){
        if(2*i+2<n) i=2*i+2;
        else break;
    } else {
        count1=count_nums(nodes,n,min,mid);
        count2=count_nums(nodes,n,mid+1,max);
        for(k=0;k<4;k++)
            count[k]=count1[k]+count2[k];
        return count;
    }
}
return count;
}

int main(){
int n,quadrant,x,y,i,q;
char k;
scanf("%d",&n);
struct node nodes[2*n-1];
set_maxmin(nodes,2*n+1,0,0,n-1);
for(i=0;i<n;i++){
    scanf("%d %d",&x,&y);
    if(x>0 && y>0)
        tree_insert(nodes,2*n+1,i,1);
    else if(x<0 && y>0)
        tree_insert(nodes,2*n+1,i,2);
    else if(x<0 && y<0)
        tree_insert(nodes,2*n+1,i,3);
    else
        tree_insert(nodes,2*n+1,i,4);
}
scanf("%d\n",&q);
for(i=0;i<q;i++){
    scanf("%c %d %d\n",&k,&x,&y);
    if(k=='C'){
        int *temp;
        temp=count_nums(nodes,2*n-1,x-1,y-1);
        printf("%d %d %d %d\n",temp[0],temp[1],temp[2],temp[3]);
    } else if(k=='X'){
        change_x_range(nodes,2*n-1,x-1,y-1);
    } else if(k=='Y'){
        change_y_range(nodes,2*n-1,x-1,y-1);
    }
}
return 0;
}

セグメントツリーを実装する前に、私は 8/11 テストケースを正しく取得しました。

誰かこれで私を助けてください

一生懸命理解しようとしなくてもいいように、私のコードを説明しようと思いました

set_maxmin は、すべてのノードの最大値と最小値を 2*n-1 の数で設定します

Tree_insert は、ノード (葉のコース) の index=max=min が見つかるまでトラバースして要素を挿入します。

count_nums は、言及されたセグメントのカウント配列を返します

change_x_range は、x 軸に沿って選択された範囲を反映し、ルートまでのカウントを更新します

change_y_range は、選択した範囲を y 軸に沿って反映し、ルートまでのカウントを更新します

score 1 · Accepted Answer

コードに関数を追加しました：

#include <stdarg.h>
#include <stdlib.h>

static void err_exit(const char *fmt, ...)
{
    va_list args;
    va_start(args, fmt);
    vfprintf(stderr, fmt, args);
    va_end(args);
    exit(1);
}

テスト入力ファイルを調整し、同じ 4 ポイントを 10 回使用して、4 ではなく 40 ポイントの新しいテストケースを作成しました。入力操作にテストを追加して進行状況を監視しました (err_exit()問題の報告に使用)。

int main(void)
{
    int n,x,y,i,q;
    char k;
    if (scanf("%d",&n) != 1)
        err_exit("WTF? Failed to read number of points\n");
    printf("Points: %d\n", n);
    struct node nodes[2*n-1];
    set_maxmin(nodes,2*n+1,0,0,n-1);
    for(i=0;i<n;i++)
    {
        if (scanf("%d %d",&x,&y) != 2)
            err_exit("WTF? Failed to read point %d\n", i);
        printf("%d: %d %d\n", i, x, y);
        if(x>0 && y>0)
            tree_insert(nodes,2*n+1,i,1);
        else if(x<0 && y>0)
            tree_insert(nodes,2*n+1,i,2);
        else if(x<0 && y<0)
            tree_insert(nodes,2*n+1,i,3);
        else
            tree_insert(nodes,2*n+1,i,4);
    }
    if (scanf("%d\n",&q) != 1)
        err_exit("WTF? Failed to read number of queries\n", q);
    printf("Queries: %d\n", n);
    for(i=0;i<q;i++)
    {
        if (scanf("%c %d %d\n",&k,&x,&y) != 3)
            err_exit("WTF? Failed to read query %d\n", i);
        printf("%d: %c %d %d\n", i, k, x, y);
        if(k=='C')
        {
            int *temp;
            temp=count_nums(nodes,2*n-1,x-1,y-1);
            printf("%d %d %d %d\n",temp[0],temp[1],temp[2],temp[3]);
        }
        else if(k=='X')
            change_x_range(nodes,2*n-1,x-1,y-1);
        else if(k=='Y')
            change_y_range(nodes,2*n-1,x-1,y-1);
        else
            err_exit("WTF? %c?\n", k);
    }
    return 0;
}

コード ( ./tldr < input01.txt) を実行すると、以下が生成されます。

Points: 40
0: 1 1
1: -1 1
2: -1 -1
3: 1 -1
4: 1 1
5: -1 1
6: -1 -1
7: 1 -1
8: 1 1
9: -1 1
10: -1 -1
Queries: 11
0: - 1 1
WTF? -?

何が起こっているかというと、配列の境界をオーバーランnodesし、変数を上書きしているということですn。

2*n-1ノードの配列を使用している理由を考慮する必要があります。(問題のインデックスは 1 ベースであり、C のように 0 ベースではないため、nおそらくノード)が必要なだけです。n + 1

input01.txt

c - C の Quadrant クエリでセグメンテーション違反が発生する

1 に答える 1

input01.txt

Related

Reference