線段樹
線段樹是一種二叉搜尋樹，與區間樹相似，它将一個區間劃分成一些單元區間，每個單元區間對應線段樹中的一個葉結點。
對于線段樹中的每一個非葉子節點[a,b]，它的左兒子表示的區間為[a,(a+b)/2]，右兒子表示的區間為[(a+b)/2+1,b]。是以線段樹是平衡二叉樹，最後的子節點數目為N，即整個線段區間的長度。
使用線段樹可以快速的查找某一個節點在若幹條線段中出現的次數，時間複雜度為O(logN）。而未優化的空間複雜度為2N，是以有時需要離散化讓空間壓縮。
題目連結: http://acm.zzuli.edu.cn/zzuliacm/problem.php?id=1877
代碼:
1 #include <cstdio>
2 #include <cmath>
3 #include <cstring>
4 #include <string>
5 #include <algorithm>
6 #include <queue>
7 #include <stack>
8 #include <map>
9 #include <set>
10 #include <vector>
11 #include <iostream>
12 using namespace std;
13 #define for0(i, n) for(int i=0; i<(n); ++i)
14 #define for1(i,a,n) for(int i=(a);i<=(n);++i)
15 #define for2(i,a,n) for(int i=(a);i<(n);++i)
16 #define for3(i,a,n) for(int i=(a);i>=(n);--i)
17 #define for4(i,a,n) for(int i=(a);i>(n);--i)
18 #define CC(i,a) memset(i,a,sizeof(i))
19 #define LL long long
20 #define MOD 1000000007
21 #define inf 0x3f3f3f3f
22
23 #define EPS 1e-6
24 #define N 100010
25 #define lson p<<1
26 #define rson p<<1|1
27
28 struct num
29 {
30 int l,r;
31 }a[N];
32 int v[N];
33
34 struct node
35 {
36 int l,r,x;
37 int mid(){
38 return (l+r)/2;
39 }
40 int len(){
41 return (r-l+1);
42 }
43 }tree[N<<2];
44
45 void buildtree(int p,int L,int R)
46 {
47 tree[p].l=L;
48 tree[p].r=R;
49 tree[p].x=0;
50 if(L==R)
51 return ;
52
53 buildtree(lson,L,tree[p].mid());
54 buildtree(rson,tree[p].mid()+1,R);
55 }
56
57 void update(int p,int L,int R)
58 {
59 if(tree[p].l==L && tree[p].r==R){
60 tree[p].x++;
61 return ;
62 }
63 if(R <= tree[p].mid())
64 update(lson,L,R);
65 else if(L > tree[p].mid())
66 update(rson,L,R);
67 else{
68 update(lson,L,tree[p].mid());
69 update(rson,tree[p].mid()+1,R);
70 }
71 }
72
73 void up(int p,int L,int R)
74 {
75 if(L==R)
76 return ;
77 tree[lson].x += tree[p].x;
78 tree[rson].x += tree[p].x;
79
80 up(lson,L,tree[p].mid());
81 up(rson,tree[p].mid()+1,R);
82
83 tree[p].x = min(tree[lson].x,tree[rson].x);
84 }
85
86 int query(int p,int L,int R)
87 {
88 if(tree[p].l==L && tree[p].r==R)
89 return tree[p].x;
90 if(R <= tree[p].mid())
91 return query(lson,L,R);
92 else if(L > tree[p].mid())
93 return query(rson,L,R);
94 else
95 return min(query(lson,L,tree[p].mid()),query(rson,tree[p].mid()+1,R));
96
97 }
98
99 int main()
100 {
101 int t;
102 scanf("%d",&t);
103 while(t--){
104 int n,m,k=0,ans;
105 scanf("%d%d",&n,&m);
106 memset(a,0,sizeof(a));
107 memset(v,0,sizeof(v));
108 buildtree(1,1,n);
109
110 for(int i=1; i<=m; i++){
111 scanf("%d%d",&a[i].l,&a[i].r);
112 update(1,a[i].l,a[i].r);
113 }
114
115 up(1,1,n);
116
117 for(int i=1; i<=m; i++){
118 ans=query(1,a[i].l,a[i].r);
119 if(ans >= 2)
120 v[k++] = i;
121 }
122 printf("%d\n", k);
123 for(int i=0; i<k; i++)
124 printf("%d%c", v[i], i==k-1?'\n':' ');
125 }
126 return 0;
127 } 另外的版本: https://hrbust-acm-team.gitbooks.io/acm-book/content/data_structure/ds_part3.html