|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34 |
Color the ballTime Limit: 9000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 7117 Accepted Submission(s): 3688Problem DescriptionN个气球排成一排，从左到右依次编号为1,2,3....N.每次给定2个整数a b(a <= b),lele便为骑上他的“小飞鸽"牌电动车从气球a开始到气球b依次给每个气球涂一次颜色。但是N次以后lele已经忘记了第I个气球已经涂过几次颜色了，你能帮他算出每个气球被涂过几次颜色吗？ Input每个测试实例第一行为一个整数N,(N <= 100000).接下来的N行，每行包括2个整数a b(1 <= a <= b <= N)。当N = 0，输入结束。 Output每个测试实例输出一行，包括N个整数，第I个数代表第I个气球总共被涂色的次数。 Sample Input31 12 23 331 11 21 30 Sample Output1 1 13 2 1 |
思路：用线段树存储，不必插到底。查找结果的时候结点值加上父亲结点的值，最后得到数组即是结果。
#define _CRT_SECURE_NO_DEPRECATE #include<iostream> #include<cstdio> #include<cstring> #include<cmath> #define MAX 100002 #define MAXN 400005 using namespace std; struct STree{ int key, lc, rc; }; STree stree[MAXN]; int n, res[MAX]; void BuildTree(int i, int l, int r){ stree[i].key = 0; stree[i].lc = l; stree[i].rc = r; if (l == r)return; int mid = (l + r) / 2; BuildTree(i * 2, l, mid); BuildTree(i * 2 + 1, mid + 1, r); } void Insert(int i, int l, int r){ if (stree[i].lc == l&&stree[i].rc == r){ stree[i].key++; return; } int mid = (stree[i].lc + stree[i].rc) / 2; if (mid >= r)Insert(i * 2, l, r); else if(mid < l) Insert(i * 2 + 1, l, r); else { Insert(i * 2, l, mid); Insert(i * 2 + 1, mid + 1, r); } } void GetResult(int k){ if (stree[k].lc == stree[k].rc){ res[stree[k].lc] = stree[k].key; return; } stree[k * 2].key += stree[k].key; stree[k * 2 + 1].key += stree[k].key; GetResult(k * 2); GetResult(k * 2 + 1); } int main() { int h, e; while (cin >> n){ if (n == 0)break; BuildTree(1, 1, n); for (int i = 0; i < n; i++){ cin >> h >> e; Insert(1, h, e); } memset(res, 0, sizeof(res)); GetResult(1); for (int i = 1; i < n; i++)cout << res[i] << " "; cout << res[n] << endl; } return 0; }
原文：http://www.cnblogs.com/littlehoom/p/3568548.html