uncle-lu的种草日记 赛氪

1.5.7 uncle-lu的种草日记

Description

新北山上有一排空地，uncle-lu想重些草上去，于是乎他将这一排空地分割成nn块并标上号1...n1...n。(这片空地上什么草都没有)

你完全想不到，uncle-lu个有E技能，他一口气可以在一段连续的区间内种上一株草。例如，他想在区间[2,5][2,5]上种草，一个E！那空地[2,5][2,5]上草数量分别+1+1。当然uncle-lu身体没那么好，他只能使用mm次E技能。

当uncle-lu用完mm次E技能，他有qq个疑惑，他想知道某一块草地上的草的数量。

Input

第一行包含3个正整数 分别是 n,m,qn,m,q

接下来mm行中，每行包含2个正整数 x,yx,y 表示 uncle-lu 一次的E技能 在[x,y][x,y]区间内种一株草(保证x≤yx≤y)

第m+2m+2行，包含qq个正整数 表示每次uncle-lu询问的草地.

Output

输出包含qq行，对于每次询问，输出询问答案

Sample Input 1 

10 5 4
2 4
3 5
4 6
5 7
1 10
4 6 3 5

Sample Output 1

4
3
3
4

Hint

对于100100%数据:1 &lt;= n &lt;= 10^8, 1 &lt;= m &lt;= 10^5 , 1 &lt;= q &lt;= 10^51<=n<=108,1<=m<=105,1<=q<=105

#include <iostream>
#include <map>
using namespace std;
map<int, int>ma;
int main()
{int n, m, q;int a, b;int qq[10];cin >> n>>m>>q;for (int i = 1; i <= n; i++) {ma.insert(pair<int, int>(i, 0));}for (int i = 0; i < m; i++) {cin >> a >> b;for (int j = a; j <= b; j++) {map<int, int>::iterator pos = ma.find(j);(*pos).second++;}}for (int i = 0; i < q; i++) {cin >> qq[i];}for (int i = 0; i < q; i++) {cout << (*ma.find(qq[i])).second<<endl;}return 0;
}