• Главная
• Все исходники
• Добавить
• md5
• base64
• url
• diff

<untitled> (C++)

Ревизии: current

#include <iostream>

using namespace std;

struct node {
    int key;
    int level;
    node *left, *right;
};

typedef node* tree;

tree bottom, deleted, last;

void init_aa_tree() {
    bottom = new node;
    bottom->level = 0;
    bottom->right = bottom;
    bottom->left = bottom;
    deleted = bottom;
}

void skew(tree &T) {
    if (T->left->level == T->level) {
        tree temp = T->left;
        T->left = temp->right;
        temp->right = T;
        T = temp;
    }
}

void split(tree &T) {
    if (T->right->right->level == T->level) {
        tree temp = T->right;
        T->right = temp->left;
        temp->left = T;
        T = temp;
    }
}

void insert(int x, tree &T) {
    if (T == bottom) {
        T = new node;
        T->left = bottom;
        T->right = bottom;
        T->key = x;
        // cerr << "# " << T->key << " " << x << endl;
        T->level = 1;
    } else {
        if (x < T->key)
            insert(x, T->left);
        else if (x > T->key)
            insert(x, T->right);
        skew(T);
        split(T);
    }
}

void del(int x, tree &T) {
    if (T != bottom) {
        last = T;
        if (x < T->key) {
            del(x, T->left);
        } else {
            deleted = T;
            del(x, T->right);
        }

        if (T == last && deleted != bottom && x == deleted->key) {
            deleted->key = last->key;
            deleted = bottom;
            T = T->right;
            delete last;
        }

        if (T->left->level < T->level - 1 || T->right->level < T->level - 1) {
            T->level--;
            if (T->right->level > T->level)
                T->right->level = T->level;
            skew(T);
            skew(T->right);
            skew(T->right->right);
            split(T);
            split(T->right);
        }
    }
}

bool helper = false;

void find(int x, tree T, int &result) {
    // cerr << "finding " << x << " in " << T -> key << endl;
    if (T != bottom) {
        if (x == T->key) {
            result = x;
            return;
        }
        if (x > T->key) {
            find(x, T->right, result);
        } else {
            find(x, T->left, result);
        }

        // cerr << "helper in " << T->key << ": " << helper << endl;

        if (helper && T->key >= x) {
            result = T->key;
            helper = false;
        }
    } else {
        helper = true;
    }
}

int main() {
    init_aa_tree();
    tree S = bottom;
    int n;
    cin >> n;
    char last = '+';
    int last_res;
    for (int i = 0; i < n; ++i) {
        char oper;
        int x;
        cin >> oper >> x;
        // cerr << oper << x << endl;
        if (oper == '+') {
            if (last == '?') {
                insert((last_res + x) % (1000*1000*1000), S);
                // cerr << "after insertion S->key = " << S->key << endl;
            } else {
                insert(x, S);
            }
            last = '+';
        } else {
            last_res = -1;
            find(x, S, last_res);
            cout << last_res << endl;
            last = '?';
        }
    }
    return 0;
}
 

Комментарии:

Нет