AcWing
1236. 递增三元组
三种方法。
哈希+前缀和：分别记录数组a和c中各元素出现的次数，再求小于等于某个值i的前缀和s[i], i∈[0, 100000].
#include <bits/stdc++.h>
using namespace std;
int n;
const int N = 100010;
int a[N], b[N], c[N];
int cnta[N], sa[N], cntc[N], sc[N];
typedef long long LL;
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
cnta[a[i]]++;
}
sa[0] = cnta[0];
for(int i = 1; i <= N - 1; i++) sa[i] = cnta[i] + sa[i - 1];
for(int i = 1; i <= n; i++) cin >> b[i];
for(int i = 1; i <= n; i++){
cin >> c[i];
cntc[c[i]]++;
}
sc[0] = cntc[0];
for(int i = 1; i <= N - 1; i++) sc[i] = cntc[i] + sc[i - 1];
LL res = 0;
for(int i = 1; i <= n; i++) res += (LL)(sa[b[i]] - cnta[b[i]]) * (sc[N - 1] - sc[b[i]]);
cout << res;
return 0;
}
排序+双指针：对三个数组分别排序，每次取b中的一个元素，移动其他两个数组的指针，根据指针索引求满足条件的数组元素个数。
#include <bits/stdc++.h>
using namespace std;
int n;
const int N = 100010;
int a[N], b[N], c[N];
int pa = 1, pc = 1; // 恰好不小于b[i]的位置，恰好大于b[i]的位置
typedef long long LL;
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++) cin >> b[i];
for(int i = 1; i <= n; i++) cin >> c[i];
sort(a + 1, a + 1 + n); sort(b + 1, b + 1 + n); sort(c + 1, c + 1 + n); // nlogn
LL res = 0;
for(int i = 1; i <= n; i++){
while(a[pa] < b[i] && pa <= n) pa++;
while(c[pc] <= b[i] && pc <= n) pc++;
res += LL(pa - 1) * (n - pc + 1);
}
cout << res;
return 0;
}
排序+二分：对数组a和c排序，每次取b中的一个元素，二分查找数组a和c中恰好(不)满足要求的位置索引，再根据索引求满足条件的数组元素个数。
#include <bits/stdc++.h>
using namespace std;
int n;
const int N = 100010;
int a[N], b[N], c[N];
typedef long long LL;
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++) cin >> b[i];
for(int i = 1; i <= n; i++) cin >> c[i];
sort(a + 1, a + 1 + n); sort(c + 1, c + 1 + n); // nlogn
LL res = 0;
for(int i = 1; i <= n; i++){ //nlogn
int t = b[i], cnta, cntc;
// 二分查找a中恰好不小于t的位置
int l = 1, r = n;
while(l < r){
int mid = l + r >> 1;
if(a[mid] >= t) r = mid;
else l = mid + 1;
}
if(a[r] >= t) cnta = r - 1; // 判断边界
else cnta = n;
// 二分查找c中恰好不大于t的位置
l = 1, r = n;
while(l < r){
int mid = l + r + 1 >> 1;
if(c[mid] <= t) l = mid;
else r = mid - 1;
}
if(c[r] <= t) cntc = n - r; // 判断边界
else cntc = n;
res += (LL)cnta * cntc;
}
cout << res;
return 0;
}