pbds警示后人
查看原帖
pbds警示后人
542881
日常放水WT双奔楼主2025/8/2 13:20

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

如果要处理重复元素,可使用double存储并参考以下做法:

......//开一个double的avl,令常量eps=1e-9
     avl;
      ......
            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());
                //if(it==avl.begin()) write(-1,'\n');
                else write(int(round(*--it)),'\n');              // 使用round应对负数的情况,比如-3+eps直接转为int后为-2,但round一下就还原-3了
                break;
            }
            case 6: {
                auto it=avl.lower_bound(read()+1);
                //if(it==avl.end()) write(-1,'\n');
                else write(int(round(*it)),'\n'); break;        // 使用round应对负数的情况
            }
        }
    }
2025/8/2 13:20
加载中...