题目
求 三元组(i,j,k), i<j<k, 满足 a[i]<a[j]<a[k] ,有多少组?(a[i] <=1e5)
枚举 j , 考虑 a[i]<a[j] 有多少 i 满足这个条件
注意到a[i]的范围,我们用一个桶 v[i] 存以下 值为i 的元素个数 , 对于枚举的a[j] , 求 v[1]+v[2]+v[3] ……v[a[j]-1] 即可
即维护一个前缀和
于是可以得到 c[i] , 即刚才求出的个数
对于a[j]<a[k]同理 ,我们得到 d[i]
那么
ans= c[i]*(n-i-d[i]) + (i-c[i]-1])*d[i]
————————————————
#include <iostream> #include <algorithm> #include <cstring> using namespace std; const int M=1e5+2,N=3e4; #define int long long int n,a[N],tr[M]; int c[N],d[N]; int lowbit(int x){ return x&-x; } void add(int x,int v){ for(;x<M;x+=lowbit(x)) tr[x]+=v; } int q(int x){ int t=0; for(;x;x-=lowbit(x)) t+=tr[x]; return t; } void solve(){ int i,j; int ans=0; memset(tr,0,sizeof tr); for(i=1;i<=n;i++){ c[i]=q(a[i]-1); add(a[i],1); } memset(tr,0,sizeof tr); for(i=n;i>=1;i--){ d[i]=q(a[i]-1); add(a[i],1); } for(i=1;i<=n;i++){ ans+= c[i]*(n-i-d[i])+(i-c[i]-1)*d[i]; } cout<<ans<<endl; } signed main(){ //freopen("in","r",stdin); //freopen("out","w",stdout); int cas; cin>>cas; while(cas--){ cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; solve(); } }
原文地址:http://www.cnblogs.com/towboa/p/16833440.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性