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

Color the ball

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

Problem DescriptionInputOutputSample InputSample Outputimport 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;}}