hdu 5792 树状数组+离散化+思维

题目大意：

Given a sequence A with length n,count how many quadruple (a,b,c,d) satisfies: $a \neq b \neq c \neq d, 1 \leq a < b \leq n, 1 \leq c < d \leq n, A_{a} < A_{b}, A_{c} > A_{d}$

$a \neq b \neq c \neq d, 1 \leq a < b \leq n, 1 \leq c < d \leq n, A_{a} < A_{b}, A_{c} > A_{d}$

由于答案会多算进去a=c || a=d || b=c || b=d的情况，那么枚举这四种情况减去就可以了，a=c那么必定b!=d，同理其他

a=c：ans-=hmn[i]*hmx[i]

a=d：ans-=mx[i]*hmx[i]

b=c：ans-=mn[i]*hmn[i]

b=d：ans-=mx[i]*mn[i]

反思与总结：

//对于树状数组，我一直有所顾忌，因为就比如num【4】的值并不加和在num【6】里，其实没必要了，因为树状数组用到的操作就是求和和求最大最小值，然后求和的话并不是直接用这些数组元素，而是一个模板函数去求，这个函数求出来的就是1~i的加和，然后求某一个区间的话就是相减，没有任何问题，而且对于树状数组维护的东西又有了较为深刻的认识（可以把其他的值一转化来维护）；

//以后的话可以将某些对象抽象，从抽象层面考虑问题，也许问题会变得更容易想，这就是教主说的改变思维方式吧，走出思维的舒适区；

//我还发现对于一个对象在一个程序中，可以分别赋予多种抽象，前提是一个用完之后再用另一个不能混着来；

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

typedef long long ll;

const int maxn = 50000+10;
int max_[maxn],min_[maxn],hmin_[maxn],hmax_[maxn];
int num[maxn],a[maxn],b[maxn],sum[maxn];
ll res;
int n,m;

int lowbit(int x)
{
    return x&(-x);
}

void add(int x)
{
    while(x<=m)
    {
        num[x]++;
        x+=lowbit(x);
    }
}

int query(int x)
{
    int ans=0;
    while(x>=1)
    {
        ans+=num[x];
        x-=lowbit(x);
    }
    return ans;
}

int main()
{
    while(scanf("%d",&n)==1)
    {
        for(int i=1;i<=n;i++) scanf("%d",&a[i]),b[i]=a[i];
        sort(b+1,b+n+1);
        m=unique(b+1,b+n+1)-(b+1);
        for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+m+1,a[i])-b;
        memset(num,0,sizeof(num));
        memset(sum,0,sizeof(sum));
        for(int i=1;i<=n;i++)
        {
            min_[i]=query(a[i]-1);
            max_[i]=query(m)-query(a[i]);
            sum[i]=sum[i-1]+min_[i];
            add(a[i]);
        }
        memset(num,0,sizeof(num));
        for(int i=n;i>=1;i--)
        {
            hmin_[i]=query(a[i]-1);
            hmax_[i]=query(m)-query(a[i]);
            add(a[i]);
        }
        res=0;
        ll num1,num2;
        for(int i=1;i<=n;i++)
        {
            num1=max_[i];
            num2=sum[n];
            res+=num1*num2;
        }
        //a=c&&b!=d;
        for(int i=1;i<=n;i++)
        {
            num1=hmin_[i];
            num2=hmax_[i];
            res-=num1*num2;
        }
        //a!=c&&b=d;
        for(int i=1;i<=n;i++)
        {
            num1=min_[i];
            num2=max_[i];
            res-=num1*num2;
        }
        //a=d&&b!=c;
        for(int i=1;i<=n;i++)
        {
            num1=max_[i];
            num2=hmax_[i];
            res-=num1*num2;
        }
        //a!=d&&b=c;
        for(int i=1;i<=n;i++)
        {
            num1=hmin_[i];
            num2=min_[i];
            res-=num1*num2;
        }
        printf("%I64d
",res);
    }
    return 0;
}