Questions

6 数字分段 TODO

这个二分法是用什么二分的？是前缀和？可是不是要分成很多段嘛？分成三段的画，怎么二分呢？

4 链表优化 40 TLE TODO

我直接用的 stl 里面的 vector，我想不到有什么优化的方法。找的过程如果用 hashtable，可以缩短到 O(1) 时间找到，但是在插入的时候，hashtable 就要花费 O(n) 的时间来修改，我现在这样是花费多个 O(logn)，改 hash 难道不是得不偿失吗？

# include <cstdio>
# include <vector>
# include <algorithm>
using namespace std;

int main(){
    int n,m,lr,v;
    vector<int>team(1,1);
    scanf("%d",&n);
    for(int i = 1;i<n;i++){
        scanf("%d %d",&v,&lr);
        team.insert(find(team.begin( ),team.end( ), v)+lr,i+1);
    }
    scanf("%d",&m);
    for(int i = 0;i<m;i++){
        scanf("%d",&v);
        vector<int>::iterator res = find(team.begin( ), team.end( ), v);
        if (res != team.end())
            team.erase(res);
    }
    for(int i = 0;i<team.size();i++){
        printf("%d",team[i]);
        if(i != team.size()-1)printf(" ");
        else printf("\n");
    }
    return 0;
}