题目
求 三元组(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(); } }
标签:int,1428,long,add,uva,include From: https://www.cnblogs.com/towboa/p/16833440.html