今日头条C++后台研发编程题
1.手串（比赛的时候IDE报问题，代码没有保存下来）
思路：
直接求一下前缀和，然后从左到右处理到2*n就可以了
2.用户满意度
离线一下，用一下莫队算法，裸的模板题
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <unordered_map>
#define FIN freopen("input.txt", "r", stdin)
using namespace std;
const int MAXN = 3e5 + 5;
const int MAXM = 50 + 5;
int n, q, l, r, k;
unordered_map<int,int> um;
int np[MAXN];
struct Q{
int l, r, k, id;
bool operator<(const Q&a) const{
if(l == a.l) return r < a.r;
return l < a.l;
}
}XW[MAXN];
vector<pair<int,int> > vec;
int main() {
//FIN;
while(~scanf("%d", &n)){
for(int i = 1;i <= n;++ i){
scanf("%d", &np[i]);
}
scanf("%d", &q);
for(int i = 0;i < q;i ++){
scanf("%d%d%d", &XW[i].l, &XW[i].r, &XW[i].k);
XW[i].id = i;
}
sort(XW, XW + q);
um.clear();
vec.clear();
int l = 1, r = 0;
for(int i = 0;i < q;++ i){
if(r < XW[i].r){
for(r = r + 1;r < XW[i].r; ++ r){
um[np[r]] ++;
}
um[np[r]] ++;
}
if(XW[i].l < l){
for(l = l - 1;XW[i].l < l;-- l){
um[np[l]] ++;
}
um[np[l]] ++;
}
if(XW[i].r < r){
for(;XW[i].r < r;-- r){
um[np[r]] --;
}
}
if(l < XW[i].l){
for(;l < XW[i].l;++ l){
um[np[l]] --;
}
}
vec.push_back(make_pair(XW[i].id, um[XW[i].k]));
}
sort(vec.begin(), vec.end());
for(int i = 0;i < vec.size();++ i){
printf("%d\n", vec[i].second);
}
}
return 0;
}
