关于优化 vector

有 $5 \times 10^5$ 个 vector，需要在后面加入元素，遍历，删除任意一个元素，二分查找。

如果用 vector 做的话会 TLE，有没有别的数据结构能优化 erase 的时间复杂度（erase 复杂度听说很玄学，如果 erase 能做到 $O(1)$ 或 $O(\log)$ 就可以），还要保证能二分（试过链表，但是链表无法二分）

或者对于 vector 有没有卡常的操作