hdu4000树状数组

84 阅读 0 评论 56 点赞

我是靠谱客的博主纯情外套，最近开发中收集的这篇文章主要介绍hdu4000树状数组，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

https://vjudge.net/problem/HDU-4000

给出n个数，求所有的i<j<k且a[i]<a[k]<a[j]的个数

题目也就是让最后那个数第二大。我们输入第i个数字a，那么我们用的树状数组存的就是sum(a-1),sum(a-1)表示在a这个位置，在前i-1个数中，有sum(a-1)个数比a小，那么我们就可以求出在后面的(i+1,n)的序列中，有R=(n-a)-(i-1-sum(a-1))个数比a要大，(n-a)表示有这么多个数比a大，(i-1-sum(a-1))表示前i-1个数里面有sum(a-1)个数比a大，那么R=(n-a)-(i-1-sum(a-1))就表示后面有多少个数比a要大。然后，我们思考一下，a当作三个数里面的最小值，然后让它们组合，是不是就是有C(R,2)即R*(R-1)/2，因为后面的序列都是固定的，所以并没有排序的概念，也就是说，原本序列1 5 4 ,那么我们没有必要去思考1 4 5的情况,因为它已经固定好了（一开始死都想不通....)，所以后面的序列选的时候直接从R个选2个就可以了，然后C(R,2)表示所有的a+两个大的(也就是小中大，小大中都包含在里面了)，那么我们要求的是小大中，所以对于每一个a来说，我们都需要减去小中大的情况，那么小中大=sum(a-1)*R，所以最后答案就是对于（1，n）所有数，求和SUM（C(R,2)-sum(a-1)*R）

#include<iostream>
#include<string>
#include<vector>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<set>
using namespace std;
typedef long long ll;
int n;
ll c[100009];
ll lowbit(ll x)
{
    return x&(-x);
}
ll getsum(ll x)
{
    ll sum=0;
    while(x)
    {
        sum+=c[x];
        x-=lowbit(x);
    }
    return sum;
}
void update(ll x,ll val)
{
    while(x<=n)
    {
        c[x]+=val;
        x+=lowbit(x);
    }
}
int main()
{
    int i,T;
    scanf("%d",&T);
    int Count=1;
    while(T--)
    {
        ll ans=0;
        scanf("%d",&n);
        memset(c,0,sizeof(c));
        for(i=1; i<=n; i++)
        {
            ll a,L,R;
            scanf("%lld",&a);
            update(a,1);
            L=getsum(a-1);
            R=(n-a)-(i-1-L);//前面n-a的含义是有多少个数比a大
            //Left表示有多少个数比a小，(i-1-Left)表示i-1个数里面有这么多个数比a大
            ans+=R*(R-1)/2-L*R;
            //printf("Left==%lld  Right==%lld ans+=%lld  sum+=%lldn",Left,Right,Right*(Right-1)/2,Left*Right);
            //sum%=100000007;
        }
        printf("Case #%d: %lldn",Count++,ans%100000007);
    }
}