http://acm.hdu.edu.cn/showproblem.php?pid=3577题意：某路火车共有 N(N<=1000000：这个数字对于站点来说着实惊人)个站点,有Q个人先后去买[bi,ei) {for 1<=i<=Q}的票，问在保证火车上总人数总不超过K的情况下哪些人可以买到票。
TLE的实现：用full[i]标记此段是否被覆盖，在插入的时候，如果目标线段覆盖了子线段并且子线段的full是false，还不能插入，只有当full[i]==true，并且目标线段覆盖了子线段才插入此子线段。细想一下，如果插入的线段都是比较短的时候，这个线段树可能退化成插入节点，而不再是插入线段了。
TLE的代码(免得忘了这个，下次再写一个)
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 using namespace std;
5
6 const int max_n=1000005;
7 int tree[max_n*4+1],full[max_n*4+1];
8 int k,Q;
9 void query(int i,int lt,int rt,int beg,int end,bool &legal){
10 if(full[i]){
11 if(tree[i]>=k){
12 legal=false;
13 }
14 return;
15 }
16 int mid=(lt+rt)/2;
17 if(beg<=mid){
18 query(i<<1,lt,mid,beg,end,legal);
19 }
20 if(end>=mid+1){
21 query((i<<1)+1,mid+1,rt,beg,end,legal);
22 }
23 }
24
25 void insert(int i,int lt,int rt,int beg,int end){
26 if(beg<=lt&&end>=rt&&full[i]){
27 tree[i]++; full[i]=true;
28 return;
29 }
30 if(full[i]){
31 full[i]=false; full[(i<<1)]=full[(i<<1)+1]=true;
32 tree[i<<1]=tree[(i<<1)+1]=tree[i];
33 }
34 int mid=(lt+rt)/2;
35 if(beg<=mid){
36 insert(i<<1,lt,mid,beg,end);
37 }
38 if(end>=mid+1){
39 insert((i<<1)+1,mid+1,rt,beg,end);
40 }
41 }
42 int main()
43 {
44
45 int T;
46 scanf("%d",&T);
47 for(int ncas=1;ncas<=T;ncas++){
48 scanf("%d%d",&k,&Q);
49
50 tree[1]=0,full[1]=true;
51 printf("Case %d:\n",ncas);
52 int beg,end;
53 for(int i=0;i<Q;i++){
54 scanf("%d%d",&beg,&end);
55 bool legal=true;
56 query(1,1,max_n-1,beg,end-1,legal);
57 if(legal){
58 insert(1,1,max_n-1,beg,end-1);
59 printf("%d ",i+1);
60 }
61 }
62 printf("\n\n");
63 }
64 }
65
改进：设两个属性： cover[i]记录完全覆盖次数， max_subcover[i] ：子段覆盖最大次数。