首页 > 代码库 > HDU2492 Ping pong

HDU2492 Ping pong

题解:

每个数,求出左右两边比这个数大的和比这个数小的,然后以每个数作为裁判,求和就行了

代码:

#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>#include<map>using namespace std;#define pb push_back#define mp make_pair#define se second#define fs first#define LL long long#define CLR(x) memset(x,0,sizeof x)#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1 typedef pair<int,int> P;const double eps=1e-9;const int maxn=20100;const int N=100010;const int mod=1e9+7;const int INF=1e9;int a[maxn],l_num[N],r_num[N];LL L[N],R[N];int n;int lowbit(int x){return x&-x;}void add(int x,int v,int*c){    while(x<N){        c[x]+=v;        x+=lowbit(x);    }}LL sum(int x,int*c){    LL cnt=0;    while(x){        cnt+=c[x];        x-=lowbit(x);    }    return cnt;}int main(){    int T;    scanf("%d",&T);    while(T--){        scanf("%d",&n);        for(int i=1;i<=n;i++) scanf("%d",&a[i]);        CLR(l_num);CLR(r_num);        for(int i=1;i<=n;i++){            L[i]=sum(a[i]-1,l_num);//左边比a[i]小             R[n+1-i]=sum(a[n+1-i]-1,r_num);//右边比a[n+1-i]小             add(a[i],1,l_num);            add(a[n+1-i],1,r_num);        }        LL ans=0;        for(int i=1;i<=n;i++){            //cout<<L[i]<<" "<<R[i]<<endl;            ans+=L[i]*(n-i-R[i])+(i-1-L[i])*R[i];        }        printf("%lld\n",ans);    }    return 0;}

 

HDU2492 Ping pong