Counting haybales (difference + discretization)

Title Description
link ：https://ac.nowcoder.com/acm/contest/7157/H
source ： Cattle from

Farmer John has just arranged his N haybales (1≤N≤100,000) at various points along the one-dimensional road running across his farm. To make sure they are spaced out appropriately, please help him answer Q queries (1≤Q≤100,000), each asking for the number of haybales within a specific interval along the road.

Input description
The first line contains N and Q.
The next line contains N distinct integers, each in the range 0…1,000,000,000, indicating that there is a haybale at each of those locations.
Each of the next Q lines contains two integers A and B (0≤A≤B≤1,000,000,000) giving a query for the number of haybales between A and B, inclusive.

Output description
You should write Q lines of output. For each query, output the number of haybales in its respective interval.

The sample input
4 6
3 2 7 5
2 3
2 4
2 5
2 7
4 6
8 10
Sample output
2
2
3
4
1
0

The main idea of the topic
In the interval [0,1000000000] There are some places in the haybales, Find interval [A,B] Inside haybales The number of

Ideas
use sum[] The array holds prefixes and ,sum[i] Indicates the interval [0,i] Inside haybales The number of , The answer for sum[B]-sum[A-1]. But the array subscript cannot reach 1,000,000,000, We noticed the most 100,000 There are haybales, most 100,000 A query , Therefore, most subscripts are actually used 300,000 individual , We can deal with the subscript problem by discretization .

AC Code

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5+7;
int mp[N*3], cnt, a[N], x[N], y[N], c[N*3], sum[N*3];
int n, Q;
int main() {
    
	freopen("Counting Haybales.txt", "r", stdin);
	scanf("%d%d", &n, &Q);
	for (int i = 1; i <= n; i++) {
    
		scanf("%d", &a[i]);
		mp[++cnt] = a[i];
	}
	for (int i = 1; i <= Q; i++) {
    
		scanf("%d%d", &x[i], &y[i]);
		mp[++cnt] = x[i];
		mp[++cnt] = y[i];
	}
	sort(mp+1,mp+cnt+1);
	cnt = unique(mp+1,mp+cnt+1)-mp;
	for (int i = 1; i <= n; i++) {
    
		int k = lower_bound(mp+1,mp+cnt+1,a[i])-mp;
		c[k]++;
	}
	for (int i = 1; i <= cnt; i++) {
    
		sum[i] = sum[i-1] + c[i];
	}
	for (int i = 1; i <= Q; i++) {
    
		int xx = lower_bound(mp+1,mp+cnt+1,x[i])-mp;
		int yy = lower_bound(mp+1,mp+cnt+1,y[i])-mp;
		printf("%d\n", sum[yy]-sum[xx-1]);
	}
	return 0;
}

Something to watch out for

• After ordering , Use unique() Function de duplication
• lower_bound() Function returns the first position greater than or equal to ,upper_bound() Function returns the first position greater than , So here we use lower_bound() Find the discretized subscript