建设游戏网站目的及其定位,wordpress管理员手册,请人制作一个app多少钱,实体店会员卡管理系统目录 题目链接
一些话
流程
套路
ac代码 题目链接 1236. 递增三元组 - AcWing题库 一些话
int f[N];
memset(f,0,sizeof f)影响不到f[N]
所以尽量不要对f[N]赋值#xff0c;不要用f[N]操作 流程
//由三重暴力i,j,k因为三重暴力底下是分别用i和j#xff0c;j和k作比较…目录 题目链接
一些话
流程
套路
ac代码 题目链接 1236. 递增三元组 - AcWing题库 一些话
int f[N];
memset(f,0,sizeof f)影响不到f[N]
所以尽量不要对f[N]赋值不要用f[N]操作 流程
//由三重暴力i,j,k因为三重暴力底下是分别用i和jj和k作比较想到可以拆成i~j,j ~k 再乘起来, // 但 n 1e5双循环复杂度也还是太高不过还有更优的方法 // 即枚举b中元素求b的第k个元素大于a中元素的个数和b的第k个元素小于c中元素的个数然后相乘。可以通过前缀和哈希或二分来实现 // 前缀和哈希要先统计a和c的元素个数然后通过前缀和来得到a和c中小于等于某值的元素个数的数组 // 然后求b的第k个元素大于a中元素的个数就是这个a中小于等于b[k] -1 的元素个数即s[b[k] - 1] //b的第k个元素小于c中元素的个数就是c中元素的个数减去c中小于等于b的第k个元素的个数即s[N-1] - s[b[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]; ac代码 #include iostream
#include algorithm
#include cstring
#include cstdio
using namespace std;
const int N 1e5 10;
int a[N],b[N],c[N],cc[N],ca[N],cnt[N],s[N];
int main(){int n;cin n;for(int i 0;i n;i) cin a[i] , a[i];for(int i 0;i n;i) cin b[i] , b[i];for(int i 0;i n;i) cin 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) ca[i] s[b[i]-1];memset(s,0,sizeof s);memset(cnt,0,sizeof cnt);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) cc[i] s[N-1] - s[b[i]];long long ans 0;for(int i 0;i n;i){ans ca[i] * (long long) cc[i];}cout ans endl;return 0;
}
