警示后人(如果你pbds 65pts)
查看原帖
警示后人(如果你pbds 65pts)
542881
日常放水WT双奔楼主2025/8/2 13:25

pbds中的tree不可以出现重复元素

若要处理此情况,可参考以下做:开一个double的平衡树

......//开一个double的avl,令常量eps=1e-9
      ......
            case 1: avl.insert(read()+i*eps); break;
            // 利用eps使重复元素之间产生细微差异
            case 2: avl.erase(avl.lower_bound(read())); break;    // 因为存在eps,所以需要lower_bound
            ......
            case 5: {
                auto it=avl.lower_bound(read());
                write(int(round(*--it)),'\n');              // 使用round应对负数的情况,比如-3+eps直接转为int后为-2,但round一下就还原-3了
                break;
            }
            case 6: {
                auto it=avl.lower_bound(read()+1);
                write(int(round(*it)),'\n'); break;        // 使用round应对负数的情况
            }
        }
    }

这里就不粘完整代码了,只粘几行启发一下思路

2025/8/2 13:25
加载中...