NC24046. [USACO 2015 Dec S]Breed Counting
描述
输入描述
The first line of input contains NN and QQ (1≤N≤100,0001≤N≤100,000, 1≤Q≤100,0001≤Q≤100,000).
The next NN lines contain an integer that is either 1, 2, or 3, giving the breed ID of a single cow in the ordering.
The next QQ lines describe a query in the form of two integers a,ba,b (a≤ba≤b).
输出描述
For each of the QQ queries (a,b)(a,b), print a line containing three numbers: the number of cows numbered a…ba…b that are Holsteins (breed 1), Guernseys (breed 2), and Jerseys (breed 3).
示例1
输入:
6 3 2 1 1 3 2 1 1 6 3 3 2 4
输出:
3 2 1 1 0 0 2 0 1
C++(clang++11) 解法, 执行用时: 252ms, 内存消耗: 3324K, 提交时间: 2020-12-12 18:15:02
#include<bits/stdc++.h>
using namespace std;
const int maxn=100009;
int n,Tn;
int sum[4][maxn];
int main(){
cin>>n>>Tn;
for(int i=1;i<=n;++i){
int x;cin>>x;
for(int j=1;j<=3;++j)sum[j][i]=sum[j][i-1];
sum[x][i]++;
}
while(Tn--){
int l,r;cin>>l>>r;
for(int j=1;j<=3;++j){
printf("%d ",sum[j][r]-sum[j][l-1]);
}
printf("\n");
}
return 0;
}
Python3(3.9) 解法, 执行用时: 938ms, 内存消耗: 26716K, 提交时间: 2020-12-15 16:47:21
NN,QQ=map(int,input().split())
arr=[int(input()) for i in range(NN)]
prearr=[[0,0,0] for i in range(NN+1)]
for i in range(NN) :
prearr[i+1]=prearr[i].copy()
prearr[i+1][arr[i]-1]+=1
# print(prearr)
for i in range(QQ) :
a,b=map(int,input().split())
end=prearr[b]
start=prearr[a-1]
print(end[0]-start[0],end[1]-start[1],end[2]-start[2])