递增三元组_(前缀和，二分)

原题链接：AcWing 1236. 递增三元组（蓝桥杯辅导课） - AcWing

题意：给定三元组，从上到下每组找一个元素构成递增关系，不能相等

思路

思路简单，先过一遍样例

发现选定第一位时，可以在第二组里找有多少大于这一位，再在第三组里找有多少大于第二组的

如果遍历实现肯定超时，考虑到：

• 第二组，找到第一个比当前大的第一个数作为分界点
• 第三组，找到比第二个数大的数作为分界点 考虑二分

当找到第一组选定的数，对应的每个第二组的大于这个数的数的索引时，包括这个数在内的后面的数都可以选（假定已经排好序）， 那么这些数对应的第三组的数也都可以选，所以目标是找到分界点，由于相加数量级别大，考虑前缀和

实现

实现时要注意理清楚二分要找什么值 由于考虑前缀和，对第二组二分时考虑的是最后一个小于等于当前数的索引（用于前缀和）

第三组要找的是，考虑第一个大于当前数的索引（要用n-l+1来确定其后有多少选择）

#include <iostream>
#include <algorithm>
 
using namespace std;
 
typedef long long LL;
 
const int N = 1e5 + 10;
 
int a[N], b[N], c[N];
LL sum[N];
 
 
int main()
{
    int n;
    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 + n + 1);
    sort(b + 1, b + n + 1);
    sort(c + 1, c + n + 1);    
    
    //二分
    int idxa = 0;
    for(int i = 1; i <= n; i ++)
    {
        //找到最后一个比自己小的
        int l = 1, r = n;
        while(l < r) 
        {
            int mid = (l + r + 1) >> 1;
            if(b[mid] <= a[i]) l = mid;
            else r = mid - 1;
        }
        idxa = i;
        if(b[l] > a[i]) a[i] = 0;
        else a[i] = l;
    }
        
    int idxb = 0;
    for(int i = 1; i <= n; i ++)
    {
        //找到第一个比自己大的
        int l = 1, r = n;
        while(l < r)
        {
            int mid = (l + r ) >> 1;
            if(c[mid] > b[i]) r = mid;
            else l = mid + 1;
        }
        // 记录下每个b可以选哪些数
        idxb = i;
        if(c[l] <= b[i]) b[i] = 0;
        else b[i] = n - l + 1;
    }
 
    for(int i = 1; i <= idxb; i ++)
    {
        //前缀和
        sum[i] += sum[i-1] + b[i];
        //cout << sum[i] << endl;
    }
    /*for(int i = 1; i  <= n; i ++)
    {    cout << b[i] << endl;
        cout << a[i] << endl;}*/
    LL ans = 0;
    for(int i = 1; i <= idxa; i ++)
    {
        //a对应的b可以选的全部数
        ans += sum[idxb] - sum[a[i]];
        //cout << ans;
    }
        
    cout << ans << endl;
    
    return 0;
}