Codeforces - 368B - Sereja and Suffixes

Question

题目大意

给你两个数 n 、 m ，以及 n 个数的数组 a[] ，然后给你 m 个查询，每个查询输入一个数 l[i] ，问你在 a 数组中， a[l[i]-1]~a[n-1] 位置有多少个不相同的数。

解析

很简单的 dp 题，从后往前遍历，关键在于使用一个 boolean 数组当前遍历的数有没有出现过。 dp[i] 代表的是 i~n 之间有多少个不同的数。

import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner cin = new Scanner(new BufferedInputStream(System.in));
        int n = cin.nextInt();
        int m = cin.nextInt();
        int[] a = new int[n];
        int[] l = new int[m+1];
        boolean[] isAppera = new boolean[500001];
        int[] dp = new int[n];
        for(int i = 0; i < n; i++)
            a[i] = cin.nextInt();
        for(int i = 0; i < m; i++)
            l[i] = cin.nextInt();
        dp[n-1] = 1;
        isAppera[a[n-1]] = true;
        for(int i = n-2; i >= 0; i--){
            dp[i] = !isAppera[a[i]] ? dp[i+1]+1 : dp[i+1];
            isAppera[a[i]] = true;
        }
        for(int i = 0; i < m; i++)
            System.out.println(dp[l[i]-1]);
    }
}

题目链接

https://codeforces.com/problemset/problem/368/B