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

有关问题请访问问题我几乎已经解决了使用具有延迟传播的分段树的 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("%dn",&q);
for(i=0;i<q;i++){
    scanf("%c %d %dn",&k,&x,&y);
    if(k=='C'){
        int *temp;
        temp=count_nums(nodes,2*n-1,x-1,y-1);
        printf("%d %d %d %dn",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通过遍历插入元素，直到找到节点的索引=max=min（叶子o'course）

count_nums 返回提到的段的计数数组

change_x_range 沿 x 轴反映所选范围，并更新计数直到根

change_y_range沿 y 轴反映所选范围，并更新计数直到根

我在你的代码中添加了一个函数：

#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 pointsn");
    printf("Points: %dn", 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 %dn", i);
        printf("%d: %d %dn", 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("%dn",&q) != 1)
        err_exit("WTF? Failed to read number of queriesn", q);
    printf("Queries: %dn", n);
    for(i=0;i<q;i++)
    {
        if (scanf("%c %d %dn",&k,&x,&y) != 3)
            err_exit("WTF? Failed to read query %dn", i);
        printf("%d: %c %d %dn", i, k, x, y);
        if(k=='C')
        {
            int *temp;
            temp=count_nums(nodes,2*n-1,x-1,y-1);
            printf("%d %d %d %dn",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

输入01.txt

相关内容

最新更新

热门标签：