牛客练习赛38 D 题 出题人的手环 （离散化+树状数组求逆序对+前缀和）

时间：2022-08-09 08:25:21

链接：https://ac.nowcoder.com/acm/contest/358/D
来源：牛客网

出题人的手环
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 524288K，其他语言1048576K
64bit IO Format: %lld

题目描述

出题人的妹子送了出题人一个手环，这个手环上有 n 个珠子，每个珠子上有一个数。
有一天，出题人和妹子分手了，想把这个手环从两个珠子间切开，并按顺时针顺序展开成一条链。

可以发现，这条链一共有 n 种可能性。求这 n 种可能性的逆序对数之积模 1000000007。

输入描述:

第一行一个数 n，表示珠子个数。
接下来一行 n 个数，以顺时针顺序给出每个珠子上的整数

输出描述:

一个数，表示答案。
示例1

输入

复制

4

1 3 2 3

输出

复制

24

说明

一共有 4 种方式：
1 3 2 3;3 1 3 2;2 3 1 3;3 2 3 1;
逆序对数分别为 1，3，2，4，积为 24。

备注:

n<=200000，-10^9<=珠子上的整数<=10^9。

思路：
个人觉得还是一个很不错的题目。
首先，因为数值范围比较大，先离散化一下。 （不会离散化的点此去学其次先根据离散化后的数组标记下求一个前缀和，前缀和 sum[i] 维护的是 离散化后的数组（下面成为新数组）中的1~i中累计的个数和，需要多开一个vis数组，
然后先根据树状数组来求出新数组的逆序对的总数。（具体求法和细节看code和注释）
然后我们把当前新数组中的第一个数放在最后一个位置，这样对一个数组的逆序对总和的影响是 减去 2~n位置中小于a[1]的个数，加上2~n位置中大于a[1]的个数，
而这恰好可以用我们刚刚求得前缀和来解决。
然后每一个调整后得数组的总和乘起来，记得取模就好了 （算法学习（二）——树状数组求逆序数）
细节见我的代码：
#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <queue>

#include <stack>

#include <map>

#include <set>

#include <vector>

#define sz(a) int(a.size())

#define all(a) a.begin(), a.end()

#define rep(i,x,n) for(int i=x;i<n;i++)

#define repd(i,x,n) for(int i=x;i<=n;i++)

#define pii pair<int,int>

#define pll pair<long long ,long long>

#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)

#define MS0(X) memset((X), 0, sizeof((X)))

#define MSC0(X) memset((X), '\0', sizeof((X)))

#define pb push_back

#define mp make_pair

#define fi first

#define se second

#define eps 1e-6

#define gg(x) getInt(&x)

#define db(x) cout<<"==  "<<x<<"  =="<<endl;

using namespace std;

typedef long long ll;

inline void getInt(int* p);

const int maxn=;

const int inf=0x3f3f3f3f;

/*** TEMPLATE CODE * * STARTS HERE ***/

int n;

ll a[maxn];

ll b[maxn];

ll tree[maxn];

ll vis[maxn];

ll sum[maxn];

const ll mod=1000000007ll;

int lowbit(int x)

{

    return x&(-*x);

}

void add(int i)

{

    while(i<=maxn)

    {

        tree[i]+=;

        i+=lowbit(i);

    }

}

ll query(int i)

{

    ll res=;

    while(i>)

    {

        res+=tree[i];

        i-=lowbit(i);

    }

    return res;

}

int main()

{

    gbtb;

    cin>>n;

    repd(i,,n)

    {

        cin>>a[i];

        b[i]=a[i];

    }

    sort(b+,b++n);// 辅组数组的排序

    int cnt=unique(b+,b++n)-b-; // 去重

    repd(i,,n)

    {

        a[i]=lower_bound(b+,b++cnt,a[i])-b;  // 离散化挂的核心code

        vis[a[i]]++;// 标记

    }

    repd(i,,n)

    {

        sum[i]=sum[i-]+vis[i]; //  求前缀和，sum[i]代表1~的个数和。

    }

    ll tot=0ll;// 一个数组总的逆序对总和。

    repd(i,,n)

    {

        add(a[i]);

        tot+=i-query(a[i]); // quert函数返回的是这个数组中小于等于a[i]的数量

        // 那么i-quert 就是 数组中大于a[i]的数量，那么就是逆序对的数量。

        //  树状数组 中维护的是一个单点修改，区间查询的树状数组

        //  我们add(a[i]) 就是向树状数组中增加一个a[i]出现的次数。

        //  query(a[i]) 查询的就是 1 ~ a[i] 出现的数量总和。

        tot=(tot+mod)%mod;

    }

    ll ans=tot;

    for(int i=;i<=n-;i++)

    {

        tot=tot-(sum[a[i]-])+n-sum[a[i]];

        // -(sum[a[i]-1]) 是减去比a[i]小的个数，即去掉了以a[i]为左的逆序对，

        // +n-sum[a[i]]; 是加上 以a[i]为右的逆序对，即加上数组中有多少个数大于a[i]

        tot=(tot+mod)%mod;

        ans*=tot;

        ans=(ans+mod)%mod;

    }

    cout<<ans<<endl;

    return ;

}

inline void getInt(int* p) {

    char ch;

    do {

        ch = getchar();

    } while (ch == ' ' || ch == '\n');

    if (ch == '-') {

        *p = -(getchar() - '');

        while ((ch = getchar()) >= '' && ch <= '') {

            *p = *p *  - ch + '';

        }

    }

    else {

        *p = ch - '';

        while ((ch = getchar()) >= '' && ch <= '') {

            *p = *p *  + ch - '';

        }

    }

}

参考了这位大佬的题解：https://blog.csdn.net/qq_40655981/article/details/86547600

 
Maxn   详细X
网络释义
Maxn: 楠楠
int maxN: 乱数产生的最大数字

相关文章