警示后人如果你ODT就是到处RE/MLE

首先确认你分割区间是先分 r+1 再分 l

然后记得多插一个，把

n+1

插进去

其次，删除之后把迭代器都重新取一遍，虽然确实按一定顺序删就没有问题，但是重新取一遍也不花什么时间是不是？

最后，最好时刻保证每次 erase(itl,itr) 后这个区间都会被再次填充

什么意思？比如交换操作，你原本这么写

CPP

inline void swap(int l1,int r1,int l2,int r2)
{
    std::vector<Node>v1,v2;
    auto itr=split(r1+1),itl=split(l1);
    for (auto it=itl;it!=itr;it++) v1.push_back(*it);
    S.erase(itl,itr);
    itr=split(r2+1),itl=split(l2);
    for (auto it=itl;it!=itr;it++) v2.push_back(*it);
    S.erase(itl,itr);
    for (int i=0;i<v1.size();i++)
        S.insert(Node(l2+v1[i].l-l1,l2+v1[i].r-l1,v1[i].v));
    for (int i=0;i<v2.size();i++)
        S.insert(Node(l1+v2[i].l-l2,l1+v2[i].r-l2,v2[i].v));
}

不如改成

CPP

inline void swap(int l1,int r1,int l2,int r2)
{
    std::vector<Node>v1,v2;
    auto itr=split(r1+1),itl=split(l1);
    for (auto it=itl;it!=itr;it++) v1.push_back(*it);
    itr=split(r2+1),itl=split(l2);
    for (auto it=itl;it!=itr;it++) v2.push_back(*it);
    erase(l2,r2);
    for (int i=0;i<v1.size();i++)
        S.insert(Node(l2+v1[i].l-l1,l2+v1[i].r-l1,v1[i].v));
    erase(l1,r1);
    for (int i=0;i<v2.size();i++)
        S.insert(Node(l1+v2[i].l-l2,l1+v2[i].r-l2,v2[i].v));
}

这么整之后常数并没有增大很多，但是可以有效避免迭代器问题

警示后人如果你ODT就是到处RE/MLE

讨论操作

回复

相关推荐

警示后人如果你ODT就是到处RE/MLE