- Color the ball
- Time Limit: 9000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
- Total Submission(s): 29305 Accepted Submission(s): 14264
- 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, 输入结束.
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 1556
- #include <iostream>
- #include <cstdio>
- #include <algorithm>
- #include <cstring>
- #include <set>
- #include <map>
- using namespace std;
- #define ll long long
- #define lowbit(x) x&(-x)
- const int N=1e5+9;
- ll a[N],c[N];
- ll n,x,y;
- void update(ll x,ll num){
- while(x<=n){
- c[x]+=num;
- x+=lowbit(x);
- }
- }
- ll getsum(ll x){
- ll sum = 0;
- while(x>0){
- sum+=c[x];
- x-=lowbit(x);
- }
- return sum;
- }
- int main()
- {
- while(~scanf("%lld",&n),n){
- for(ll i = 1 ;i <=n+9;i++){
- a[i]=0;
- c[i] =0;
- }
- for(ll i =0;i<n;i++){
- scanf("%lld%lld",&x,&y);
- update(x,1);
- update(y+1,-1);
- }
- for(ll i =1;i<=n;i++){
- printf("%lld%c",getsum(i),i==n?'\n':' ');
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2833570.html