为了不断优化推荐效果,今日头条每天要存储和处理海量数据。假设有这样一种场景:我们对用户按照它们的注册时间先后来标号,对于一类文章,每个用户都有不同的喜好值,我们会想知道某一段时间内注册的用户(标号相连的一批用户)中,有多少用户对这类文章喜好值为k。因为一些特殊的原因,不会出现一个查询的用户区间完全覆盖另一个查询的用户区间(不存在L1<=L2<=R2<=R1)。
数据范围: , , , 每组查询满足 ,查询的喜好值满足
为了不断优化推荐效果,今日头条每天要存储和处理海量数据。假设有这样一种场景:我们对用户按照它们的注册时间先后来标号,对于一类文章,每个用户都有不同的喜好值,我们会想知道某一段时间内注册的用户(标号相连的一批用户)中,有多少用户对这类文章喜好值为k。因为一些特殊的原因,不会出现一个查询的用户区间完全覆盖另一个查询的用户区间(不存在L1<=L2<=R2<=R1)。
输入: 第1行为n代表用户的个数 第2行为n个整数,第i个代表用户标号为i的用户对某类文章的喜好度 第3行为一个正整数q代表查询的组数 第4行到第(3+q)行,每行包含3个整数l,r,k代表一组查询,即标号为l<=i<=r的用户中对这类文章喜好值为k的用户的个数。 数据范围n <= 300000,q<=300000 k是整型
输出:一共q行,每行一个整数代表喜好值为k的用户的个数
5 1 2 3 3 5 3 1 2 1 2 4 5 3 5 3
1 0 2
样例解释: 有5个用户,喜好值为分别为1、2、3、3、5, 第一组询问对于标号[1,2]的用户喜好值为1的用户的个数是1 第二组询问对于标号[2,4]的用户喜好值为5的用户的个数是0 第三组询问对于标号[3,5]的用户喜好值为3的用户的个数是2
emmm,整了个分块记录每个块内每个喜好值的个数,然后瞎搞了一下就AC了
#include<bits/stdc++.h> using namespace std; const int MAXN = 3e5+5; const int CC = 600; int N,Q; int arr[MAXN]; int L[CC],R[CC],pos[MAXN]; int ans[CC][MAXN]; int getSum(int l,int r,int k){ int res = 0; int lpos = pos[l],rpos = pos[r]; if(lpos == rpos){ for(int i=l;i<=r;i++) res += (arr[i] == k); return res; } for(int i=l;i<=R[lpos];i++) res += (arr[i]==k); for(int i=L[rpos];i<=r;i++) res += (arr[i]==k); for(int i=lpos+1;i<=rpos-1;i++) res += ans[i][k]; return res; } int main() { scanf("%d",&N); for(int i=1;i<=N;i++) scanf("%d",&arr[i]); int cnt = sqrt(N); for(int i=1;i<=cnt;i++){ L[i] = (i-1) * cnt + 1; R[i] = i*cnt; } if(R[cnt] < N){ L[cnt+1] = R[cnt] + 1; R[cnt+1] = N; cnt++; } for(int i=1;i<=cnt;i++) for(int j=L[i];j<=R[i];j++) pos[j] = i; for(int i=1;i<=N;i++) ans[pos[i]][arr[i]]++; scanf("%d",&Q); while(Q--){ int l,r,k; scanf("%d%d%d",&l,&r,&k); printf("%d\n",getSum(l,r,k)); } return 0; }
# Python版 def output(user1,user2,k,kList): selectList = [] for i in range(user1-1,user2): selectList.append(kList[i]) count = 0 for i in selectList: if k == i: count +=1 return count userNum = int(input('请输入用户数量:')) kList = [] for i in range(1,userNum+1): k = int(input('请输入用户{}的喜爱值:'.format(i))) kList.append(k) q = int(input('请输入用户的组数:')) while q > 0: user1 = int(input('请输入起始用户标号:')) user2 = int(input('请输入终止用户标号:')) k = int(input('请输入要判断的k值:')) q -= 1 print(output(user1,user2,k,kList))
水过
#include <bits/stdc++.h>
using namespace std;
map<int, vector<int> >ma;
int n, q, t;
int l, r, k;
int solve(int l, int r, int k) {
if (ma[k].size() == 0) return 0;
auto it1 = lower_bound(ma[k].begin(), ma[k].end(), l);
auto it2 = upper_bound(ma[k].begin(), ma[k].end(), r);
return it2 - it1;
}
int main() {
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> t;
ma[t].push_back(i);
}
cin >> q;
for (int i = 0; i < q; ++i) {
cin >> l >> r >> k;
cout << solve(l, r, k) << endl;
}
return 0;
}
import bisect N = int(input()) L = [[] for i in range(0,300050)] index = [int(i) for i in input().split()] num = 1; for i in range(0,N): L[index[i]].append(num) num=num + 1; Q = int(input()) for i in range(Q): a, b, c = map(int, input().strip().split()) i1 = bisect.bisect_left(L[c], a) i2 = bisect.bisect_right(L[c], b) print(i2-i1)
num_user = int(input()) preferences = list(map(int, input().split())) num_query = int(input()) prefer_dict = {} for i in range(num_user): if preferences[i] not in prefer_dict.keys(): prefer_dict[preferences[i]] = [i] else: prefer_dict[preferences[i]].append(i) for i in range(num_query): line = list(map(int, input().split())) start = line[0] - 1 end = line[1] - 1 score = line[2] count = 0 if score in prefer_dict.keys(): # 先进行判断 indexes = prefer_dict[score] for index in indexes: if start <= index <= end: count += 1 print(count)
import java.util.*; public class Main{ public static void byteDanceSolution1(){ Scanner scanner=new Scanner(System.in); int n=scanner.nextInt(); int[] array=new int[n+1]; Map<Integer,TreeSet<Integer>> mp=new HashMap<>(); for(int i=1;i<=n;++i){ array[i]=scanner.nextInt(); TreeSet<Integer> list=mp.getOrDefault(array[i],new TreeSet<>()); list.add(i); mp.put(array[i],list); } // System.out.println(mp); int q=scanner.nextInt(),l,r,k; List<Integer> ans=new LinkedList<>(); for(int i=0;i<q;++i){ l=scanner.nextInt(); r=scanner.nextInt(); k=scanner.nextInt(); if(mp.containsKey(k)){ ans.add(mp.get(k).subSet(l,r+1).size()); }else{ ans.add(0); } } ans.forEach(System.out::println); } public static void main(String[] args) { byteDanceSolution1(); } }
#include<iostream> usingnamespacestd; intmain(){ intn=0; cin>>n; int*user = newint[n]; for(inti=0;i<n;i++) { cin>>user[i]; } intq=0; cin>>q; while(q--) { intl,r,k; cin>>l>>r>>k; intnum = 0; for(inti=l-1;i<r;i++) { if(user[i] == k) { num++; } } cout<<num<<endl; } return0; }
符号表应用,把喜好值作为key,对应该喜好值的人的集合作为value
比如查询5的时候,直接找到所有喜好值为5的人的集合,遍历集合中哪些人在范围内。
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scan=new Scanner(System.in);
int n=scan.nextInt();
int[] fav=new int[n];
for(int i=0;i<n;i++){
fav[i]=scan.nextInt();
}
Map<Integer,List<Integer>> map=new HashMap<>();
for(int i=0;i<n;i++){
int key=fav[i];
int value=i+1;
if(!map.containsKey(key)){
List<Integer> list=new LinkedList<>();
list.add(value);
map.put(key,list);
}else{
List<Integer> list=map.get(key);
list.add(value);
}
}
int m=scan.nextInt();
Queue<Integer> queue=new LinkedList<>();
for(int i=0;i<m;i++){
int lo=scan.nextInt();
int hi=scan.nextInt();
int des=scan.nextInt();
List<Integer> list=map.get(des);
int count=0;
if(list!=null){
for(Integer integer:list){
if(integer>=lo&&integer<=hi){
count++;
}
}
}
queue.add(count);
}
for(Integer integer:queue){
System.out.println(integer);
}
}
}
import java.util.Scanner; import java.util.List; import java.util.ArrayList; public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int number = Integer.parseInt(sc.nextLine()); List<String> list=new ArrayList<>(); for(int i=0;i<number;i++){ list.add(sc.nextLine()); } String[] numbers = list.get(0).split(" "); int groupnumber=Integer.parseInt(list.get(1).trim()); for(int i=2;i<list.size();i++){ int count=0; String[] grouparr = list.get(i).split(" "); int start=Integer.parseInt(grouparr[0]); int end=Integer.parseInt(grouparr[1]); for(int j=start-1;j<=end-1;j++){ if(numbers[j].equals(grouparr[2])){ count++; } } System.out.println(count); } } }
#include<iostream>
#include<vector>
#include<unordered_map>
#include<algorithm>
using namespace std;
int main()
{
int n;cin >> n;
unordered_map<int, vector<int> > k_index;
for (int i = 1;i <= n;i++)
{
int data;cin >> data;
k_index[data].push_back(i);
}
//输入查询
int q;cin >> q;
while (q--)
{
int l, r, k;
cin >> l >> r >> k;
unordered_map<int, vector<int> >::iterator temp_it = k_index.find(k);
if (temp_it == k_index.end())
cout << 0 << endl;
else
{
//二分查找
auto ln = lower_bound(temp_it->second.begin(), temp_it->second.end(),l);
auto rn = upper_bound(temp_it->second.begin(), temp_it->second.end(),r);
cout << rn - ln << endl;
}
}
return 0;
}
import java.util.HashMap; import java.util.ArrayList; import java.util.List; import java.util.Map; import java.util.Scanner; public class Main { public static void main(String[] args) { try (Scanner scanner = new Scanner(System.in)) { // 用户个数 int userCount = scanner.nextInt(); // key表示fav值,value表示fav位置 Map<Integer, List<Integer>> favMap = new HashMap<Integer, List<Integer>>(); for (int i = 0; i < userCount; i++) { int num = scanner.nextInt(); if (favMap.containsKey(num)) { favMap.get(num).add(i + 1); } else { List<Integer> li = new ArrayList<Integer>(); li.add(i + 1); favMap.put(num, li); } } // 测试组个数 int testCount = scanner.nextInt(); // 结果集 int[] results = new int[testCount]; for (int i = 0; i < testCount; i++) { int min = scanner.nextInt(); int max = scanner.nextInt(); int testFav = scanner.nextInt(); if (favMap.containsKey(testFav)) { for (Integer favIndex : favMap.get(testFav)) { if (min <= favIndex && favIndex <= max) { results[i]++; } } } } // 输出结果集 for (int i = 0; i < testCount; i++) { System.out.println(results[i]); } } catch (Exception e) { // TODO: handle exception } } }
import java.util.*; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); Map<Integer, List<Integer>> m = new HashMap<>(); for (int i = 1; i <= n; ++i) { int k = in.nextInt(); m.computeIfAbsent(k, e -> new ArrayList<>()).add(i); } int q = in.nextInt(); while (q-- != 0) { int left = in.nextInt(), right = in.nextInt(), k = in.nextInt(); List<Integer> ls = m.getOrDefault(k, new ArrayList<>()); int res = 0; for (int i: ls) { if (i >= left && i <= right) res++; } System.out.println(res); } } }
#include <iostream> using namespace std; #include <bits/stdc++.h> int main() { int n; cin>>n; vector<int>f(n+1); for(int i=1;i<=n;i++){ cin>>f[i]; } int q,l,r,fav; cin>>q; for(int i=0;i<q;i++){ cin>>l>>r>>fav; int ret=0; for(int j=l;j<=r;j++){ if(f[j]==fav)ret++; } cout<<ret<<endl; } return 0; }
import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int[] liken = new int[n]; //用于管理用户喜好的数组 长度为用户个数 for(int i=0;i<n;i++) {liken[i] = in.nextInt();} int q = in.nextInt(); for(int i=0;i<q;i++) { int start = in.nextInt(); int end = in.nextInt(); int like = in.nextInt(); int result = function(start,end,like,liken); System.out.println(result); } } public static int function(int start, int end, int like,int[] liken) { int count = 0; for (int i = start - 1; i < end; ++i) { if(like == liken[i]){ count++; } } return count; } }
#include <iostream> using namespace std; int main() { int n; cin>>n; int user[n]; int i,j,k; for (i=0;i<n;++i) { cin>>user[i]; } cin>>k; int l,r,like; for (i=0;i<k;++i) { int num=0; cin>>l>>r>>like; for (j=l-1;j<r;++j) { if (user[j]==like) { ++num; } } cout<<num<<endl; } } 看了上面各位大神的解答还是觉得太高级,来一个真·大学生版的,刚学数据结构就能看懂
import java.util.*; public class Main{ public static void main(String[] arg){ Scanner sc=new Scanner(System.in); int n=sc.nextInt(); HashMap<Integer,ArrayList<Integer>> hashmap =new HashMap<>(); for(int i=1;i<=n;i++){ Integer temp=sc.nextInt(); if(!hashmap.containsKey(temp)){ ArrayList<Integer> list=new ArrayList<>(); list.add(i); hashmap.put(temp,list); }else{ ArrayList<Integer> list=hashmap.get(temp); list.add(i); hashmap.put(temp,list); } } int q=sc.nextInt(); for(int i=0;i<q;i++){ Integer left=sc.nextInt(); Integer right=sc.nextInt(); Integer k=sc.nextInt(); int count=0; ArrayList<Integer> list=hashmap.get(k); if(list==null){ System.out.println(count); }else{ for(Integer integer:list){ if(integer<=right&&integer>=left){ count++; } } System.out.println(count); } } } }