线段树：跳水问题

【来源】网上流传的2017-360秋招笔试题
【问题描述】
【算法思路】
直接求解会超时。使用“线段树”，节点信息为当前区段的元素个数。假设输入元素最大值为M, 建立有M个叶子节点的树，再依次插入元素并向上更新节点信息。
【程序】
  1 #include <iostream>
  2 #include <vector>
  3 
  4 //#pragma comment(linker, "/STACK:102400000,102400000")
  5 using namespace std;
  6 struct Segment
  7 {
  8     int l, r;
  9     int value;
 10     bool lazyTag;
 11     int lazyValue;
 12     Segment() :l(0), r(0), value(INT_MAX), lazyTag(false) {};
 13 };
 14 void buildTree(vector<Segment> &tree, int node, int l, int r)
 15 {
 16     tree[node].l = l;
 17     tree[node].r = r;
 18     if (l == r) return;
 19     buildTree(tree, node << 1, l, (l + r) >> 1);
 20     buildTree(tree, (node << 1) + 1, (l + r + 1) >> 1, r);
 21     tree[node].value = tree[node << 1].value + tree[(node << 1) + 1].value;
 22 }
 23 void update(vector<Segment> &tree, int node)
 24 {
 25     if (node == 0) return;
 26     // <<1相当于*2，>>1相当于/2取整
 27     tree[node].value = tree[node << 1].value+tree[(node << 1) + 1].value;
 28     update(tree, node >> 1);
 29 }
 30 void pushDown(vector<Segment> &tree, int father)
 31 {
 32     if (tree[father].lazyTag)
 33     {
 34         int leftChild = father << 1, rightChild = (father << 1) + 1;
 35         tree[leftChild].value = (tree[leftChild].r - tree[leftChild].l + 1)*tree[father].lazyValue;
 36         tree[leftChild].lazyTag = true;
 37         tree[leftChild].lazyValue = tree[father].lazyValue;
 38         tree[rightChild].value = (tree[rightChild].r - tree[rightChild].l + 1)*tree[father].lazyValue;
 39         tree[rightChild].lazyTag = true;
 40         tree[rightChild].lazyValue = tree[father].lazyValue;
 41         tree[father].lazyTag = false;
 42     }
 43 }
 44 void updateInterval(vector<Segment> &tree, int node, int l, int r, int value)
 45 {
 46     if (tree[node].l == l&&tree[node].r == r)
 47     {
 48         tree[node].lazyTag = true;
 49         tree[node].value = (r - l + 1)*value;
 50         tree[node].lazyValue = value;
 51         return;
 52     }
 53     else {
 54         //pushDown(tree, node);
 55         if (tree[node << 1].r >= r) updateInterval(tree, node << 1, l, r, value);
 56         else if (tree[(node << 1) + 1].l <= l) updateInterval(tree, (node << 1) + 1, l, r, value);
 57         else
 58         {
 59             updateInterval(tree, node << 1, l, tree[node << 1].r, value);
 60             updateInterval(tree, (node << 1) + 1, tree[(node << 1) + 1].l, r, value);
 61         }
 62     }
 63     tree[node].value = tree[node << 1].value + tree[(node << 1) + 1].value;
 64 }
 65 
 66 int query(vector<Segment> &tree, int node, int l, int r)
 67 {
 68     if (tree[node].l == l&&tree[node].r == r) return tree[node].value;
 69     else
 70     {
 71         //pushDown(tree, node);
 72         if (tree[node << 1].r >= r) return query(tree, node << 1, l, r);
 73         else if (tree[(node << 1) + 1].l <= l) return query(tree, (node << 1) + 1, l, r);
 74         else
 75         {
 76             return query(tree, node << 1, l, tree[node << 1].r) + query(tree, (node << 1) + 1, tree[(node << 1) + 1].l, r);
 77         }
 78     }
 79 }
 80 #define MAXN 200005
 81 int A[MAXN];
 82 int main() {
 83 #ifdef DEBUG
 84     ifstream cin("in.txt");
 85     ofstream cout("out.txt");
 86     //freopen("in.txt", "r",stdin);
 87     //freopen("out.txt", "w",stdout);
 88 #endif
 89     int n=0, a, b, size = 1;
 90     int N;
 91     cin >> N;
 92     for (size_t i = 0; i < N; i++)
 93     {
 94         cin >> A[i];
 95         n = max(n, A[i]);
 96     }
 97     while (size < n) size <<= 1;
 98     vector<Segment> tree(size * 2);
 99     for (size_t i = 0; i < size; i++)
100     {
101         tree[i + size].value=0;
102     }
103     buildTree(tree, 1, 1, size);
104     int ans;
105     for (size_t i = 0; i < N; i++)
106     {
107         tree[A[i]-1 + size].value++;
108         update(tree, (A[i]-1 + size)/2);
109         ans = query(tree,1,A[i],size);
110         if (!i)
111             cout << ans - tree[A[i] - 1 + size].value;  //减去相等的个数，输出大于的个数
112         else
113             cout<< ' '<< ans - tree[A[i] - 1 + size].value;
114     }
115 
116     return 0;
117 }