P1637 三元上升子序列

问题

P1637 三元上升子序列
给定一个整数序列，统计满足下标递增且数值严格递增的三元子序列数量。

数据规模：$n\le 3\times 10^4$，$a_i\le 10^5$。

这是一个很简单的题，想法也很简单，对于一个三元组来说，我们只需要枚举每个中间点，然后计算左边有多少个比它小的，右边有多少个比它大的。

然后把两边的数乘一下，就可以得到当前位置对于答案的贡献了。

▶

P1637

struct BIT {
/* ================================================== */
ll tr[maxn];
int sz;
void init( int N ) { sz = N;
    fill( tr, tr + sz + 1, 0 );
}
void add( int idx, ll val ) {
    for( int i = idx; i <= sz; i += i & -i ) tr[i] += val;
} // 单点修改 a[idx] += val
ll ask( int idx ) {
    ll res = 0;
    for( int i = idx; i; i -= i & -i ) res += tr[i];
    return res;
} // 查询前缀和 [1, idx]
ll ask( int l, int r ) { 
    return ask( r ) - ask( l - 1 ); 
} // 查询区间和 [l, r]
/* ================================================== */
} bit;

int a[maxn], L[maxn], R[maxn];

void solve( ) {
    int n = read( );
    int mx = -1;
    for( int i = 1; i <= n; ++ i ) {
        a[i] = read( );
        mx = max( mx, a[i] );
    }

    bit.init( mx );
    for( int i = 1; i <= n; ++ i ) {
        L[i] = bit.ask( 1, a[i] - 1 );
        bit.add( a[i], 1 );
    }

    bit.init( mx );
    for( int i = n; i; -- i ) {
        R[i] = bit.ask( a[i] + 1, mx );
        bit.add( a[i], 1 );
    }

    ll ans = 0;
    for( int i = 1; i <= n; ++ i ) {
        ans += L[i] * R[i];
    }
    cout << ans << '\n';
}

记录

• 归属：树状数组、贡献统计。
• 新增：固定三元组的中间元素后，左右选择互相独立，答案可以拆成左右计数的乘积。
• 分类：待定。