c - C中的象限查询给出分段错误

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 (leaf o'course)

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 次，我创建了一个 40 点而不是 4 点的新测试用例。我通过添加对输入操作的测试（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您需要考虑为什么要使用节点数组。只需要n（或者可能n + 1是节点，因为问题中的索引是基于 1 的，而不是像 C 中那样基于 0）。

输入01.txt

c - C中的象限查询给出分段错误

1 回答 1

输入01.txt

Related

Reference