HDU5147 Sequence II（Dec. 8th, 2018）

逆序对 数据结构

题目来源

题意：给定长度为$n$的序列s，求数对$(a,b,c,d)$满足$1≤a<b<c<d≤n$且$s_a<s_b$，$s_c<s_d$。

思路：
1. 求出所有位置$i$的顺序对数量$seq_i$。
2. 维护指针$i$扫描数组，令$b=i$，则在$[1,i)$中小于$s_i$的数的数量$seq_i$即合法的$a$的数量，这样就确定了第一个顺序对。
3. 反转数组，再次统计顺序对数量$qes_i$，就可以得到在$(i,n]$中大于$s_i$的顺序对数，则

$$ans=\sum_{i=1}^n(\sum_{j=1}^iseq_i)\times qes_i$$

代码：

// La Lune
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define wt(x) (x & -x)
using namespace std;
typedef long long lune;
const lune N = 1e5 + 5;
lune n, c[N], seq[N], qes[N], a[N];
inline void add(lune pos, lune x){
    for(lune i = pos; i <= n; i += wt(i))
        c[i] += x;
}
inline lune que(lune pos){
    lune res = 0;
    for(lune i = pos; i >= 1; i -= wt(i))
        res += c[i];
    return res;
}
int main(){
    lune T; scanf("%lld", &T);
    while(T--){
        memset(seq, 0, sizeof(seq));
        memset(qes, 0, sizeof(qes));
        memset(c, 0, sizeof(c));
        scanf("%lld", &n); lune ans = 0;
        for(lune i = 1; i <= n; i++){
            scanf("%lld", &a[i]);
            seq[i] = que(a[i]);
            add(a[i], 1);
        }
        memset(c, 0, sizeof(c));
        for(lune i = n; i >= 1; i--){
            qes[i] = (n - i) - que(a[i]);
            add(a[i], 1);
        }
        lune res = 0;
        for(lune i = 1; i <= n; i++){
            ans += res * qes[i];
            res += seq[i];
        }
        printf("%lld\n", ans);
    }
    return 0;
}