Color the ball
Time Limit: 9000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 16530 Accepted Submission(s): 8228
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
Sample Output
1 1 1
3 2 1
Author
8600
Source
Recommend
LL
题目的大概意思就是记录每个气球的涂色次数 这里如果单独的去处理每个元素 恭喜你 tle
这里用线段树的思想 记录每一段被涂过的次数 然后最后从上向下找的时候 累加起来（子随父）
搞清这一点 这道题目就是一道简单的线段树的题目了 ps（这道题目让我对节点 下标 以及线段树的组成有了更深的理解----- 下标1代表第一大段 即原始段 2代表第一左字段 依次类推）
#include<cstdio>
#include<iostream>
#define maxn 1000010
using namespace std;
struct node
{
int l,r,num;
}stu[maxn*3 ];
int n,x,y;
void buildtree(int i,int l,int r)//i为线段树的节点
{
stu[i].l=l;
stu[i].r=r;
stu[i].num=0;//二分
if(l==r) return;
buildtree(i*2,l,(l+r)/2);
buildtree(i*2+1,(l+r)/2+1,r);
}
void updata(int x,int y,int i)//有点询问的意思
{
int l=stu[i].l;
int r=stu[i].r;
int mid=(l+r)/2;
if(l==x&&r==y)//把单个的元素涂色 看成一层的元素涂色
{
stu[i].num++;
return;
}
if(y<=mid) updata(x,y,i*2); //要掌握这个基本的搜索的过程 不断的分解
else if(x>mid) updata(x,y,i*2+1);
else
{
updata(x,mid,i*2);
updata(mid+1,y,i*2+1);
}
}
void que(int pos,int sum)//区分节点值 与下标 //这里的sum就是累加项目了 不断的进行累加 直到区间长度为一为止
{
int l=stu[pos].l;
int r=stu[pos].r;
int mid=(l+r)/2;
if(l==r)
{
if(l==1) printf("%d",stu[pos].num+sum);
else printf(" %d",stu[pos].num+sum);
return;
}
que(pos*2,stu[pos].num+sum);
que(pos*2+1,stu[pos].num+sum);
}
int main()
{
while(cin>>n)
{
if(n==0) break;
buildtree(1,1,n); while(n--)
{
cin>>x>>y;
updata(x,y,1);
}
que(1,0);
cout<<endl;
}
return 0;
}