小单刷题笔记之递增三元组（前缀和/二分）

给定三个整数数组

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

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

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

输入格式

第一行包含一个整数 N。

第二行包含 N 个整数 A1,A2,…AN

第三行包含 N 个整数 B1,B2,…BN

第四行包含 N 个整数 C1,C2,…CN

输出格式

一个整数表示答案。

数据范围

1≤N≤1e5 0≤Ai,Bi,Ci≤1e5

输入样例：

3
1 1 1
2 2 2
3 3 3

输出样例：

27

思路：

1）暴力：枚举所有数，时间复杂度O（n^3),此题N的规模为1e5，大概是1e15,此法TLE，实在没思路打蓝桥可以骗分；

#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010;
int a[N],b[N],c[N];


int main(){
	int n;cin>>n;
	int ans=0;
	for(int i=0;i<n;++i)scanf("%d",&a[i]);
	for(int i=0;i<n;++i)scanf("%d",&b[i]);
	for(int i=0;i<n;++i)scanf("%d",&c[i]);
	
	for(int i=0;i<n;++i){
		for(int j=0;j<n;++j){
			for(int k=0;k<n;k++){
				if(a[i]<b[i]&&b[i]<c[i]){
					ans++;
				}
			}
		}
	}
	cout<<ans;
	
	return 0;
}

2）排序+二分，复杂度为O（n*logn），大概1e7的一个复杂度，是可以AC的，我这里直接用了c++的upper_bound和lower_bound来求。就是只枚举b数组，然后找到a数组比b[i]小的所有数的个数*c数组所有比b[i]大的个数。要注意下，这俩函数返回的是指针，计算的时候要减去一个

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>

using namespace std;
const int N=1e5+5;
int a[N],b[N],c[N];
int n;
int main(){
    cin>>n;


    for(int i=0;i<n;++i)cin>>a[i];
    for(int i=0;i<n;++i)cin>>b[i];
    for(int i=0;i<n;++i)cin>>c[i];
    sort(a,a+n);
    sort(c,c+n);
    
    int ans=0;
    for(int i=0;i<n;++i){
        int *pc=upper_bound(c,c+n,b[i]);//第一个大于b[i]的下标
        int *pa=lower_bound(a,a+n,b[i]);//第一个等于b[i]的下标
    
	    int *cc=c;
        int *aa=a;
	
		int numc=pc-cc;
	    int numa=pa-aa;
    
	    numc=n-numc;
       
        ans+=numc*numa;
    }
    cout<<ans;
    
    return 0;
}

3）前缀和+桶排序思想 时间复杂度O（n），

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const int N=1e5+5;
int a[N],b[N],c[N];
int cnt[N],s[N];
int as[N],cs[N];
int main(){
    int n;cin>>n;
    for(int i=0;i<n;++i)scanf("%d",&a[i]),a[i]++;
    for(int i=0;i<n;++i)scanf("%d",&b[i]),b[i]++;
    for(int i=0;i<n;++i)scanf("%d",&c[i]),c[i]++;
    
    for(int i=0;i<n;++i)cnt[a[i]]++;
    for(int i=1;i<N;++i)s[i]=s[i-1]+cnt[i];
    for(int i=0;i<n;++i)as[i]=s[b[i]-1];
    
    memset(cnt,0,sizeof cnt);
    memset(s,0,sizeof s);
    
    for(int i=0;i<n;++i)cnt[c[i]]++;
    for(int i=1;i<N;++i)s[i]=s[i-1]+cnt[i];
    for(int i=0;i<n;++i)cs[i]=s[N-1]-s[b[i]];
    
    LL ans=0;
    for(int i=0;i<n;i++)ans+=(LL)as[i]*cs[i];
    cout<<ans;
    
    
    
    
    
    return 0;
}

用到前缀和一般都需要把区间+1，因为转移的时候需要用到前一个s[i-1]。这个思路也是枚举b的位置，因为枚举b的位置以后，a中小于b[i]的个数和c中大于b[i]的个数是固定的。先统计一下a中所有数出现的次数，存在cnt中，再求cnt的前缀和s，意思就是：前i个数出现的总次数。（都不用排序了hh），最后再求一下as，等于s中所有小于b[i]的数出现的个数和。c基本上同理。

今天你刷算法题了吗？