H-亚丝娜sama（前缀和）

题目链接：http://acm.csust.edu.cn/problem/3026

Description

 

众所周知桐人能砍子弹，但是有人想用数量伤到桐人，所以他带着一群人来攻击桐人。

桐人想知道他在第k秒时需要砍多少颗子弹，但是他砍子弹已经很辛苦了，所以他来找聪明的你来帮他算一算。

他有t次询问，每次询问一个k。

子弹从发射到击中桐人要m秒，有n个人射击，每1秒射出一发子弹（弹夹足够大不需要换子弹，一旦开始就不会停），

现给出你这n个人开始射击的时间，请你帮帮桐人吧。

Input

 

第一行3个整数n,m,t用空格分开（0≤n≤100000,1≤m≤100000,1≤t≤100000）。

第二行是n个正整数ai​表示第i个人开始射击的时间（0≤ai​≤100000）。

接下来t行，每行一个数字k（0≤k≤300000）。

Output

 

请输出tt行，每行一个答案（第kk秒需要砍的子弹数目）。

Sample Input 1 

5 1 2
0 1 2 2 3
2
3

Sample Output 1

2
4

---

在原来射出的时间基础上加上m，然后对该时间的映射++,然后做一个时间所映射的子弹数的前缀和就完事了。

当然，你也可以用排序+二分写这题。

以下是前缀和AC代码：

#include <bits/stdc++.h>
using namespace std;

const int mac=1e5+10;

int a[mac],b[3*mac];
int sum[3*mac];

int main()
{
    int n,m,t;
    scanf ("%d%d%d",&n,&m,&t);
    for (int i=1; i<=n; i++){
        scanf ("%d",&a[i]);
        a[i]+=m;b[a[i]]++;
    }
    for (int i=1; i<=3*mac; i++){
        sum[i]=sum[i-1]+b[i];
    }
    for (int i=1; i<=t; i++){
        int k;
        scanf ("%d",&k);
        printf ("%d
",sum[k]);
    }
    return 0;
}