自动搬运

查看原文

来自洛谷，原作者为

	MZY666 「It's time to see what I can do_To test the limits and break through.」

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

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

以下是正文

原题传送门。在我的博客中食用更佳。

题意概括：

先输入两个数 $N$，$Q$，分别表示牛个数和询问个数。

接下来先输入每只牛的类型，随后再输入 $Q$ 组询问，每组询问是两个数：$a$ 和 $b$，表示询问这两个牛的编号之间每种牛各有多少只。

要求输出每组询问的结果。记得换行。

思路：前缀和。如何实现呢？

在题中有这样一句话：

每个询问希望求出某个区间内每个品种奶牛的数量。

划重点：区间内。那么我们就可以用三个一位数组 $x[i],y[i],z[i]$来存储每一种奶牛到第 $i$ 头时的总数量。

这样一来，每次用后面读入牛的编号所对应的个数减去前面读入牛的编号-1所对应的个数即可算出区间和（前缀和）了，即：

x_sum=x[b]-x[a-1],y_sum=y[b]-y[a-1],z_sum=z[b]-z[a-1].

是时候上完整代码了！

#include<bits/stdc++.h>//万能头文件好
#define ll long long//个人习惯
using namespace std;
ll x[100005],y[100005],z[100005];//数组最好开大个5个左右，以防万一
int main(){
	ll n,q,i,a,b;//习惯先把变量放这，数组放上面
	scanf("%lld%lld",&n,&q);//读入N和Q，为了方便都写的n和q.
	for(i=1;i<=n;i++){
		scanf("%lld",&a);//读入a，此时的a用于暂存当前品种 
		x[i]=x[i-1];y[i]=y[i-1];z[i]=z[i-1];
        //把之前的每一种类型的奶牛先加上来，稍稍压行
		switch(a){//判断这只牛的类型
			case 1:
				x[i]++;
				break;
			case 2:
				y[i]++;
				break;
			case 3:
				z[i]++;
				break;
		}//把这只牛加上去
	}
	for(i=1;i<=q;i++){//开始读入询问
		scanf("%lld%lld",&a,&b);//读入题目描述中的a和b.
		printf("%lld %lld %lld\n",x[b]-x[a-1],y[b]-y[a-1],z[b]-z[a-1]);
        //这一步前面有单独分析。
	}
	return 0;//over
}

还是很简单的把。本蒟蒻还不会树状数组（好像有大佬这样做），如有需要请移步他处。

完结撒花~