http://acm.hdu.edu.cn/showproblem.php?pid=4000

x<z<y不好直接求,那么可以先求出x<{y,z}的个数,再减去x<y<z的个数。
由于序列是1~N的某个排列,所以比x小的数一定是x-1。
利用这一点,结合树状数组即可求出答案。

#include<cstdio>
#include<cstring>

const int maxn = 100010;
const int mod = 100000007;
long long arry[maxn], n;

inline int low(int x)
{
    return x & (-x);
}

long long getsum(int x)
{
    long long s = 0;
    while (x)
    {
        s += arry[x];
        x -= low(x);
    }
    return s;
}

void update(int x)
{
    while (x <= n)
    {
        arry[x]++;
        x += low(x);
    }
}

int main()
{
    int m, cas = 1;
    scanf("%d", &m);
    while (m--)
    {
        scanf("%d", &n);
        int t;
        long long tot = 0, tem = 0, k, leftmin, rightmax, ans = 0;
        memset(arry, 0, sizeof(arry));
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &t);
            leftmin = getsum(t);
            update(t);
            rightmax = n + leftmin - i - t + 1; /// 利用序列的性质
             tot = rightmax * (rightmax - 1) / 2 % mod;
            tem = leftmin * rightmax % mod;
            ans = ((ans + tot - tem) % mod + mod) % mod;
        }
        printf("Case #%d: %I64d\n", cas++, ans);
    }
    return 0;
}

Comments

comments powered by Disqus