Неожиданный результат GNU order-statistics-tree - PullRequest
Новая
       49

Неожиданный результат GNU order-statistics-tree

0 голосов
/ 26 мая 2018

Я только что кое-что узнал о структурах данных на основе политик GNU.Но я получил неожиданный результат по этому вопросу: (оригинальная версия описана на китайском языке, поэтому я перевел ее.)

Вам нужно написать структуру данных, которая поддерживает следующие операции:

  1. номер вставки x
  2. номер удаления x
  3. поиск номера x порядок («порядок» относится к числу элементов, меньших, чем это число+1)
  4. поиск номера, порядок которого x
  5. поиск номера x префикс
  6. поиск номера x 'суффикс s 
     #include <iostream>
     #include <vector>
     #include <ext/pb_ds/assoc_container.hpp>
     #include <ext/pb_ds/tree_policy.hpp>
     #include <set>

     using namespace std;
     using ost = __gnu_pbds::tree<
                            int,
                            __gnu_pbds::null_type,
                            less<int>,
                            __gnu_pbds::rb_tree_tag,
                            __gnu_pbds::tree_order_statistics_node_update>;

int a;
int main() {
    ost s;
    int n;
    cin>>n;
    int opnum;
    ost::iterator i;
    for(int j=1;j<=n;j++)
    {
        cin>>opnum;
        switch(opnum)
        {

            case 1:
                cin>>a;
                s.insert(a);
                break;
            case 2:
                cin>>a;
                s.erase(a);
                break;
            case 3:
                cin>>a;
                cout<<s.order_of_key(a)+1<<endl;
                break;
            case 4:
                cin>>a;
                cout<<*s.find_by_order(a-1)<<endl;
                break;
            case 5:
                cin>>a;
                i=s.lower_bound(a);
                --i;
                while(a<=*i)
                    --i;
                cout<<*i<<endl;
                break;
            case 6:
                cin>>a;
                cout<<*(s.upper_bound(a))<<endl;
                break;
        }
        /*
        for(auto i:s)
        {
            cout<<"\t"<<i<<endl;
        }
        */

    }
    return 0;
}

Но принимаются только 55% точек данных.А в неправильном ответе баллов проблемы возникают после сотен строк.Так что это должно быть очень маленькой проблемой.Вы можете понять это?Я был бы очень признателен.

Что я знаю о неожиданном результате, так это то, что он обычно превышает ожидаемый результат.Но в какой-то момент требуется 7 при выводе программы 6.так что я действительно запутался.Я даже не знаю, в какой дозе case возникает проблема.

Кроме того, точка данных гарантированно верна.Я проверил это самостоятельно, написав Treap.

РЕДАКТИРОВАТЬ

диапазон данных:

предел операций: 100000 раз числовой предел: каждое число находится в [-10000000, 10000000]

...