1236. 递增三元组

https://www.acwing.com/problem/content/1238/
先用桶装有数的
for(int i=1;i<=n;i++) cnt[a[i]]++;
cnt[i]表示前i个数有数的,有就为1,无就为0
再利用递推计算一下前缀和s[i]
s[i]=cnt[0]+cnt[1]+cnt[2]+....+cnt[i]
则有
for(int i=1;i<N;i++)s[i]=s[i-1]+cnt[i];
由于数都是用桶装的,即每一个有数的cnt[i]都是1
则前缀和s[i]即表示有数的个数,或者是说,比i小的数或者等于i的数出现的个数

我们需要算的是有多少中组合方式,则对于一个特定的B[j],A值和C值互不影响
可相乘求组合数

接下来就是枚举B[i],求在B值为B[i]下,小于B[i]的A值可以有多少种,大于B[i]的C值可以为多少种
相乘后,把所有此值求和即可

小于B[i]的A值的个数,由此前求的前缀和得,为 s[ b[i]-1 ] 
大于B[i]的C值的个数,稍加分析,可知由减法运算可算出,即为 s[ N-1 ]-s[ b[i] ]
上述两式对应的是同一个B[i],所以我们需要枚举B[i],相乘求和
可以用数组存储单独枚举每一个B[i],小于B[i]的A值的个数;
即若as[N]表示A中小于B[i]的个数;
那么既有as[i]=s[ b[i]-1 ] ;
同理有cs[i]=s[ N-1 ]-s[ b[i] ];

存储后,再在后面共同枚举B[j],计算as[i]*cs[i]求和即可

#include<iostream>
#include<cstring>
#include<algorithm>
#define N 100010
using namespace std;
typedef long long LL;
int n;
int a[N],b[N],c[N];
int as[N];
int cs[N];
int cnt[N],s[N];//模拟
int main()
{
    cin>>n;
    for(int i = 0;i < n;i ++)   scanf("%d",&a[i]),a[i]++;//加1是为了后面处理as不越界,都加了1,就不影响结果个数
    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];//最大可以枚举到C[N-1]
    for(int i = 0;i < n;i ++)   cs[i] = s[N-1] - s[b[i]];
    LL res = 0;
    for(int i = 0;i < n;i ++)   res += (LL)as[i]*cs[i];
    cout<<res<<endl;
    return 0;
}

 显然,此题也具有二段性
枚举每一个B[i],不断二分逼近满足a[i]>b[i]
同理,不断二分逼近满足c[i]<b[i];
记录他们的下标,再进行乘法原理计算
可以用排序+二分做法

#include<iostream>
#include<cstring>
#include<algorithm>
#define N 100010
using namespace std;
typedef long long LL;
int n;
int a[N], b[N], c[N];
LL res;
int main()
{
	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]++;
	sort(a, a + n);
	sort(b, b + n);
	sort(c, c + n);
	for (int i = 0; i < n; i++)
	{
		int l = 0, r = n - 1;
		while (l < r)
		{
			int mid = l + r + 1 >> 1;
			if (a[mid] < b[i])l = mid;
			else r = mid - 1;
		}
		if (a[l] >= b[i]) //a中无小小于b[i]的数
			l = -1; //做个标记
		int flag1 = l; //未做标记则flag1为正确答案
		l = 0, r = n - 1;
		while (l < r)
		{
			int mid = l + r >> 1;
			if (c[mid] > b[i])r = mid;
			else l = mid + 1;
		}
		if (c[l] <= b[i]) //c中无大于b[i]的数
			r = n;
		int flag2 = r;
		res += (LL)(flag1 + 1) * (n - flag2);
	}
	cout << res << endl;
	return 0;
}