HDU_5792_WorldIsExploding（樹狀數組&&離散化）

World is Exploding

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 585    Accepted Submission(s): 274

Problem Description Given a sequence A with length n,count how many quadruple (a,b,c,d) satisfies: a≠b≠c≠d,1≤a<b≤n,1≤c<d≤n,Aa<Ab,Ac>Ad .  

Input The input consists of multiple test cases.

Each test case begin with an integer n in a single line.

The next line contains n integers A1,A2⋯An .

1≤n≤50000

0≤Ai≤1e9  

Output For each test case,output a line contains an integer.  

Sample Input

4
2 4 1 3
4
1 2 3 4
        

Sample Output

1
0
        

Author ZSTU  

Source 2016 Multi-University Training Contest 5  

Recommend wange2014

題意

給出一個數串A

然後問你滿足a，b，c，d各不相同且

a<b,c<d,Aa<Ab,Ac>Ad

的4元組個數

解題思路

如果這個題目是二進制組的話

就變成了樹狀數組水題

那麼4元組其實可以拆解為2個二進制組

樹狀數組求解出

rbig，lbig，rsmall，lsmall

分别代表i位置左側比它大的個數，右側比它大的個數，左側比它小的個數，右側比它小的個數

問題是如果把兩個二進制組的解乘起來

那麼有一些重複計數的

我們發現這些重複的情況有

a=c b=d（這個其實是0個，因為大于小于都是嚴格的）

a=c b>d（這個枚舉a，然後b和d的選擇是沒有交集的把rbig和rsmall乘起來就可以了）

a<c b=d lbig*lsmall

a=d rbig*lbig

b=c rsmall*lsmall

減掉這些多算的就可以了

兩個點，一個需要離散化，一個有重複數字

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

typedef unsigned long long LL;
const int M=5e4+5;

int nu[M],nu2[M];

LL t1[M];
LL lbig[M],lsmall[M],rbig[M],rsmall[M];
inline int lowbit(int x)
{
    return x&(-x);
}
void add(LL t[],int x,int v)
{
    for(int i=x;i<M;i+=lowbit(i))
        t[i]+=v;
}
LL getsum(LL t[],int x)
{
    LL ans=0;
    for(int i=x;i;i-=lowbit(i))
        ans+=t[i];
    return ans;
}
//離散化
int nn;
int findv(int x)
{
    return lower_bound(nu2+1,nu2+nn+1,x)-nu2;
}

int main()
{
//    nu2[1]=5;
//    nu2[2]=6;
//    nu2[3]=7;
//    nu2[4]=8;
//    nu2[5]=9;
//    nu2[6]=10;
//    nn=6;
//    cout<<findv(8)<<endl;
    //freopen("1.in","r",stdin);
    int n;
    LL sumrbig,sumrsmall,sumlbig,sumlsmall;
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=1;i<=n;i++)
            scanf("%d",&nu[i]);
        sumrbig=sumrsmall=sumlbig=sumlsmall=0;
        memset(t1,0,sizeof(t1));
        memcpy(nu2,nu,sizeof(nu));
        sort(nu2+1,nu2+n+1);
        nn=unique(nu2+1,nu2+n+1)-nu2-1;
        //cout<<nn<<endl;
        for(int i=1;i<=n;i++)
        {
            int tmp=findv(nu[i]);
            add(t1,tmp,1);
            lsmall[i]=getsum(t1,tmp-1);
            lbig[i]=i-getsum(t1,tmp);
            sumlbig+=lbig[i];
            sumlsmall+=lsmall[i];
        }
        memset(t1,0,sizeof(t1));
        for(int i=n;i>=1;i--)
        {
            int tmp=findv(nu[i]);
            add(t1,tmp,1);
            rsmall[i]=getsum(t1,tmp-1);
            rbig[i]=n-i-getsum(t1,tmp)+1;
            sumrbig+=rbig[i];
            sumrsmall+=rsmall[i];
        }
        //for(int i=1;i<=n;i++)
        //    cout<<"i "<<i<<" ls "<<lsmall[i]<<" lb "<<lbig[i]<<" rs "<<rsmall[i]<<" rb "<<rbig[i]<<endl;
        LL ans=sumrbig*sumrsmall;
        //cout<<"ans1 "<<ans1<<endl;
        //LL ans2=0;
        for(int i=1;i<=n;i++)
            ans-=lsmall[i]*rsmall[i];
        for(int i=1;i<=n;i++)
            ans-=lbig[i]*rbig[i];
            //cout<<"ans2 1 "<<ans2<<endl;
        for(int i=1;i<=n;i++)
            ans-=lsmall[i]*lbig[i];
            // cout<<"ans2 2 "<<ans2<<endl;
        for(int i=1;i<=n;i++)
            ans-=rbig[i]*rsmall[i];
            //cout<<"ans2 3 "<<ans2<<endl;
        printf("%I64u\n",ans);
    }
    return 0;
}