这个题很多人用线段树过了。那个做法我看了，是很好的，可惜是个离线。而有的时候我们需要在线。比方说，把题面改改，倘若再给你个n倍时间，让你每插入一个人就把整个表输出一遍，你再倒过来还能做吗？那就很难了对吧。
所以我觉得这个题吧，其实正解是个跳表。
1.
首先我们不考虑跳表，考虑二叉搜索树。
如果这个题用二叉搜索树，怎么做呢？
考虑一下啊。
首先很容易知道每个人名字和点的键值key是没关系的对吧。
那么人的名字就只能作为value了对吧。
那我们需要个key。
那么，key要保证什么条件呢？
很明显每次插进去一个点q，插在b点的位置上，而a是b点前的点。
那么插入前：
a->b
插入后：
a->q->b
对吧。
那么就要求q.key>a.key , q.key<b.key
能够想到的一个很简单的办法就是q.key = (a.key+b.key)/2
那么问题解决了：
我们首先给队首加个虚点key=0，给队尾加个虚点key = DOUBLE_MAX;
然后每次查询找到要插入的位置（二叉搜索树以key的大小二叉）上的点b，然后找他的前面的点a，然后你就知道了q的key，value赋进去，然后插进去就行了。
所以本题就这么结束了。。。才没有！
我们稍稍动动脑筋想想就知道，double最大值才1e300多点，你这边倒好一下子弄了个2e5的插入，那么我们需要（最糟糕的情况）分割成 2^(2e5) 段，很明显每一段的间隔是小数点后很多很多位，这种情况下我们比较double的大小真的可以做到吗？很明显不行对不对！
好了，问题来了，现在我们来解决它。
用key判断不是精度不够吗？我们不用key不就好了！
——解决个毛啊，二叉搜索树没有key还搜个屁。。。
这就是为什么这个题要用跳表。
因为，跳表是可以没有key的。
= =当然了有key的跳表会更加好写就是了。
2.
Q：什么是跳表
A：网上很多教程了，都挺不错的，再写就浪费资源了。
Q：跳表有什么用
A：二叉搜索树能做的都能做。
Q：那么比二叉搜索树好在哪？
A：好在它不用key的大小来指定节点的先后关系，而是多条重叠的链表一样，指针指定先后顺序的。这样就可以搞不方便建key的题。
而且，多线程的时候似乎比二叉搜索树性能好。（只是听过有这么个说法，然而我并没有验证过）
Q：那么比二叉搜索树差在哪？
A：如果可以建key：需要花费n*logn的空间。
如果不可以建key：需要花费2*n*logn的空间。
空间复杂度不优。
3.如何从有key的跳表转化为无key的跳表。
有key跳表你们随便去找个人博客看看就行了，那个讲的人很多的，
http://www.cppblog.com/mysileng/archive/2013/04/06/199159.html
我的跳表是用这份改的，并没有刻意抹痕迹所以大家还是可以知道哪里对应哪里的
有key跳表的节点：
struct node { int key; int value; node *next[MAX_LEVEL]; }; 其中，next指向的就是每层的下一个节点无key跳表的节点：
struct node { int value; node *next[MAX_LEVEL]; int seg[MAX_LEVEL]; };可以注意到我们去掉了一个key，而新增了一个seg数组。seg[i]记录的是this到next[i]之间的距离值
这个题只有一个插入操作对吧。
大体的思路是，插入的时候，除了update数组以外，我们还要记录一个updateseg数组，用来记录当前update[i]的key。
这个key并不是记录在节点里的，而是从表头往后，一个一个seg[i]加上去的。
就是说，每次遍历到这个点的时候，用路径上的一个个seg来加出来当前的key，然后存进数组。
然后根据两个数组判断一下，做个插入操作就行了。
思路很简单。
具体可以看我代码= =
代码写的很丑见谅啊。
#include<stdio.h> #include<string.h> #include<math.h> #include<iostream> #include<cstdlib> //#include<algorithm> //#include<map> //#include<deque> //#include<vector> //#include<set> //#include<bits/stdc++.h> //#include<tr1/unordered_map> using namespace std; #define MAXN 200008 #define MAX_LEVEL 17 //节点 struct node { int value; node *next[MAX_LEVEL]; int seg[MAX_LEVEL]; node() { value = 0; for (int i = 0; i < MAX_LEVEL; i++) { next[i] = NULL; seg[i] = 0; } } }; node nodes[MAXN]; int nodecnt; //创建节点 node* createNode(int level, int value) { nodes[nodecnt] = node(); nodes[nodecnt].value = value; nodecnt++; return nodes + (nodecnt - 1); } //随机产生层数 int randomLevel() { int k = 1; while (rand() % 2) k++; k = (k < MAX_LEVEL) ? k : MAX_LEVEL - 1; return k; } //跳表 struct skiplist { int level; int size; node *header; skiplist() { level = 0; size = 0; header = NULL; } //初始化跳表 void init() { level = 0; size = 0; header = NULL; nodecnt = 0; header = createNode(0, 0); } //插入节点（把所有后面的节点后移一个） int insertNode(int key, int value) { node *update[MAX_LEVEL]; for (int i = 0; i < MAX_LEVEL; i++) { update[i] = header; } int updateseg[MAX_LEVEL]; for (int i = 0; i < MAX_LEVEL; i++) { updateseg[i] = 0; } node *p, *q; q = NULL; p = header; int k = level; //从最高层往下查找需要插入的位置 //填充update int nowkey = 0; for (int i = level - 1; i >= 0; i--) { while (((q = p->next[i]) != NULL) && (nowkey + p->seg[i] < key)) { nowkey += p->seg[i]; p = q; } updateseg[i] = nowkey; update[i] = p; } // if (q != NULL && q->key == key) { // return; // } //产生一个随机层数K //新建一个待插入节点q //一层一层插入 k = randomLevel(); //更新跳表的level if (k > level) { for (int i = level; i < k; i++) { updateseg[i] = -1; } level = k; } q = createNode(k, value); //逐层更新节点的指针，和普通列表插入一样 for (int i = 0; i < k; i++) { node* u = update[i]; if (updateseg[i] == -1) { //printf("IMHERE!!!\N"); header->seg[i] = key; header->next[i] = q; } else { if (updateseg[i] + u->seg[i] == key) { node* a = u; u = u->next[i]; q->seg[i] = 1; q->next[i] = u; a->next[i] = q; } else { if (update[i]->next[i] != NULL) { node* b = u->next[i]; q->next[i] = b; q->seg[i] = u->seg[i] - (key - updateseg[i]) + 1; u->next[i] = q; u->seg[i] = key - updateseg[i]; // //q->seg[i] = update[i]->seg[i]; } else { u->next[i] = q; u->seg[i] = key - updateseg[i]; } } } // } for (int i = k; i < level; i++) { node* u = update[i]; if (u->next[i] != NULL) { u->seg[i]++; } } size++; return 1; } void print() { node *p, *q; p = header; q = NULL; int k = level; int flag0 = 0; //for (int i = k - 1; i >= 0; i--) { while ((q = p->next[0]) != NULL) { if (flag0) printf(" "); else flag0 = 1; printf("%d", q->value); p = q; } //} printf("\n"); } void test_print() { //从最高层开始打印 node *p, *q = NULL; //从最高层开始搜 int k = level; for (int i = k - 1; i >= 0; i--) { p = header; while ((q = p->next[i]) != NULL) { printf("%d -> ", q->value); p = q; } printf("\n"); } printf("\n"); } void ppp() { for (int i = 0; i < 10; i++) { for (int j = 0; j < MAX_LEVEL; j++) { printf("%d ", nodes[i].next[j] - nodes); } printf("\n"); for (int j = 0; j < MAX_LEVEL; j++) { printf("%d ", nodes[i].seg[j]); } printf("\n"); printf("\n"); } } }; skiplist SL; int n; int main() { while (scanf("%d", &n) != EOF) { //scanf("%d", &n); SL.init(); int l, r; for (int i = 0; i < n; i++) { scanf("%d", &l); scanf("%d", &r); SL.insertNode(l + 1, r); } SL.print(); //SL.ppp(); } return 0; }
