hdu 2492 Ping pong (线段树)

题目大意：

对于任意一组 x,y,z  满足

x<y<z && (a[x] < a[y] < a[z]  ||   a[x]>a[y]>a[z] )   

如果有其中一个元素不同，则称为不同。

问给出的序列里有多少组不同。

思路：

用线段树维护  一个数左边有多少个数比其小

右边有多少个数比其大。

然后相乘就得当前y可以得到的数量。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define lson num<<1,s,mid
#define rson num<<1|1,mid+1,e
#define maxn 100005
#pragma comment (linker,"/STACK:102400000,102400000")
using namespace std;
typedef long long LL;

int tre[maxn<<2];

void pushup(int num)
{
    tre[num]=tre[num<<1]+tre[num<<1|1];
}

int query(int num,int s,int e,int l,int r)
{
    if(l<=s && r>=e)
    {
        return tre[num];
    }
    int mid=(s+e)>>1;

    if(r<=mid)return query(lson,l,r);
    else if(l>mid)return query(rson,l,r);
    else
    {
        return query(lson,l,mid)+query(rson,mid+1,r);
    }
}

void update(int num,int s,int e,int pos)
{
    if(s==e)
    {
        tre[num]++;
        return;
    }
    int mid=(s+e)>>1;
    if(pos<=mid)update(lson,pos);
    else update(rson,pos);

    pushup(num);
}

int save[20005];
int lit[20005];
int big[20005];

int main()
{
    int T;
    int n;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        memset(tre,0,sizeof tre);

        int Max=-1;

        for(int i=1;i<=n;i++)
        {
            scanf("%d",&save[i]);
            Max=max(save[i],Max);
        }

        for(int i=1;i<=n;i++)
        {
            lit[i]=query(1,1,Max,1,save[i]);
            update(1,1,Max,save[i]);
        }

        memset(tre,0,sizeof tre);
    
        for(int i=n;i>=1;i--)
        {
            big[i]=query(1,1,Max,save[i],Max);
            update(1,1,Max,save[i]);
        }

        LL ans=0;
        for(int i=1;i<=n;i++)
        {
            ans+=lit[i]*big[i];
            ans+=(i-1-lit[i])*(n-i-big[i]);
        }

        printf("%I64d\n",ans);
    }
    return 0;
}

hdu 2492 Ping pong (线段树),布布扣,bubuko.com

hdu 2492 Ping pong (线段树)

原文：http://blog.csdn.net/u010709592/article/details/24204931