多校联合训练5&&HDU5792

450 浏览 0 回复 2016-08-03

just_sort

+关注

【题意】求有多少种四个数满足Aa < Ab,Ac > Ad,1 < =a < b < = n ,1 < = c < d < = n

【解题方法】4个数两两不同，1 <= a < b <= n，1 <= c < d <= n，A_a < A_b，A_c > A_d。定义： $\left | { y | x < y <= n, A_x < A_y } \right |$ $\left | { y | 1 <= y < x, A_x < A_y } \right |$ $\left | { y | x < y <= n, A_x > A_y } \right |$ $\left | { y | 1 <= y < x, A_x > A_y } \right |$ $\sum_{i=1}^{n}{rs(i)}$ 以上都可以通过树状数组在 $n)O(n\ log\ n)$ 的时间内求出(需要先对A序列进行离散化处理)。然后， $\sum_{a=1}^{n}{rg(a) * (allg - lg(a) - rs(a))} - \sum_{b=1}^{n}{ls(b) * (lg(b) + rs(b)}$

$【AC 代码】$

#include<bits/stdc++.h>
using namespace std;
const int N =6e5;
#define LL long long
LL sum[N],a[N],x1[N],x2[N],d1[N],d2[N],A[N];
int k;
int lowbit(int x){return x&(-x);}
void update(int x)
{
    while(x<k){
        sum[x]++;
        x+=lowbit(x);
    }
}
LL query(int x)
{
    LL t=0;
    while(x){
        t+=sum[x];
        x-=lowbit(x);
    }
    return t;
}
int main()
{
    int n;
    while(~scanf("%d",&n)){
        for(int i=1;i<=n;i++){
            scanf("%I64d",&a[i]);
            A[i]=a[i];
        }
        sort(A+1,A+1+n);
        k=2;
        for(int i=2;i<=n;i++) if(A[i]!=A[i-1]) A[k++]=A[i];
        memset(sum,0,sizeof(sum));
        for(int i=1;i<=n;i++){
            int pos=lower_bound(A+1,A+k,a[i])-A;
            x1[i]=query(pos-1);
            d1[i]=query(k-1)-query(pos);
            update(pos);
        }
        memset(sum,0,sizeof(sum));
        for(int i=n;i>=1;i--){
            int pos=lower_bound(A+1,A+k,a[i])-A;
            d2[i]=query(pos-1);
            x2[i]=query(k-1)-query(pos);
            update(pos);
        }
        LL ans1=0,ans2=0;
        for(int i=1;i<=n;i++){
            ans1+=x1[i];
            ans2+=d1[i];
        }
        LL ans=ans1*ans2;
        for(int i=1;i<=n;i++){
            ans-=x1[i]*d1[i]+x2[i]*d2[i]+x1[i]*d2[i]+x2[i]*d1[i];
        }
        printf("%I64d\n",ans);
    }
    return 0;
}