自动搬运

查看原文

来自洛谷，原作者为

	无名之雾 I LOVE KaFKa forever

搬运于2025-08-24 22:56:34，当前版本为作者最后更新于2024-03-30 13:16:32，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

求出 $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;
}