Сегмент неисправности в некоторых особых неизвестных случаях, сводящих меня с ума

Я отлаживал весь день, и я действительно полностью потерян. Помогите! Я тестировал множество случаев локально в Visual Studio. Работает нормально. Но в системе онлайн-судейства нашей школы есть несколько случаев, сообщающих RE (код выхода 6), что означает проблему с ошибкой сегмента. Я действительно не знаю, что произошло в этих случаях со всеми случайными случаями, работающими совершенно локально. Я проверил список возможных проблем, которые могут вызвать ошибку сегмента. Я просто не могу разобраться, поэтому, пожалуйста, помогите. Это действительно сводит меня с ума.

Замечания:
Это дерьмо. В структуре данных намного больше кода, но все остальное работает нормально, поэтому я попытался извлечь весь соответствующий код. Я уверен, что treapNode* treap::deleteNode(valueType value) Функция запускает проблему сбоя сегмента. Если вы заметили что-то пропущенное, пожалуйста, дайте мне знать.

Мне очень жаль, что это выглядит так долго … какой-нибудь совет по поводу моего кодирования? Я действительно оценил бы это!

——————-Обновить———————-

хорошо, я положу весь свой код здесь, чтобы вам было легче Кстати, у меня нет доступа к UNIX-подобной платформе …

——————-обновить формат ввода —————-

пример:

5         //the total number of the following operations
0 1 2     //this operation '0' means inserting '1' and '2' seperately
0 2 3     //while this means inserting '2' in x, '3' in y;
1 2 5     //skip operation '1'
2 0 1     //this operation '2' means delete the smallest number in x, and second small number in y
0 4 1

oj обещает не вставлять номер, который уже существует, и не удалять ранг, который не существует.

#include <cstdio>
#include <ctime>
#include <cstdlib>
using namespace std;

typedef unsigned long long valueType;

struct treapNode
{
valueType value;
int prior;
int lChildNum;
int rChildNum;
treapNode* lChild;
treapNode* rChild;
treapNode* parent;
treapNode(valueType value, int randPrior)
:value(value), prior(randPrior), lChildNum(0), rChildNum(0), lChild(NULL), rChild(NULL), parent(NULL) {}
};

class treap
{
public:
treap(valueType value);
treapNode* searchRank(treapNode* baseNode, valueType rank);
treapNode* insertNode(valueType value);
void deleteRank(valueType rank);
void printTreap(treapNode* tempRoot);
treapNode* root;
private:
treapNode* searchValue(valueType value);
treapNode* lRotate(treapNode* node);
treapNode* rRotate(treapNode* node);
};

treap::treap(valueType value)
{
srand(time(0));
root = new treapNode(value, rand());
}

treapNode* treap::searchRank(treapNode* baseNode, valueType rank)
{
baseNode = root;
int delta;
while (1)
{
delta = rank-baseNode->lChildNum-1;
if (delta==0) break;
if (delta>0)
{
baseNode=baseNode->rChild;
rank=delta;
}
else baseNode=baseNode->lChild;
}

return baseNode;
// int delta=rank-baseNode->lChildNum-1;
// if (delta==0) return baseNode;
// if (delta>0)
// {
//     //baseNode must have a rChild
//     return searchRank(baseNode->rChild, delta);
// }
// else
// {
//     //baseNode must have a lChild
//     return searchRank(baseNode->lChild, rank);
// }
}

treapNode* treap::searchValue(valueType value)
{
treapNode* travNode = root;
while (1)
{
if (value>travNode->value)
{
if (travNode->rChild==NULL) break;
travNode=travNode->rChild;
}
if (value<travNode->value)
{
if (travNode->lChild==NULL) break;
travNode=travNode->lChild;
}
}

return travNode;
}

void treap::deleteRank(valueType rank)
{
treapNode* deleteRankPointer = searchRank(root, rank);
treapNode* tempNodePointer=deleteRankPointer;
while(1)
{
if (tempNodePointer->lChild!=NULL || tempNodePointer->rChild!=NULL)
{
if (tempNodePointer->lChild!=NULL && (tempNodePointer->rChild==NULL || tempNodePointer->lChild->prior>tempNodePointer->rChild->prior)) rRotate(tempNodePointer);
else lRotate(tempNodePointer);
}
else
{
if (tempNodePointer->parent->value>tempNodePointer->value)
{
tempNodePointer=tempNodePointer->parent;
tempNodePointer->lChild=NULL;
tempNodePointer->lChildNum=0;
deleteRankPointer->parent=NULL;
delete deleteRankPointer;
}
else
{
tempNodePointer=tempNodePointer->parent;
tempNodePointer->rChild=NULL;
tempNodePointer->rChildNum=0;
deleteRankPointer->parent=NULL;
delete deleteRankPointer;
}
break;
}
}
treapNode* travNode=tempNodePointer;
while (travNode!=root)
{
if (travNode->parent->value>travNode->value) travNode->parent->lChildNum--;
else travNode->parent->rChildNum--;
travNode=travNode->parent;
}
}

treapNode* treap::insertNode(valueType value)
{
treapNode* tempNodePointer = searchValue(value);
if (tempNodePointer->value>value)
{
//tempNodePointer->lChildNum++;
tempNodePointer->lChild=new treapNode(value, rand());
tempNodePointer->lChild->parent=tempNodePointer;
tempNodePointer=tempNodePointer->lChild;
}
else
{
//tempNodePointer->rChildNum++;
tempNodePointer->rChild=new treapNode(value, rand());
tempNodePointer->rChild->parent=tempNodePointer;
tempNodePointer=tempNodePointer->rChild;
}
treapNode* travNode = tempNodePointer;
//update by prior first
while (travNode!=root)
{
if (travNode->prior<=travNode->parent->prior) break;
if (travNode->parent->value>travNode->value) rRotate(travNode->parent);
else lRotate(travNode->parent);
}
//update the childNum of upper nodes
while (travNode!=root)
{
if (travNode->parent->value>travNode->value) travNode->parent->lChildNum++;
else travNode->parent->rChildNum++;
travNode=travNode->parent;
}

return tempNodePointer;
}

treapNode* treap::lRotate(treapNode* node)
{
//node has a rChild

if (node!=root)
{
//node has a parent
if (node->parent->value>node->value) node->parent->lChild=node->rChild;
else node->parent->rChild=node->rChild;
node->rChild->parent=node->parent;
}
else
{
root=root->rChild;
root->parent=NULL;
//no need to update childNum
}
treapNode* tempNodePointer = node->rChild;
if (node->rChild->lChild!=NULL)
{
node->rChild=node->rChild->lChild;
node->rChildNum=tempNodePointer->lChildNum;
node->rChild->parent=node;
}
else
{
node->rChild=NULL;
node->rChildNum=0;
}
tempNodePointer->lChild=node;
node->parent=tempNodePointer;
tempNodePointer->lChildNum=node->lChildNum+node->rChildNum+1;

return tempNodePointer;
}

treapNode* treap::rRotate(treapNode* node)
{
//node has a lChild

if (node!=root)
{
//node has a parent
if (node->parent->value>node->value) node->parent->lChild=node->lChild;
else node->parent->rChild=node->lChild;
node->lChild->parent=node->parent;
}
else
{
root=root->lChild;
root->parent=NULL;
//no need to update childNum
}
treapNode* tempNodePointer = node->lChild;
if (node->lChild->rChild!=NULL)
{
node->lChild=node->lChild->rChild;
node->lChildNum=tempNodePointer->rChildNum;
node->lChild->parent=node;
}
else
{
node->lChild=NULL;
node->lChildNum=0;
}
tempNodePointer->rChild=node;
node->parent=tempNodePointer;
tempNodePointer->rChildNum=node->lChildNum+node->rChildNum+1;

return tempNodePointer;
}

void treap::printTreap(treapNode* tempRoot)
{
if (tempRoot->lChild!=NULL) printTreap(tempRoot->lChild);
printf("%lld: %d; lN: %d; rN: %d; lC: %lld; rC: %lld\n", tempRoot->value, tempRoot->prior, tempRoot->lChildNum, tempRoot->rChildNum, tempRoot->lChild==NULL?0:tempRoot->lChild->value, tempRoot->rChild==NULL?0:tempRoot->rChild->value);
if (tempRoot->rChild!=NULL) printTreap(tempRoot->rChild);
}

int main()
{
int n;
scanf("%d", &n);

int op;
valueType inputX, inputY;
int result=0;

scanf("%d %lld %lld", &op, &inputX, &inputY);

treap* xTreap=new treap(inputX);
treap* yTreap=new treap(inputY);

int Count=1;
for (int i=1; i<n; i++)
{
scanf("%d %lld %lld", &op, &inputX, &inputY);
switch (op)
{
case 0:
xTreap->insertNode(inputX);
yTreap->insertNode(inputY);
Count++;
break;
case 1:
break;
case 2:
xTreap->deleteRank(inputX+1);
yTreap->deleteRank(inputY+1);
Count--;
break;
default:
break;
}
}

return 0;
}

0

Решение

Задача ещё не решена.

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]