Color the ball

Time Limit: 9000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5650 Accepted Submission(s): 3009

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

Sample Output

1 1 1
3 2 1

　　在网上搜到的线段树的题目，于是就做了，这一题如果直接模拟的话目测会超时。

　　这一题我用了一个lazy的变量，在每一层上都装了lazy，一开始如果是大范围加1的话直接在lazy上加，只有在要求每一个单元的值的时候才把lazy加上去，这样可以把多次重复的动作化为一步。不过时间花得比较长。

上代码：

 1 #include <stdio.h>
 2 #include <string.h>
 3 #define MAX (100000+10)
 4 using namespace std;
 5 
 6 typedef struct
 7 {
 8     int l,r;
 9     int t;
10 }Node;
11 
12 Node N[MAX<<2];
13 
14 int f;
15 
16 void build(int l,int r,int p)
17 {
18     N[p].l=l;
19     N[p].r=r;
20     N[p].t=0;
21     if(l==r) return;
22     int mid=(l+r)>>1;
23     build(l,mid,p<<1);
24     build(mid+1,r,(p<<1)+1);
25 }
26 
27 void adjust(int a,int b,int p)         /*要操作的总边界在每一次调用函数的时候都不会改变，只改变p*/
28 {
29     /*当当前的根节点完全包含在总边界里面的时候*/
30     if(a<=N[p].l && N[p].r<=b) {N[p].t++;return ;}
31     /*当总边界并没有完全包含当前的根节点的时候*/
32     int mid=(N[p].l+N[p].r)>>1;
33     if(mid<a) adjust(a,b,(p<<1)+1);  /*如果总边界只在右半部分*/
34     else if(mid>=b)  adjust(a,b,(p<<1)); /*如果总边界只在左半部分*/
35     else                             /*如果总边界在左半部分和右半部分都有*/
36     {
37         adjust(a,b,p<<1);
38         adjust(a,b,(p<<1)+1);
39 
40     }
41 }
42 
43 void Tra(int a,int b,int p,int count)
44 {
45     count+=N[p].t;
46     if(N[p].l==N[p].r) {if(f++) printf(" "); printf("%d",count);}
47     else
48     {
49         int mid=(a+b)>>1;
50         Tra(a,mid,p<<1,count);
51         Tra(mid+1,b,(p<<1)+1,count);
52     }
53 }
54 
55 int main()
56 {
57     int n,i,a,b;
58     //freopen("data.txt","r",stdin);
59     while(scanf("%d",&n),n)
60     {
61         memset(N,0,sizeof(N));
62         build(1,n,1);
63         for(i=0;i<n;i++)
64         {
65             scanf("%d %d",&a,&b);
66             adjust(a,b,1);
67         }
68         f=0;
69         Tra(1,n,1,0);
70         printf("
");
71     }
72     return 0;
73 }

1556