【无标题】

题目：

1236. 递增三元组

•    题目
•    提交记录
•    讨论
•    题解
•    视频讲解

给定三个整数数组

A=[A1,A2,…AN]A=[A1,A2,…AN],
B=[B1,B2,…BN]B=[B1,B2,…BN],
C=[C1,C2,…CN]C=[C1,C2,…CN],

请你统计有多少个三元组 (i,j,k)(i,j,k) 满足：

1. 1≤i,j,k≤N1≤i,j,k≤N
2. Ai<Bj<CkAi<Bj<Ck

输入格式

第一行包含一个整数 NN。

第二行包含 NN 个整数 A1,A2,…ANA1,A2,…AN。

第三行包含 NN 个整数 B1,B2,…BNB1,B2,…BN。

第四行包含 NN 个整数 C1,C2,…CNC1,C2,…CN。

输出格式

一个整数表示答案。

数据范围

1≤N≤1051≤N≤105,
0≤Ai,Bi,Ci≤1050≤Ai,Bi,Ci≤105

输入样例：

3
1 1 1
2 2 2
3 3 3

输出样例：

27

代码：双指针

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e5+10;
int num[3][N];int main(){int n;scanf("%d", &n);for(int i = 0; i < 3; ++i) for(int j = 1; j <= n; ++j) scanf("%d", &num[i][j]);for(int i = 0; i < 3; ++i)sort(num[i]+1, num[i]+n+1);LL ans = 0;//双指针查找a<b的，c>b的。以b为中间点int a=1,c=1;//a,c为数组AC的下标表示，也就是指针满足条件在移动for(int i=1;i<=n;i++){int b=num[1][i];//每一个b中的数字while(a<=n&&(num[0][a]<b))  a++;//将数组A的元素从前往后扫描，符合条件的则移动指针while(c<=n&&(num[2][c]<=b))  c++;//<=是因为，要找的是c>b的个数，而这里c<=b时，下标为c满足大于的个数为n-cans += (LL)(a-1)*(n-c+1);//将每一次b的值满足的数量加起来//a-1是因为初始化a从1开始自增，最终的个数应该是-1。和c的情况一样a++之后下一次不满足<b了，所以满足的是a-1个个数//n-c+1是因为：当当前满足最后一个<=b时，c++进入循环，此时的值num[2][c]是>b的，所以从c到n的个数（包含c,c已经大于b了）有n-c+1}cout<<ans<<endl;return 0;
}

思路方法：有三种

1、先看看暴力：三层for循环，判断每一层a[i]<b[j]<c[k],O(n^3)=10^15超时

2、优化：枚举B数组，cnt1*cnt2

尝试通过枚举的次序进行优化本题，先枚举B数组，在A中寻找小于B[i]的数的个数cnt1，在C中寻找大于B[i]的数的个数cnt2，带有B[i]的合法选择数就是cnt1*cnt2。

用暴力查找时间总的时间复杂度为O(n2)，还是会超时。

3、进一步优化，基于方法2------枚举+查找（二分）O(nlogn)

用到了查找，查找最典型的就是二分nlogn

先排序abc数组，在二分找。用到了lower_bound()和upper_bound()  c++的库函数

排序和二分时间复杂度都是O(nlogn)

//二分
for(int i = 1; i <= n; ++i) {int key = num[1][i];//A中二分查找第一个小于key的数的下标int pos1 = lower_bound(num[0]+1, num[0]+n+1, key)-num[0]-1;//C中二分查找第一个大于key的数的下标int pos2 = upper_bound(num[2]+1, num[2]+n+1, key)-num[2];if(pos1 >= 1 && pos2 <= n) {ans += (LL)pos1*(n-pos2+1);}
}

4、在进一步优化------枚举+双指针O(nlogn)

在3的二分查找上可以使用双指针O(n)

进一步对查找进行优化，对于排过序的数组A和B，寻找A中小于B[i]的元素的个数可以考虑双指针算法，因为每个指针最多移动n次，故查找的时间复杂度降到O(n)，查找C与查找A同理，只是找第一个大于B的位置。

a,c为下标，即双指针指向

A找第一次不满足<b的位置（数组下标）---------最后个数为a-1

C找第一次不满足<=b的位置，因为c>b-----------最后个数为n-c+1

//双指针
int a = 1, c = 1;
for(int i = 1; i <= n; ++i) {int key = num[1][i];while(a<=n && num[0][a] < key) a++;while(c<=n && num[2][c] <= key) c++;ans += (LL)(a-1)*(n-c+1);
}

5、再进行进一步优化，考虑是否可以不进行排序--------哈希前缀和O(n)

将A,C数组中数字出现的次数存入cnta,cntc中

cnta,cntc存放数字出现的次数，这时就A[i]即为数组cnta的下标A[i]的位置，在哈希存入的时候已经按下标排序了。

计算前缀和，最后只用找到<b位置的前缀和ac相乘即可。次数相乘

之前的双指针算法时间复杂度的瓶颈为：排序𝑂(𝑛𝑙𝑜𝑔2𝑛)

考虑是否可以不排序在O(n)的时间内解决此问题呢？

既然要排序实现快速的查找A中小于B[i]的数的个数，可以将数组A中所有元素出现的次数存入一个哈希表中，因为数组中元素的范围只有n^5, 可以开一个大的数组cnta 作为哈希表。

在枚举B中元素时，我们需要快速查找找小于B[i]的所有元素的总数，只需要在枚举之前先将求出表中各数的前缀和即可。

查找C与查找A同理可得。

 

//前缀和
#include <iostream>
#include <cstdio>using namespace std;typedef long long LL;
const int N = 1e5+10;
int A[N], B[N], C[N];
int cnta[N], cntc[N], sa[N], sc[N];int main() {int n;scanf("%d", &n);//获取数i在A中有cntc[i]个，并对cnt求前缀和safor(int i = 1; i <= n; ++i) {scanf("%d", &A[i]);cnta[++A[i]]++;}sa[0] = cnta[0];for(int i = 1; i < N; ++i) sa[i] = sa[i-1]+cnta[i];//B只读取即可for(int i = 1; i <= n; ++i) scanf("%d", &B[i]), B[i]++;//获取数i在C中有cntc[i]个，并对cnt求前缀和scfor(int i = 1; i <= n; ++i) {scanf("%d", &C[i]);cntc[++C[i]]++;}sc[0] = cntc[0];for(int i = 1; i < N; ++i) sc[i] = sc[i-1]+cntc[i]; //遍历B求解LL ans = 0;for(int i = 1; i <= n; ++i) {int b = B[i];ans += (LL)sa[b-1] * (sc[N-1] - sc[b]);}cout<<ans<<endl;return 0;
}