今日头条2018校园招聘后端方向-编程题二

发表于 | 分类于 ，

题目

描述

一个数列长度为 n,现给出一个区间 [l,r] 及一个值 k,求区间内 k 值的个数

输入

第 1 行,一个数 n
第 2 行,数列中的 n 个元素
第 3 行,给定的区间数 q
第 4 到 q+3 行,每行三个数 分别为 l,r,k

输出

n 行,每个区间 qk 的个数, 和输入顺序相同

Example

Input

5
1 2 3 3 5
3
1 2 2
2 3 1
3 5 3

Output

1
0
2

题解

莫队算法

  • 读入所有查询区间,对区间排序,
  • 莫队算法,用 map 维护 qk 出现的次数
  • 时间复杂度 O(qlog q+nlog n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <bits/stdc++.h>

using namespace std;

int k[301024],n,q;

struct question
{
    int l,r,k,i;
    const bool operator<(const question q)
    {
        return l<q.l||l==q.l&&r<q.r;
    }
}questions[301024];

bool comp(const question q1,const question q2)
{
    return q1.i<q2.i;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&k[i]);
    }
    cin>>q;
    for(int i=1;i<=q;++i)
    {
        scanf("%d%d%d",&questions[i].l,&questions[i].r,&questions[i].k);
        questions[i].i=i;
    }
    sort(questions+1,questions+q+1);
    map<int,int>kNum;
    for(int i=questions[1].l;i<=questions[1].r;++i)
    {
        ++kNum[k[i]];
    }
    questions[1].k=kNum[questions[1].k];
    for(int i=2;i<=q;++i)
    {
        for(
            int l=questions[i-1].l,r=questions[i-1].r;
            l!=questions[i].l||r!=questions[i].r;
            )
        {
            if(l<questions[i].l)
                --kNum[k[l]],++l;
            else if(l>questions[i].l)
                ++kNum[k[r]],--l;
            if(r>questions[i].r)
                --kNum[k[r]],--r;
            else if(r<questions[i].r)
                ++kNum[k[r]],++r;
        }
        questions[i].k=kNum[questions[i].k];
    }
    sort(questions+1,questions+q+1,comp);
    for(int i=1;i<=q;++i)
    {
        printf("%d\n",questions[i].k);
    }
}