看花

	#include <iostream>
#include <set>
#include <vector>
#include <unordered_set>
using namespace std;
int main(){
    int m,n;
    while(cin >> n >> m){
        vector<int> a(n);
        for(int i = 0; i < n; ++i){
            scanf("%d" , &a[i]);
        }
        vector<vector<int>> ans(n, vector<int>(n, 1)); // ans[i][j] 表示从时间[i + 1， j + 1]看了几种花，其中i <= j;
        for(int i = 0; i < n; ++i){
            unordered_set<int> set_a;
            set_a.insert(a[i]);
            for(int j = i; j < n; ++j){
                set_a.insert(a[j]);
                ans[i][j] = set_a.size();
            }
        }
        int Q;
        cin >> Q;
        while(Q--){
            int l, r;
            scanf("%d %d" , &l, &r);
            //printf("%d\n",ans[l - 1][r - 1]);
            //cin >> l >> r;
            cout << ans[l - 1][r - 1] << endl;
        }
    }
    return 0;
}

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int []A = new int [n];
        int []B = new int [m];
        for(int i=0;i<n;i++){
            A[i] = sc.nextInt();
        }
        int Q = sc.nextInt();
        int [][]a = new int [Q][2];
        for(int i=0;i<Q;i++){
            a[i][0] = sc.nextInt();
            a[i][1] = sc.nextInt();
        }
        
        
        for(int i=0;i<Q;i++){
        	int t=0;
        	for(int j=a[i][0]-1;j<=a[i][1]-1;j++){
        		int dd = A[j];
                if(B[dd-1]!=i+1){
                    B[dd-1]=i+1;
                    t++;
                }
        		
        	}
        	System.out.println(t);
        	
        	}
  
        }
    }

本题经典问题是查询区间不同数量，简单做法是树状数组求法 （还有***树做法

先对询问进行离线。 然后按照右端点从小到大排序。

1. 树状数组统计答案，对于第一次出现直接加1
2. 第二次出现，先减去上一次的影响，在加1

显然数据范围可以开到 n, k 可以开到 1e6，不然暴力预处理就过了

#include
using namespace std;
const int N = 1e6 + 5;
int a[N];
struct Bit {
    int c[N];
    int n;
    void init() { memset(c, 0, sizeof(c)); }
    int lowbits(int x) { return x & -x;}
    void add(int i, int v) {
        for(; i <= n; i += lowbits(i)) c[i] += v;
    }
    int get(int i) {
        int ans = 0;
        if(i <= 0) return 0;
        for(; i > 0; i -= lowbits(i)) ans += c[i];
        return ans;
    }
}B;
struct node {
    int l, r, id;
    bool friend operator < (node a, node b) {
        return a.r < b.r;
    }
}b[N];
int id[N], ans[N];
int main()
{
    /*
    #ifndef ONLINE_JUDGE
    freopen("a.txt", "r", stdin);
    #endif // ONLINE_JUDGE
    */
    int n, m, k;
    scanf("%d %d", &n, &k);
    B.init();
    B.n = n;
    memset(id, -1, sizeof(id));
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    scanf("%d", &m);
    for(int i = 1; i <= m; i++) {
        int l, r;
        scanf("%d %d", &l, &r);
        b[i] = {l, r, i};
    }
    sort(b + 1, b + m + 1);
    int j = 1, sum = 0;
    for(int i = 1; i <= n; i++) {
        if(id[a[i]] != -1) B.add(id[a[i]], -1), sum--;
        id[a[i]] = i; sum++;
        B.add(i, 1);
        while(j <= m && b[j].r == i) {
            int tmp = sum - B.get(b[j].l-1);
            ans[b[j].id] = tmp;
            j++;
        }
    }
    for(int i = 1; i <= m; i++) {
        printf("%d\n", ans[i]);
    }
    return 0;
}

import java.util.*;
public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int[] a = new int[n];
//		         读取看的次数的种类
		for(int i=0;i<n;i++) {
			a[i]= sc.nextInt(); 
		}
		int q = sc.nextInt();
		for(int i=0;i<q;i++) {
			int l = sc.nextInt();
			int r =sc.nextInt();
			System.out.println(test(l,r,a));

		}
	}
	public static int test(int l,int r,int[]a) {
		Set<Integer> temp = new HashSet<>();
		for(int i=l-1;i<r;i++) {
			temp.add(a[i]);
		}
		return temp.size();
	}
}
 

n,m=map(int,input().strip().split())
lt=list(map(int,input().strip().split()))
Q=int(input())
for i in range(Q):
    l,r=map(int,input().strip().split())
    print(len(set(lt[l-1:r])))

//用深度优先搜索的简单解法，虽然超时了，但可以看看方法，代码如下。 
#include <stdio.h>						
int n,m,q,l,r;			//题目数据 
int t,total=0;		 
int a[2019];
int v[2019]={0};				//用来标记是否被访问过的数组 
void dfs(int l,int r){
	if(l==r){				//递归出口，当左等于右时跳出 ，此时在处理最后一个数 
		if(v[l]==0)						 
			printf("%d\n",total+1);	//最后一个数若未访问总数加一 
		else
			printf("%d\n",total);	//最后一个数若已访问总数不变 
			
		total=0;			//数据清零 ，准备处理下一组问题 
		for(int i=1;i<=n;i++)
		v[i]=0;
		return;
	}
	for(int k=l;k<=r;k++){			
		if(a[k]==a[l]&&v[k]==0){	//标记与第一个数字相等且未被访问过的数字 
			v[k]=1;						
			t=2;			//如果找到新的未被访问的数字的话让t=2
		}
	}
	if(t==2){				//如果t=2，说明找到新的数字，总数++,再把t初始化 
		total++;
		t=0;
	}
	dfs(l+1,r);				//向右寻找下一个 
}
int main(void){
	scanf("%d%d",&n,&m);			//输入m,n,a[i] 
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}								
	scanf("%d",&q);				//输入Q 
	for(int i=1;i<=q;i++){
		scanf("%d%d",&l,&r);		//输入l，r 
		dfs(l,r);			//搜索开始 
	}
	return 0;
}

86.6% 提示超时，大佬们帮忙看看如何优化。
import java.util.*;
public class Main{
    public static void main(String[] args) {
        Scanner sc= new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        int[] a=new int[n];
        for(int i=0;i<n;i++){
            a[i]=sc.nextInt();
        }
        int Q=sc.nextInt();
        while (Q!=0){
            int l=sc.nextInt();
            int r=sc.nextInt();
            cal(a,l,r,m);
            Q--;
        }
    }
    private static void cal(int[] a, int l, int r, int m){
        int left=l-1;
        int right=r-1;
        int len=right-left+1;
        int[] num=new int[len];
        System.arraycopy(a, 0 + left, num, 0, len);
        Arrays.sort(num);
        int count=0;
        for(int i=0;i<len-1;i++){
            if(num[i]!=num[i+1]){
                count++;
            }
        }
        System.out.println(count+1);

    }
}

import java.util.Scanner;

public class Flower {

	public static void main(String[] args) {
		Scanner scanner=new Scanner(System.in);
		int n=0,m=0;
		n=scanner.nextInt();
		m=scanner.nextInt();
		int[] a=new int[n+1];
		int[] b=new int[m+1];
		
		for(int i=1;i<=n;i++) {
			a[i]=scanner.nextInt();	
		}
		int q=scanner.nextInt();
		int[] c=new int[q];
		for(int i=0;i<q;i++) {
			for(int k=0;k<m+1;k++) {
				b[k]=0;
			}
			int t=0;
			int l=scanner.nextInt();
			int r=scanner.nextInt();
			for(int j=l;j<=r;j++) {
				if(b[a[j]]!=1) {
				t++;
				b[a[j]]=1;
				}
			}
			c[i]=t;
		}
		for(int i=0;i<q;i++)
		{
			System.out.println(c[i]);
		}
	}

}

# 通过87%  最后超内存了  之前的思路是遍历一遍，用dict 保存当前为止出现过得花以及对应的次数
# 超时； 现在是2维遍历，维护一个二维矩阵，表示i到j的种类数，也只通过了87%
import sys
lines = sys.stdin.readlines()
n,m = [int(n) for n in lines[0].strip().split()]
c = [int(n) for n in lines[1].strip().split()]
qNum = int(lines[2].strip())
q = []
for i in range(3,len(lines)):
    q.append([int(m) for m in lines[i].strip().split()])

res = [[0 for i in range(n)] for j in range(n)]
for i in range(len(c)):
    s = set()
    for j in range(i,n):
        s.add(c[j])
        res[i][j] = len(s)

for quary in q:
    l,r = quary[0],quary[1]
    print(res[l-1][r-1])