楼兰图腾

不念不忘少年蓝@ 2023-03-06 03:27 7阅读 0赞

# 楼兰图腾 #

![博客图片][format_png]

## 题目链接 ##

[牛客][Link 1]

[AcWing][]

## 题目概述 ##

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

1.   y i > y j , y j < y k y\_i > y\_j, y\_j < y\_k yi>yj,yj<yk;
2.   y i < y j , y j > y k y\_i < y\_j, y\_j > y\_k yi<yj,yj>yk.  
    数据规模:  
     n ≤ 2 ⋅ 1 0 5 n\\leq 2\\cdot 10^5 n≤2⋅105  
    并且对于输出的结果保证不会超出`int64`的范围.

## 思路分析 ##

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

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

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

统计 y i y\_i yi右面比它小的元素的个数:

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

> 5  
> 1 5 3 2 4

1.  i=5

**lefts:**

**tress:**

1.  i=4

**lefts:**

**tress:**

1.  i=3

**lefts:**

**tress:**

1.  i=2

**lefts:**

**tress:**

1.  i=1

**lefts:**

**tress:**

在上面的计算过程,通过`sum`可以计算比 a \[ i \] a\[i\] a\[i\]小的元素的个数,也就是统计 1 − ( a \[ i \] − 1 ) 1-(a\[i\]-1) 1−(a\[i\]−1)已经出现了几个,然后通过`add(a[i],1)`标记 a \[ i \] a\[i\] a\[i\]出现,这样从后向前迭代计算可以得到在 a \[ i \] a\[i\] a\[i\]右面且比 a \[ i \] a\[i\] 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;
    }

## 其它 ##

[format_png]: /images/20230208/4bedd9ba6324420886fae2962434662b.png
[Link 1]: https://ac.nowcoder.com/acm/contest/1032/A
[AcWing]: https://www.acwing.com/problem/content/243/

楼兰图腾

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关楼兰图腾

相关狼图腾

相关洛谷P1498 南蛮图腾

相关 241. 楼兰图腾(树状数组)