CDOJ 1256 二维前缀和处理

昊昊喜欢运动

他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

Sample Input	Sample Output
5 3 1 2 3 2 2 3 1 4 2 4 1 5	3 2 3

Hint

Source

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

 

题意：询问任意区间内 参加活动的种类

 

题解：二维前缀和 

        cout T

#include<bits/stdc++.h>
#define ll __int64
#define mod 1e9+7
#define PI acos(-1.0)
#define bug(x) printf("%%%%%%%%%%%%%",x);
using namespace std;
int n,m;
int a[2005];
int mp[2005][105];
int l,r;
int q;
int main()
{
    scanf("%d %d",&n,&m);
    int exm=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            mp[i][j]=mp[i-1][j];
        }
        scanf("%d",&a[i]);
        mp[i][a[i]]++;
    }
    scanf("%d",&q);
    for(int i=1;i<=q;i++)
    {
        scanf("%d %d",&l,&r);
        int flag=0;
        for(int j=1;j<=m;j++)
        {
            if((mp[r][j]-mp[l-1][j])>0)
                flag++;
        }
        printf("%d
",flag);
    }

    return 0;
}