hdu4417区间统计

本文主要是介绍hdu4417区间统计，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

给你一个数列{An}，然后有m次查询，每次查询一段区间 [l,r] <= h 的值的个数。

import java.io.BufferedInputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.NavigableSet;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;
import java.util.SortedSet;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.TreeSet;public class Main {public static void main(String[] args) throws IOException{StreamTokenizer cin = new StreamTokenizer(new BufferedInputStream(System.in)); InputReader in = new InputReader(System.in)  ;PrintWriter out = new PrintWriter(System.out) ;int t = in.nextInt() ;for(int i = 1 ; i <= t ; i++){out.println("Case " + i + ":");new Task().solve(in, out); }out.flush() ; }}class  Task{static int N = 100008 ;static class Wall implements Comparable<Wall>{int  high ;int  id ;public Wall(int high , int id){this.high = high ;this.id = id ;}public int compareTo(Wall o) {return Integer.compare(high, o.high) ;}} static class Ask extends Wall{int left ;int right ;Ask(int left , int right , int high , int id){super(high , id) ;this.left = left ;this.right = right ;}} static  Wall[] walls = new Wall[N] ;static  Ask[] asks = new Ask[N] ;static  int[] answer = new int[N] ;static  int[] c = new int[N] ;int   lowbit(int x){return x & (-x) ;}void  add(int i){for(; i <= n ; i += lowbit(i)) c[i] += 1 ; }int   sum(int i){int s = 0 ;for(; i > 0 ; i -= lowbit(i)) s += c[i] ;return s  ;}int   sum(int l , int r){return sum(r) - sum(l-1) ;}int  n ;public void solve(InputReader in , PrintWriter out) throws IOException{n = in.nextInt() ;int m = in.nextInt() ;for(int i = 1 ; i <= n ; i++) walls[i] = new Wall(in.nextInt(), i) ;for(int i = 1 ; i <= m ; i++)asks[i] = new Ask(in.nextInt()+1, in.nextInt()+1, in.nextInt(), i) ;Arrays.sort(walls , 1 , 1+n) ;Arrays.sort(asks , 1 , 1+m) ;Arrays.fill(c, 0);int  pos = 1 ;for(int i = 1 ; i <= m ; i++){while(pos <= n && walls[pos].high <= asks[i].high){add(walls[pos].id) ;pos++ ;}answer[asks[i].id] = sum(asks[i].left , asks[i].right) ;}for(int i = 1 ; i <= m ; i++) out.println(answer[i]) ;}}class   InputReader{public BufferedReader  reader;public StringTokenizer  tokenizer;public InputReader(InputStream stream){reader = new BufferedReader(new InputStreamReader(stream), 32768) ;tokenizer = null ;}public String next(){while(tokenizer == null || ! tokenizer.hasMoreTokens()){try{tokenizer = new StringTokenizer(reader.readLine());}catch (IOException e) {throw new RuntimeException(e);}}return tokenizer.nextToken();  }public int  nextInt(){return Integer.parseInt(next());}public long nextLong(){return Long.parseLong(next());}public double nextDouble(){return  Double.parseDouble(next());}}

这篇关于hdu4417区间统计的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---