昊昊爱运动

Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)

昊昊喜欢运动

他NN天内会参加MM种运动(每种运动用一个[1,m][1,m]的整数表示)

舍友有QQ个问题

问昊昊第ll天到第rr天参加了多少种不同的运动

Input

输入两个数NN, MM (1≤N≤20001≤N≤2000, 1≤M≤1001≤M≤100);

输入NN个数aiai表示在第i天昊昊做了第aiai类型的运动;

输入一个数QQ(1≤Q≤1061≤Q≤106);

输入QQ行每行两个数 ll, rr(1≤l≤r≤n1≤l≤r≤n);

Output

一共QQ行

每一行输出一个数表示昊昊在第ll天到第rr天一共做了多少种活动

Sample input and output

Source

第七届ACM趣味程序设计竞赛第二场（正式赛）

思路：一眼不是离线树状数组，然后看到数据比较小，n*n*m超时；

　　　预处理n*n，Q*m可以水过；

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define pi (4*atan(1.0))

const int N=2e3+,M=4e6+,inf=1e9+;

int sum[N][N];

int a[N];

int main()

{

    int n,m,t;

    scanf("%d%d",&n,&m);

    for(int i=; i<=n; i++)

        scanf("%d",&a[i]);

    for(int i=; i<=n; i++)

    {

        for(t=; t<=m; t++)

            sum[t][i]=sum[t][i-];

        sum[a[i]][i]=sum[a[i]][i-]+;

    }

    int q;

    scanf("%d",&q);

    while(q--)

    {

        int l,r,ans=;

        scanf("%d%d",&l,&r);

        for(int i=;i<=m;i++)

        if(sum[i][r]-sum[i][l-]>)

        ans++;

        printf("%d\n",ans);

    }

    return ;

}

运动