1 #include <bits/stdc++.h> 2 using namespace std; 3  4 const int MAXN = 3e4 + 10; 5 int n,  m,  l,  r;                  //长度n，线段数m 6  7  8 struct line { 9     int left, right;                //left:左边界 right:右边界10     int n;                          //该节点的权值11 } a[MAXN];12 13 void buildt(int l,  int r,  int step){14     a[step].left = l;               //建立当前节点的左边界赋值15     a[step].right = r;              //建立当前节点的右边界赋值16     a[step].n = 0;                  //初始化当前节点的权值17     if(l == r)  {return; }          //如果是叶子节点，不进行下面的递归建树操作18     buildt(l, (l + r) / 2, step * 2); //递归建立左结点19     buildt((l + r) / 2 + 1, r, step * 2 + 1); //递归建立右结点20 }21 22 void dfs(int step){23     cout << step          << "    "  //当前节点下标24          << a[step].left  << "    "  //结点左边界25          << a[step].right << "    "  //结点右边界26          << a[step].n     << endl;   //结点对应权值27     if(a[step].left == a[step].right) return;//若为叶子结点，结束当前节点深搜28     dfs(step * 2);      //递归搜索左结点29     dfs(step * 2 + 1);  //递归搜索右结点30     return ;31 }32 33 void insert(int s, int t, int step){34     if(s == a[step].left && t == a[step].right) {35         ++ a[step].n; //插入的线段匹配则该条线段的记录 +136         return ;      //插入操作成功，返回37     }38 39     if(a[step].left == a[step].right) //如果当前线段没有子节点，返回40         return ;41 42     int mid = (a[step].left + a[step].right) / 2; //二分思想确立中值mid43 44     if(mid >= t) {              //如果中值在t的右边45         insert(s, t, step * 2); //则插入到左儿子46 47     } else if (mid < s) {       //如果中值在s的左边48         insert(s, t, step * 2 + 1);//则插入到右儿子49 50     } else {51         insert(s, mid, step * 2);//否则中点将线段划分，左端到中点部分放入左结点52         insert(mid + 1, t, step * 2 + 1);//中点到右端部分放入右结点53     }54     return ;55 }56 57 int main(){58     cout << MAXN << endl;59     cin >> n >> m;60     buildt(0, n, 1);61     //dfs(1);62     for(int i = 0; i < m; i ++ ) {63         cin >> l >> r;64         insert(l, r, 1);65     }66     dfs(1);67     return 0;68 }