HDU 1556 Color the ball （树状数组+普通数组）

来源：未知责任编辑：责任编辑发表时间:2013-11-17 14:34　点击:次

Time Limit: 9000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) p>Total Submission(s): 6323 Accepted Submission(s): 3343

p>Problem Description

p>N个气球排成一排，从左到右依次编号为1,2,3....N.每次给定2个整数a b(a <= b),lele便为骑上他的“小飞鸽"牌电动车从气球a开始到气球b依次给每个气球涂一次颜色。但是N次以后lele已经忘记了第I个气球已经涂过几次颜色了，你能帮他算出每个气球被涂过几次颜色吗？

p>Input

p>每个测试实例第一行为一个整数N,(N <= 100000).接下来的N行，每行包括2个整数a b(1 <= a <= b <= N)。

p>当N = 0，输入结束。

p>Output

p>每个测试实例输出一行，包括N个整数，第I个数代表第I个气球总共被涂色的次数。

p>Sample Input

p>3

p>1 1

p>2 2

p>3 3

p>3

p>1 1

p>1 2

p>1 3

p>0

p>Sample Output

p>1 1 1

p>3 2 1

p>普通方法： p>

import java.io.*;  
import java.util.*;  
public class Main {  
    int aa[]=new int[100100];  
    public static void main(String[] args) throws IOException{  
        new Main().work();  
    }  
    void work() throws IOException{  
        BufferedReader bu=new BufferedReader(new InputStreamReader(System.in));  
        int n=Integer.parseInt(bu.readLine());  
        while(n!=0){  
            Arrays.fill(aa, 0);  
            for(int i=0;i<n;i++){  
                String str[]=bu.readLine().split(" ");  
                int a=Integer.parseInt(str[0]);  
                int b=Integer.parseInt(str[1]);  
                aa[a]++;  
                aa[b+1]--;  
            }  
            int ans=aa[1];  
            System.out.print(ans);  
            for(int i=2;i<=n;i++){  
                ans+=aa[i];  
                System.out.print(" "+ans);  
                  
            }  
            System.out.println();  
            n=Integer.parseInt(bu.readLine());  
        }  
    }  
}

树状数组

 

 
 
import java.io.*;  
import java.util.*;  
public class Main {  
    int[] c=new int[100110];  
    int[] a=new int[100110];  
    int n,id;  
    public static void main(String[] args) throws IOException{  
        new Main().work();  
    }  
    void work() throws IOException{  
        BufferedReader bu=new BufferedReader(new InputStreamReader(System.in));  
        n=Integer.parseInt(bu.readLine());  
        while(n!=0){  
            Arrays.fill(c, 0);  
            for(int i=0;i<n;i++){  
                String str[]=bu.readLine().split(" ");  
                int aa=Integer.parseInt(str[0]);  
                int bb=Integer.parseInt(str[1]);  
                plus(aa,1);  
                plus(bb+1,-1);  
            }  
              
            System.out.print(getSum(1));  
            for(int i=2;i<=n;i++){  
                System.out.print(" "+getSum(i));  
            }  
              
            System.out.println();  
            n=Integer.parseInt(bu.readLine());  
        }  
    }  
      
    int lowbit(int x){  
        return x&(-x);  
    }  
    //相加  
    void plus(int pos,int x){  
        while(pos<=n){  
            c[pos]+=x;  
            pos+=lowbit(pos);  
        }  
    }  
    //求和  
    int getSum(int x){  
        int sum=0;  
        while(x>0){  
            sum+=c[x];  
            x-=lowbit(x);  
        }  
        return sum;  
    }  
}