1236. 递增三元组

en...

就是学了也有比较长的时间，能写出来的题目还是没有难度

希望你只是走的慢，但一直在路上

1236. 递增三元组 - AcWing题库

这个题的优化蛮好的

第一版：二分

#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010;
int n; 
int a[N],b[N],c[N];
int ct[N];
long long ans;
int main(){scanf("%d",&n);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]);}sort(a,a+n);sort(c,c+n);for(int i=0;i<n;i++){int x=b[i];int l=-1,r=n;while(l<(r-1)){int mid=(l+r)>>1;if(a[mid]<x) l=mid;else r=mid;}int tmp=l+1;l=-1,r=n;while(l<(r-1)){int mid=(l+r)>>1;if(c[mid]<=x) l=mid;else r=mid;}ans+=(long long)tmp*(n-r);}printf("%lld",ans);return 0;
}

第二版：因为对每个数都要二分，改成线性找，时间复杂度降O(n)，但是排序O(nlogn)

#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010;
int n; 
int a[N],b[N],c[N];
long long ans;
int main(){scanf("%d",&n);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]);}sort(a,a+n);sort(b,b+n);sort(c,c+n);int l=-1,r=-1;for(int i=0;i<n;i++){while(l<(n-1)&&a[l+1]<b[i]) l++;while(r<(n-1)&&c[r+1]<=b[i]) r++;//   printf("%d\n",(l+1)*(n-1-r));ans+=(long long)(l+1)*(n-1-r);}printf("%lld",ans);return 0;
}

第三版：排序是为了确定比某个值小的数的个数，hash，总时间复杂度降O(n)

#include<iostream>
using namespace std;
const int N=100010;
int n; 
int ha[N],b[N],hc[N];
int cta[N],ctc[N];
long long ans;
int main(){scanf("%d",&n);for(int i=0;i<n;i++){int x; scanf("%d",&x);ha[x]++;}for(int i=0;i<n;i++){scanf("%d",&b[i]);}for(int i=0;i<n;i++){int x; scanf("%d",&x);hc[x]++;}for(int i=1;i<N;i++){cta[i]=cta[i-1]+ha[i-1];}for(int i=N-2;i;i--){ctc[i]=ctc[i+1]+hc[i+1];}for(int i=0;i<n;i++){ans+=(long long)cta[b[i]]*ctc[b[i]];}printf("%lld",ans);return 0;
}