首页 > 代码库 > HDU- 4000 Fruit Ninja(树状数组)

HDU- 4000 Fruit Ninja(树状数组)

2024-09-28 10:15:39   217人阅读

题目大意

给出一串数字，是1到n的一种排列，找出  x<z<y 的三个数字的个数（在数列中x,y,z按顺序出现）

分析

刚刚拿到题目，就有一种树状数组处理比当前数字大或者小的感觉，一开始我锁定了y，在y的右边和左边分别找到比y小的数字，然而这样只能保证 z<y,x<y，不能保证x<z。所以最终获得的三个数字会有x<z<y,与z<x<y两种可能。筛去z<x<y并不好处理。

所以：

如果锁定x寻找右边比x大的数字，可以得到x<y<z,以及x<z<y两种可能。x<y<z可通过固定y寻找左边比它小，右边比它大来计数的方法直接筛去。

注意乘法时候的数据范围。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAX_NUM            100005
#define modd             100000007
#define lowbit(q)            (q)&(-(q))
typedef long long int LL;
int c[MAX_NUM];
void update(int i ){
    for (int j = i ; j <= 1e5 ; ){
        c[j] ++ ;
        j += lowbit(j);
    }
}
int query(int i){
    int sum = 0; 
    while(i){
        sum += c[i];
        i -= lowbit (i);
    }
    return sum ;
}
LL num[MAX_NUM];
LL pre[MAX_NUM];
LL las[MAX_NUM];
int main(int argc, char const *argv[])
{
    int t;
    scanf("%d",&t);
    int vs = 0;
    while(t--){
        int n;
        scanf("%d",&n);
        LL ans = 0;
        memset(c,0,sizeof(c));
        for(int i = 1 ; i <= n; i++){
            scanf("%lld",&num[i]);
            pre[i] = query(num[i]-1);
            update(num[i]);
        }
        memset(c,0,sizeof(c));
        for(int i = n ; i >0 ; i--){
            las[i] = (n-i) - query(num[i]);
            ans =(ans + (las[i]*(las[i]-1))/2 - (pre[i]*las[i]) )%modd;
            update(num[i]);
        }
        printf("Case #%d: %lld\n",++vs,ans );
    }
    return 0;
}

 

HDU- 4000 Fruit Ninja(树状数组)


联系
我们