Color the ball
Time Limit: 9000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 6346 Accepted Submission(s): 3354
Problem Description
N个气球排成一排，从左到右依次编号为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，输入结束。
当N = 0，输入结束。
Output
每个测试实例输出一行，包括N个整数，第I个数代表第I个气球总共被涂色的次数。
Sample Input
3 1 1 2 2 3 3 3 1 1 1 2 1 3 0
Sample Output
1 1 1 3 2 1
Author
8600
Source
HDU 2006-12 Programming Contest
Recommend
LL
/*
线段树这道题做完以后，收获很大，学到了线段树的另一种应用：如果需要对某个区间内所有元素进行同样操作，则只需要对线段树上对应区间进行操作即可。
统计每个气球被涂次数，只需要匹配到线段树的对应的区间即可，不需要统计到叶子节点。否则会超时，在最后统计结果的时候则需要搜索到叶子节点。
即：①处的作用
*/#include <iostream>
using namespace std;
const int nMax = 100010;
//int A[nMax];
struct Node
{int l, r;int num;Node(){}Node(int l,int r,int num) : l(l), r(r), num(num){}
}node[nMax * 4];
int ans[nMax];
int N;void build(int rt, int l, int r)
{if(l < r){int mid = (l + r) / 2;build(rt * 2, l, mid);build(rt * 2 + 1, mid + 1, r);node[rt] = Node(l, r, 0);}else if(l == r)node[rt] = Node(l, r, 0);
}void update(int rt, int l, int r)
{if(node[rt].l ==l && node[rt].r == r)//①node[rt].num ++;else{int mid = (node[rt].l + node[rt].r) / 2;if(mid >= r)update(rt * 2, l, r);else if(mid + 1 <= l)update(rt * 2 + 1, l, r);else{update(rt * 2, l, mid);update(rt * 2 + 1, mid + 1, r);}}
}void solve(int rt)
{int i;if(node[rt].num > 0){for(i = node[rt].l; i <= node[rt].r; ++ i)ans[i] += node[rt].num;}if(node[rt].l < node[rt].r){solve(rt * 2);solve(rt * 2 + 1);}
}int main()
{//freopen("e://data.in", "r", stdin);while(scanf("%d", &N) != EOF && N){int a, b;int i;build(1, 1, N);for(i = 1; i <= N; ++ i){scanf("%d%d", &a, &b);update(1, a, b);}memset(ans, 0, sizeof(ans));solve(1);for(i = 1; i <= N; ++ i){if(i != 1) printf(" ");printf("%d", ans[i]);}printf("\n");}return 0;
}
/**Description:初学线段树 Author:qzc Created:2013.9.18 Last Change:Functions:*/
#include<iostream>
#include<stdio.h>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
#include<math.h>
#include<string>
#include<string.h>
#define N 100001
using namespace std;
struct Node{int left,right,num;Node(){} Node(int left,int right,int num):left(left),right(right),num(num){}
}node[N*4];
int cnt[N];
int built(int index,int left,int right){node[index]=Node(left,right,0);if(left<right){int mid=(left+right)/2;built(index*2,left,mid);built(index*2+1,mid+1,right);}return 0;
}
int update(int left,int right,int index){if(node[index].left==left&&node[index].right==right){node[index].num++;return 0; }int mid=(node[index].left+node[index].right)/2;if(mid>=right)update(left,right,index*2);else if(mid+1<=left)update(left,right,index*2+1);else{update(left,mid,index*2);update(mid+1,right,index*2+1);}return 0;
}
int addall(int n){for(int i=1;i<4*n;i++){if(!node[i].left)continue; //break;会WA if(node[i].left==node[i].right){cnt[node[i].left]+=node[i].num; //cout<<cnt[node[i].left];} else {node[i*2].num+=node[i].num;node[i*2+1].num+=node[i].num;}}return 0;
}
int main(){// freopen("in.txt","r",stdin);int n;while(cin>>n,n){int i,j,k;memset(cnt,0,sizeof(cnt));built(1,1,n);for(i=1;i<=n;i++){int a,b;scanf("%d%d",&a,&b);update(a,b,1);}addall(n);for(i=1;i<n;i++)printf("%d ",cnt[i]);printf("%d\n",cnt[i]);}return 0;
}