2552. Count Increasing Quadruplets
Given a 0-indexed integer array nums of size n containing all numbers from 1 to n, return the number of increasing quadruplets.
A quadruplet (i, j, k, l) is increasing if:
- 0 <= i < j < k < l < n, and
- nums[i] < nums[k] < nums[j] < nums[l].
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| long long fenwick[4040];
void update(long long n, long long k) {
while(n < 4040) {
fenwick[n] += k;
n += n & - n;
}
}
long long query(long long n) {
long long res = 0;
while(n) {
res += fenwick[n];
n -= n & -n;
}
return res;
}
class Solution {
public:
long long countQuadruplets(vector<int>& nums) {
memset(fenwick,0,sizeof fenwick);
long long res = 0;
for(int k = nums.size() - 1; k >= 0; k--) {
long long sum = 0;
for(int i = k - 1; i >= 0; i--) {
if(nums[i] > nums[k]) sum += nums.size() - 1 - k - query(nums[i]);
else if(sum) res += sum;
}
update(nums[k],1);
}
return res;
}
};
|
