题解：P10288 [GESP样题 八级] 区间

· · 题解

题意

求出 x 在 r 到 l 中的出现次数。

30 pts

显然只需要写一个暴力去统计 x 的出现次数即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
inline void write(int x){
    if(x==0){putchar('0');return;}
    int len=0,k1=x,c[10005];
    if(k1<0)k1=-k1,putchar('-');
    while(k1)c[len++]=k1%10+'0',k1/=10;
    while(len--)putchar(c[len]);
}
int a[100005];
signed main(){ 
    int t=read();
    while(t--){ 
        int n=read();
        for(int i=1;i<=n;i++)a[i]=read();
        int q=read();
        while(q--){
            int l=read(),r=read(),x=read();
            int cnt=0;
            for(int i=l;i<=r;i++){
                if(a[i]==x)cnt++;
            }
            cout<<cnt<<"\n";
        }
    } 
    return 0;
}

60 pts

不难想到可以用一个 vector 存储 每种数字出现的位置。

#include<bits/stdc++.h>
using namespace std;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
inline void write(int x){
    if(x==0){putchar('0');return;}
    int len=0,k1=x,c[10005];
    if(k1<0)k1=-k1,putchar('-');
    while(k1)c[len++]=k1%10+'0',k1/=10;
    while(len--)putchar(c[len]);
}
const int N=1e5+5;
int a[N];
signed main(){ 
    int t=read();
    while(t--){ 
        vector<int>b[N];
        int n=read();
        for(int i=1;i<=n;i++){
            a[i]=read();
            b[a[i]].push_back(i);
        }
        int q=read();
        while(q--){
            int l=read(),r=read(),x=read();
            int cnt=0;
            for(int i=0;i<b[x].size();i++){
                if(b[x][i]>=l&&b[x][i]<=r)cnt++;
            }
            cout<<cnt<<"\n";
        }
    } 
    return 0;
}

100 pts

观察数据范围，发现 a_i\le10^9 单纯 vector 存储会爆掉。所以可以采用 map 套 vector 来解决。

同时在对于 数字出现次数进行查找时，采用二分的方法降低复杂度。可以直接使用 lower_bound 与 upper_bound。

#include<bits/stdc++.h>
using namespace std;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
inline void write(int x){
    if(x==0){putchar('0');return;}
    int len=0,k1=x,c[10005];
    if(k1<0)k1=-k1,putchar('-');
    while(k1)c[len++]=k1%10+'0',k1/=10;
    while(len--)putchar(c[len]);
}
const int N=1e5+5;
map<int,vector<int> >mp;
signed main(){ 
    int t=read();
    while(t--){ 
        mp.clear();
        int n=read();
        for(int i=1;i<=n;i++){
            int a=read();
            mp[a].push_back(i);
        }
        int q=read();
        while(q--){
            int l=read(),r=read(),x=read();
            int cnt=upper_bound(mp[x].begin(),mp[x].end(),r)-lower_bound(mp[x].begin(),mp[x].end(),l);
            write(cnt),puts("");
        }
    } 
    return 0;
}