Examples
AcWing 1210. Consecutive interval number
Xiao Ming has been thinking about such a strange and interesting question these days:
How many consecutive intervals are there in an arrangement of 1 ∼ N?
The definition of the serial interval here is:
If all the elements in the interval [L,R] (i.e. the L-th to r-th elements of this arrangement) can get a "continuous" sequence with a length of R − L+1 after incremental sorting, it is called this interval serial interval.
When N is very small, Xiao Ming can quickly calculate the answer, but when N becomes large, the problem is not so simple. Now Xiao Ming needs your help.
Input format
The first line is a positive integer N, indicating the scale of the arrangement.
The second line is N different numbers Pi, indicating an arrangement of these N numbers.
Output format
Output an integer representing the number of different consecutive intervals.
Data range
1≤N≤10000,
1≤Pi≤N
Input example 1:
4
3 2 4 1
Output example 1:
7
Input example 2:
5
3 4 2 5 1
Output example 2:
9
Example explanation
In the first use case, there are seven consecutive intervals: [1,1], [1,2], [1,3], [1,4], [2,2], [3,3], [4,4]
In the second use case, there are 9 consecutive intervals: [1,1], [1,2], [1,3], [1,4], [1,5], [2,2], [3,3], [4,4], [5,5]
Idea:
- 1e4, all intervals can be enumerated
- Note that the input data ensures that the values of each element are different, so the continuous is equivalent to the maximum minus the minimum is equal to the interval length - 1
- Obviously, it is impossible to get the maximum and minimum value of each interval through each sorting, because we list all intervals in order, so we can use the dynamic update method
#include <iostream>
using namespace std;
const int N = 1e4 + 10;
int n, a[N];
int main()
{
cin >> n;
for (int i = 1; i <= n && cin >> a[i]; i ++ );
int res = 0;
for (int i = 1; i <= n; i ++ )
{
int mx = 0, mi = 1e5;
for (int j = i; j <= n; j ++ )
{
mx = max(mx, a[j]);
mi = min(mi, a[j]);
if (j - i + 1 == mx - mi + 1) res ++ ;
}
}
cout << res;
}
AcWing 1236. Incremental triplet
Given three integer arrays
A=[A1,A2,...AN],
B=[B1,B2,...BN],
C=[C1,C2,...CN],
Please count how many triples (i,j,k) satisfy:
1≤i,j,k≤N
Ai<Bj<Ck
Input format
The first line contains an integer N.
The second line contains N integers A1,A2,... AN.
The third line contains N integers B1,B2,... BN.
The fourth line contains N integers C1,C2,... CN.
Output format
An integer represents the answer.
Data range
1≤N≤105,
0≤Ai,Bi,Ci≤105
Input sample:
3
1 1 1
2 2 2
3 3 3
Output example:
27
Idea (two points):
- Remember to sort before two points
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int n;
int a[3][N];
int main()
{
cin >> n;
for (int i = 0; i < 3; i ++ )
for (int j = 1; j <= n; j ++ )
cin >> a[i][j];
for (int i = 0; i < 3; i ++ ) sort(a[i] + 1, a[i] + n + 1); // Dichotomy
ll res = 0;
for (int i = 1; i <= n; i ++ )
{
int cnta = lower_bound(a[0] + 1, a[0] + n + 1, a[1][i]) - a[0] - 1;
int cntc = n - (upper_bound(a[2] + 1, a[2] + n + 1, a[1][i]) - a[2]) + 1;
res += (ll)cnta * cntc;
}
cout << res;
}
Train of thought (double pointer):
- Further optimize the search. Find the number less than key in array a after sorting. Double pointer algorithm can be used. The same is true for array c
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int n;
int a[3][N];
int main()
{
cin >> n;
for (int i = 0; i < 3; i ++ )
for (int j = 1; j <= n; j ++ )
cin >> a[i][j];
for (int i = 0; i < 3; i ++ ) sort(a[i] + 1, a[i] + n + 1); // Dichotomy
ll res = 0;
int pa = 1, pc = 1;
for (int i = 1; i <= n; i ++ )
{
int key = a[1][i];
while (pa <= n && a[0][pa] < key) pa ++ ; // >=
while (pc <= n && a[2][pc] <= key) pc ++ ; // >
res += (ll)(pa - 1) * (n - pc + 1);
}
cout << res;
}
Ideas (prefix and):
- Each time, the number of a array smaller than b[i] is found, so this number can be preprocessed
- First, record the corresponding quantity of each value in the a array, because the element value range is only 1 0 5 10^5 105, so just use the array directly
- Note that the element value of this question may be 0, so the overall offset increases by 1, which does not affect the relative size
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int n;
int cnta[N], b[N], cntc[N];
int main()
{
cin >> n;
for (int i = 1, x; i <= n && cin >> x; i ++ ) cnta[ ++ x] ++ ;
for (int i = 1; i <= n && cin >> b[i]; i ++ ) b[i] ++ ;
for (int i = 1, x; i <= n && cin >> x; i ++ ) cntc[ ++ x] ++ ;
// cnta[0] = cnta[0];
for (int i = 1; i < N; i ++ ) cnta[i] += cnta[i - 1];
// cntc[0] = cntc[0];
for (int i = 1; i < N; i ++ ) cntc[i] += cntc[i - 1];
ll res = 0;
for (int i = 1; i <= n; i ++ )
{
int key = b[i];
res += (ll)cnta[key - 1] * (cntc[N - 1] - cntc[key]);
}
cout << res;
}