Discretization of initial knowledge
Discretization
Discretization, mapping limited individuals in infinite space to limited space, so as to improve the space-time efficiency of the algorithm.
Generally speaking, discretization is to reduce the data without changing the relative size of the data.
For example:
Original data: 1999100000,15;
After treatment: 1,3,4,2;
Original data: {100200}, {2050000}, {1400};
After treatment: {3,4}, {2,6}, {1,5};
Discretization of data
Some data itself is very large, so it cannot save the corresponding attributes as the subscript of the array. If you only need the relative attributes of this pile of data, you can discretize it. When the data is only related to the relative size between them, but has nothing to do with the specific number, it can be discretized.
For the topic, when the data range is too large but the amount of data is small, you can try discretization
Operation steps
- Store all values to be discretized
- sort
- Delete duplicate elements
- The corresponding value of the index element after discretization
Examples
Suppose there is an infinite number axis, and the number on each coordinate on the number axis is 0.
Now, let's start with n operations. Each operation adds c to the number at a certain position x.
Next, make m queries. Each query contains two integers L and r. you need to find the sum of all numbers between the interval [l, r].
Input format
The first line contains two integers n and m.
Next n lines, each containing two integers x and c.
Then follow the line m, each line containing two integers l and r.
Output format
There are m lines in total, and each line outputs the sum of numbers in the interval obtained in the query.
Data range
−
1
0
9
≤
x
≤
1
0
9
,
−10^9≤x≤10^9,
−109≤x≤109,
1
≤
n
,
m
≤
1
0
5
1≤n,m≤10^5
1≤n,m≤105
−
1
0
9
≤
l
≤
r
≤
1
0
9
−10^9≤l≤r≤10^9
−109≤l≤r≤109
−
10000
≤
c
≤
10000
−10000≤c≤10000
−10000≤c≤10000
Input sample:
3 3
1 2
3 6
7 5
1 3
4 6
7 8
Output example:
8
0
5
thinking
x. l, r range is
[
−
1
0
9
,
1
0
9
]
[−10^9,10^9]
[−109,109]
Obviously, you can't use arrays to simulate the number axis
And the range of n and m is
[
1
,
1
0
5
]
[1,10^5]
[1,105]
Discretize x, l, r
The maximum space required at this time is only
n
+
2
∗
m
n+2*m
n+2∗m
This allows you to use arrays for processing
The steps are as follows
typedef pair<int, int> PII; const int N = 300010;// n+2*m == 300000; int n, m; int a[N], s[N];//s[N] is the prefix and array of a[N] vector<PII> add, ask;//Save insert operands and query operands respectively vector<int> alls; // Store all values to be discretized
Next, the array to be discretized is sorted for binary search
sort(alls.begin(), alls.end());
Delete duplicate elements (STL)
alls.erase(unique(alls.begin(), alls.end()), alls.end()); //unique returns the next sequence at the end of the de duplicated sequence, which is compressed by erase
Implementation of unique function (double pointer)
vector<int>::iterator unique(vector<int> &a) { int j = 0; for (int i = 0; i < a.size(); i ++ ) if (!i || a[i] != a[i - 1]) a[j ++ ] = a[i]; return a.begin() + j; } alls.erase(unique(alls), alls.end());//duplicate removal
Discretization
Writing method 1
int find(int x) // Find the first position greater than or equal to x { int l = 0, r = alls.size() - 1; while (l < r) { int mid = l + r >> 1; if (alls[mid] >= x) r = mid; else l = mid + 1; } return r + 1; // Map to 1, 2 n }//Start mapping from 1 to facilitate the processing of prefixes and
Writing method 2
lower_bound function (this is written in the comments section of the complete code)
int lower_bound(int *array, int size, int key)
Complete code
#include <iostream> #include <vector> #include <algorithm> using namespace std; typedef pair<int, int> PII; const int N = 300010; int n, m; int a[N], s[N]; vector<PII> add, ask; vector<int> alls; // Store all values to be discretized // Find the discretized value corresponding to x by bisection int find(int x) // Find the first position greater than or equal to x { int l = 0, r = alls.size() - 1; while (l < r) { int mid = l + r >> 1; if (alls[mid] >= x) r = mid; else l = mid + 1; } return r + 1; // Map to 1, 2 n }//Start mapping from 1 to facilitate the processing of prefixes and vector<int>::iterator unique_by(vector<int> &a) //Implementation of unique { int j = 0; for (int i = 0; i < a.size(); i ++ ) if (!i || a[i] != a[i - 1]) a[j ++ ] = a[i]; // a[0] ~ a[j - 1] non repeated numbers in all a return a.begin() + j; } int main() { cin >> n >> m; for (int i = 0; i < n; i ++ ) { int x, c; cin >> x >> c; add.push_back({x, c}); alls.push_back(x);//Insert the number to be discretized into the array to be discretized } for (int i = 0; i < m; i ++ ) { int l, r; cin >> l >> r; ask.push_back({l, r}); alls.push_back(l);//Insert the number to be discretized into the array to be discretized alls.push_back(r); } sort(alls.begin(), alls.end()); alls.erase(unique(alls.begin(), alls.end()), alls.end()); // Process insert for (auto item : add) { int x = find(item.first);//Discretized value //int x = lower_bound(alls.begin(),alls.end(),item.first)-alls.begin()+1; a[x] += item.second; } // Preprocessing prefix and for (int i = 1; i <= alls.size(); i ++ ) s[i] = s[i - 1] + a[i]; // Handling inquiries for (auto item : ask) { int l = find(item.first), r = find(item.second); //int l = lower_bound(alls.begin(),alls.end(),item.first)-alls.begin()+1; //int r = lower_bound(alls.begin(),alls.end(),item.second)-alls.begin()+1; cout << s[r] - s[l - 1] << endl; } return 0; }