为了不断优化推荐效果,今日头条每天要存储和处理海量数据。假设有这样一种场景:我们对用户按照它们的注册时间先后来标号,对于一类文章,每个用户都有不同的喜好值,我们会想知道某一段时间内注册的用户(标号相连的一批用户)中,有多少用户对这类文章喜好值为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
#include <iostream> using namespace std; int main() { int n, q; cin >> n; int user[n + 1]; for (int i = 1; i <= n; i++) cin >> user[i]; cin >> q; int l, r, k; while (q--) { cin >> l >> r >> k; int count = 0; for (int i = l; i <= r; i++) if (user[i] == k) count++; cout << count << endl; } return 0; }
#include<bits/stdc++.h> using namespace std; #define pb push_back const int N = 1e6+5; int a[N],b[N]; vector<int>v[N]; int main(){ ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); int n;cin>>n; for(int i=1;i<=n;i++)cin>>a[i],b[i]=a[i]; sort(b+1,b+1+n); int len=unique(b+1,b+1+n)-b-1; for(int i=1;i<=n;i++){ int now=lower_bound(b+1,b+1+len,a[i])-b; v[now].push_back(i); } int q;cin>>q; while(q--){ int x,y,z;cin>>x>>y>>z; int k=z; z=lower_bound(b+1,b+len+1,z)-b; if(z==len+1||b[z]!=k){ cout<<0<<'\n';continue; } x=lower_bound(v[z].begin(),v[z].end(),x)-v[z].begin(); y=upper_bound(v[z].begin(),v[z].end(),y)-v[z].begin(); cout<<y-x<<'\n'; } return 0; }
#include <stdio.h> //#include <stdlib.h> #define N 300000 inthabits(inta[],intstart,intend,intkey); intmain() { intuser[N],scan[3*N]; inti,n,q;//用户喜爱值数组和查询数组(3个为一组) scanf("%d",&n); for(i=1;i<=n;i++) scanf("%d",&user[i]); scanf("%d",&q); for(i=1;i<=3*q;i++) scanf("%d",&scan[i]);//数据输入 for(i=1;i<=3*q;i+=3) habits(user,scan[i],scan[i+1],scan[i+2]); return0; } inthabits(inta[],intstart,intend,intkey){ inti,sum=0; for(i=start;i<=end;i++) if(a[i]==key) sum++; printf("%d\n",sum); returnsum; } |
在可变字典中存可变数组,喜好值k为key,找到的用户注册时间为value,最后比较的就是value数组中的值是否在那段区间内
importsysn =int(sys.stdin.readline().strip())b =sys.stdin.readline().strip().split(" ")c =int(sys.stdin.readline().strip())nums =[]fori inrange(int(c)):nums.append(sys.stdin.readline().strip().split(" "))fori inrange(len(nums)):last =list(nums[i])ss =b[int(last[0])-1:int(last[1])]print(ss.count(last[2]))