hdu3333区间统计

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

题目大意：求一个区间内不重复数字的和，例如1 1 1 3，区间[1,4]的和为4。

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.print("Case " + i + ": ");new Task().solve(in, out); }out.flush() ; }}class  Task{static int N = 30002 ;static long[] sum = new long[N<<2] ;static int[] num = new int[N] ;static long[] answer = new long[100002] ;void  update(int i , long val , int l , int r , int t){if(l == r){sum[t] += val ; return ;}int m = (l + r) >> 1 ;if(i <= m) update(i, val, l, m, t<<1) ;else  update(i, val, m+1, r, t<<1|1) ;sum[t] = sum[t<<1] + sum[t<<1|1] ;}long  ask(int L , int R , int l , int r , int t){if(L <= l  && r <= R) return sum[t] ;long s = 0 ;int m = (l + r) >> 1 ;if(L <= m) s += ask(L , R , l, m, t<<1) ;if(R > m)  s += ask(L , R , m+1, r, t<<1|1) ;return s ;}static class Query implements Comparable<Query>{int left ;int right ;int id ;public Query(int left , int right , int id){this.left = left ;this.right = right ;this.id = id ;}public int compareTo(Query o) {return Integer.compare(right, o.right) ;}}public void solve(InputReader in , PrintWriter out) throws IOException{HashMap<Integer, Integer> hash = new HashMap<Integer, Integer>() ;int n = in.nextInt() ;for(int i = 1 ; i <= n ; i++) num[i] = in.nextInt() ;int m = in.nextInt() ;Query[] q = new Query[m] ;for(int i = 0 ; i < m ; i++)q[i] = new Query(in.nextInt(), in.nextInt(), i) ;Arrays.sort(q) ;Arrays.fill(sum, 0)  ;int pos = 1 ;for(int i = 0 ; i < m ; i++){for( ; pos <= n && pos <= q[i].right ; pos++){if(hash.get(num[pos]) != null)update(hash.get(num[pos]), -num[pos], 1, n, 1) ;hash.put(num[pos], pos) ;update(pos, num[pos], 1, n, 1) ;}answer[q[i].id] = ask(q[i].left, q[i].right, 1, n, 1) ;}for(int i = 0 ; 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());}}

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

---