首页 > 代码库 > cdoj 1256 昊昊爱运动 预处理

cdoj 1256 昊昊爱运动 预处理

2024-08-11 21:53:59   220人阅读

昊昊爱运动

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

Sample InputSample Output
5 31 2 3 2 231 42 41 5
323

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+10,M=4e6+10,inf=1e9+10;int sum[N][N];int a[N];int main(){    int n,m,t;    scanf("%d%d",&n,&m);    for(int i=1; i<=n; i++)        scanf("%d",&a[i]);    for(int i=1; i<=n; i++)    {        for(t=1; t<=m; t++)            sum[t][i]=sum[t][i-1];        sum[a[i]][i]=sum[a[i]][i-1]+1;    }    int q;    scanf("%d",&q);    while(q--)    {        int l,r,ans=0;        scanf("%d%d",&l,&r);        for(int i=1;i<=m;i++)        if(sum[i][r]-sum[i][l-1]>0)        ans++;        printf("%d\n",ans);    }    return 0;}

 

cdoj 1256 昊昊爱运动 预处理


联系
我们