package poj_2352;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;

public class Main {
	public static final int max=40000;
	public static int[] c=new int[max];
	
	public static int lowbit(int x) {
		return x&(-x);
	}
	
	public static void add(int x,int y) {
		for(int i=x;i<=max;i+=lowbit(i))
			c[i]+=y;
	}
	
	public static int ask(int x) {
		int ans=0;
		
		for(int i=x;i>0;i-=lowbit(i))
			ans+=c[i];
		
		return ans;
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		InputReader sc=new InputReader(System.in);
		PrintWriter out=new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
		int n=sc.nextInt();
		int[] res=new int[n];
		
		for(int i=0;i<n;i++) {
			int x=sc.nextInt()+1;
			int y=sc.nextInt();
			int temp=ask(x);
			res[temp]++;
			add(x,1);
		}
		for(int i=0;i<n;i++)
			out.println(res[i]);
		out.flush();
	}
}


class InputReader{
	StreamTokenizer sc;
	
	public InputReader(InputStream stream) {
		sc=new StreamTokenizer(new BufferedReader(new InputStreamReader(stream)));
		sc.ordinaryChars(33,126);
		sc.wordChars(33,126);
	}
	
	public String next() throws IOException {
		sc.nextToken();
		return sc.sval;
	}
	
	public int nextInt() throws NumberFormatException, IOException {
		return Integer.parseInt(next());
	}
	
	public long nextLong() throws NumberFormatException, IOException {
		return Long.parseLong(next());
	}
	
	public boolean hasNext() throws IOException {
		int res=sc.nextToken();
		sc.pushBack();
		return res!=sc.TT_EOF;
	}
}

• Re:Java 树状数组 (1967) 514963983 2019-05-18 21:21:06