Color the ballTime Limit: 9000/3000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 11387Accepted Submission(s): 5680
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
31 12 23 331 11 21 30
Sample Output
1 1 13 2 1
Author
8600
Source
Recommend
LL|We have carefully selected several similar problems for you:15421698154133973333
思路：题意很容易懂只是用一般的办法会超时，所以需要用到一些省时间的算法，树状数组和线段树就恰恰符合这个条件
树状数组
#include<iostream>#include<algorithm>#include<stdio.h>#include<string.h>#include<string.h>#include<stdlib.h>using namespace std;int a[100010];int n;int lowbit(int x){return x&(-x);}void build(int x,int y){while(x<=n){a[x] += y;x += lowbit(x);}}int sum(int x)//求和{int s=0;while(x>0){s=s+a[x];x=x-lowbit(x);}return s;}int main(){while(scanf("%d",&n)!=EOF){if(n == 0){break;}int x,y;memset(a,0,sizeof(a));for(int i=1;i<=n;i++){scanf("%d%d",&x,&y);build(x,1);build(y+1,-1);}for(int i=1;i<=n;i++){if(i == n){printf("%d\n",sum(i));}else{printf("%d ",sum(i));}}}return 0;}
线段树：
#include<iostream>#include<algorithm>#include<stdio.h>#include<string.h>#include<string.h>#include<stdlib.h>using namespace std;const int maxn = 100010;struct node{int l;int r;int lz;int ans;} q[maxn<<4];int n;void pushdown(int rt,int lr){if(q[rt].lz){q[rt<<1].ans += (lr-(lr>>1))*q[rt].lz;q[rt<<1|1].ans += (lr>>1)*q[rt].lz;q[rt<<1].lz += q[rt].lz;q[rt<<1|1].lz += q[rt].lz;q[rt].lz = 0;}}void build(int l,int r,int rt){q[rt].l = l;q[rt].r = r;q[rt].ans = 0;q[rt].lz = 0;if(l == r){return ;}int mid = (l+r)>>1;build(l,mid,rt<<1);build(mid+1,r,rt<<1|1);q[rt].ans = q[rt<<1].ans + q[rt<<1|1].ans;}void updata(int ll,int rr,int k,int l,int r,int rt){if(ll>r || rr<l){return ;}if(ll<=l && rr>=r){q[rt].ans = q[rt].ans + (r-l+1)*k;q[rt].lz += k;return ;}pushdown(rt,r-l+1);int mid = (l+r)>>1;if(mid>=ll){updata(ll,rr,k,l,mid,rt<<1);}if(rr>mid){updata(ll,rr,k,mid+1,r,rt<<1|1);}q[rt].ans = q[rt<<1].ans + q[rt<<1|1].ans;}void qurry(int l,int r,int rt){if(l == r){if(l == n){printf("%d\n",q[rt].ans);}else{printf("%d ",q[rt].ans);}return ;}pushdown(rt,r-l+1);int mid = (l+r)>>1;qurry(l,mid,rt<<1);qurry(mid+1,r,rt<<1|1);}int main(){while(scanf("%d",&n)!=EOF){if(n == 0){break;}build(1,n,1);int x,y;for(int i=0; i<n; i++){scanf("%d%d",&x,&y);updata(x,y,1,1,n,1);}qurry(1,n,1);}return 0;}
世上最累人的事，莫过於虚伪的过日子
