楼兰图腾

楼兰图腾

题目链接

牛客

AcWing

题目概述

给出一组输入格式为((1,y_1),(2,y_2),dots ,(n,y_n))的输入,其中的(y_1,y_2,cdots,y_n)是(1-N)的某个排列,现在计算可以随机选取三个序偶,其中第一个分量(X)满足(1leq i < j < k leq n),分别计算输出可以满足下面两种约束条件的序偶选择方法的个数:

1. (y_i > y_j, y_j < y_k);
2. (y_i < y_j, y_j > y_k).
   数据规模:

[nleq 2cdot 10^5 ]

并且对于输出的结果保证不会超出int64的范围.

思路分析

这题主要的工作是计算(y_i)左面比它小(大)的数和右面比它小(大)的个数有多少个,假设左面比它小的数有(left)个,右面比它它小的有(right)个,那么显然,它可以构成满足上面条件2的选择有(left*right)个,然后从第二个开始依次计算,累加计算到倒数第二个,就得到第二个的选择的个数.
对于第一个的计算仍然沿用第一个的方法,可以得到左面比这个数大的有(i-1-left),右面比它大的有(n-i-right),用同样的方法计算第一个条件要求的选择的个数.

很明显可以用一个for循环计算数(y_i)左面右面比它小的数字的个数,时间复杂度为(O(n)),整个时间复杂度为(O(n^2)),结合数据范围(10^5),总的计算量大约为(10^{10}),一定会TLE的.

使用树状数组可以在(O(log(n)))的时间内统计出在(y_i)左面或者右面比(y_i)小的数的个数.

统计(y_i)右面比它小的元素的个数:

    memset(tree, 0, sizeof(tree));
    for(int i = n; i > 0; --i){
        rights[i] += sum(a[i]-1);
        add(a[i],1);
    }

因为(a[i]-1 < a[i]),所以只要计算的从第(1)项到第(a[i]-1)中已经出现的数出现的个数,就是(a[i])右面比它小的数的个数,然后把这个(a[i])加入进去,表示此时又添加了一个元素.
以题目中给出的样例为例:

5
1 5 3 2 4

1. i=5

lefts:

1	2	3	4	5
0	0	0	0	0

tress:

1	2	3	4	5
0	0	0	1	0

2. i=4

lefts:

1	2	3	4	5
0	0	0	0	0

tress:

1	2	3	4	5
0	0	0	1	2

3. i=3

lefts:

1	2	3	4	5
0	0	1	0	0

tress:

1	2	3	4	5
0	0	1	1	3

4. i=2

lefts:

1	2	3	4	5
0	3	1	0	0

tress:

1	2	3	4	5
0	1	1	1	3

5. i=1

lefts:

1	2	3	4	5
0	3	1	0	0

tress:

1	2	3	4	5
1	1	1	2	4

在上面的计算过程,通过sum可以计算比(a[i])小的元素的个数,也就是统计(1-(a[i]-1))已经出现了几个,然后通过add(a[i],1)标记(a[i])出现,这样从后向前迭代计算可以得到在(a[i])右面且比(a[i])小的元素的个数,然后可以以相同的方式正向迭代计算出(a[i])左面比它小的元素的个数.

树状数组add和sum原来略去不表

代码

/*
 * @Author: Shuo Yang
 * @Date: 2020-08-04 09:35:00
 * @LastEditors: Shuo Yang
 * @LastEditTime: 2020-08-04 10:59:31
 * @FilePath: /Code/test.cpp
 */
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+5;
int tree[N];
int a[N];
int n = 0;

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

void add(int k, int x){
    while( k <= n){
        tree[k] += x;
        k += lowbit(k);
    }
}

int sum(int k){
    int ans = 0;
    while( k > 0){
        ans += tree[k];
        k -= lowbit(k);
    }
    return ans;
}

ll lefts[N];
ll rights[N];

int main(int argc, const char** argv) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n;
    for(int i = 1; i <= n; ++i)
        cin>>a[i];
    memset(tree, 0, sizeof(tree));
    for(int i = n; i > 0; --i){
        rights[i] += sum(a[i]-1);
        add(a[i],1);
    }
    memset(tree, 0, sizeof(tree));
    for(int i = 1; i <= n; ++i){
        lefts[i] += sum(a[i]-1);
        add(a[i],1);
    }
    ll ans = 0;
    for(int i = 2; i < n; ++i)
        ans += 1ll*(i-1-lefts[i])*(n-i-rights[i]);
    cout<< ans <<" ";
    ans = 0;
    for(int i = 2; i < n; ++i){
        ans += 1ll*lefts[i]*rights[i];
    }
    cout<<ans<<endl;
    return 0;
}

其它