0

我刚刚了解了一些关于 GNU 基于策略的数据结构的知识。但是我在这个问题上得到了一些意想不到的结果：（原版是中文描述的，所以我已经翻译了。）

您需要编写一个支持以下操作的数据结构：

  1. 插入号码x
  2. 删除号码x
  3. 查找 numberx的 order("order" 是指小于这个 number 的元素个数+1)
  4. 查找订单号x
  5. 查找 numberx的前缀
  6. 查找 numberx的后缀
     #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]

4

0 回答 0