【來源】網上流傳的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 }