出题人的手环(牛客练习赛38D 离散化+树状数组)

题目链接(https://ac.nowcoder.com/acm/contest/358/D)

题目描述

出题人的妹子送了出题人一个手环，这个手环上有 n 个珠子，每个珠子上有一个数。

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

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

输入描述:

第一行一个数 n，表示珠子个数。

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

样例输入

4

1 3 2 3

样例输出

24

备注

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

题目就是求这n个顺时针排列的逆序数乘积，那么重点就是求逆序数啦，首先求出第一个排列的逆序数，看一下数据范围，n方肯定不行，那么考虑离散化加树状数组N*logN，求出逆序数之后，再从后向前遍历这个数组，考虑每一次的排列的变化，相当于将最后一个数移到第一个位置，那么这个数移动之后造成的逆序数的变化可以O(1)计算出来的，然后每一次的逆序数乘在一起就好啦，嘤嘤嘤，具体实现看我代码qwq

#include <set>

#include <map>

#include <queue>

#include <stack>

#include <math.h>

#include <bitset>

#include <vector>

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#define MAXN 1010100

#define LL long long

#define fi first

#define se second

#define mp make_pair

#define pb push_back

#define ll __int64

#define INF 0x7fffffff

#define cs(s) freopen(s,"r",stdin)

#define mem(x) memset(x,0,sizeof(x))

#define PI acos(-1)

#define eps 1e-10

using namespace std;

int gcd(int a,int b){return b?gcd(b,a%b):a;}

int lcm(int a,int b){return a/gcd(a,b)*b;}

LL powmod(LL a,LL b,LL MOD){LL ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}

//head

LL sum[200001],tree[200001],mod=1000000007,vis[200001],a[200001],b[200001];

int n;

void add(int t){//树状数组更新

	for(int i=t;i<=n;i+=(i)&(-i))tree[i]+=1,tree[i]%=mod;

}

LL que(int t){//树状数组求和，返回的是1-t的和

	LL q=0;

	for(int i=t;i;i-=(i)&(-i))q+=tree[i],q%=mod;

	return q;

}

int main(){

	ios::sync_with_stdio(false);

	cin>>n;

	for(int i=1;i<=n;i++)cin>>a[i],b[i]=a[i];

		sort(b+1,b+1+n);

	int cnt=unique(b+1,b+1+n)-b-1;//离散化操作

	for(int i=1;i<=n;i++){

		a[i]=lower_bound(b+1,b+1+cnt,a[i])-b;

		vis[a[i]]++;

	}

	for(int i=1;i<=n;i++)sum[i]=sum[i-1]+vis[i];//记录1-i的个数和

	LL op=0;

	for(int i=1;i<=n;i++){//树状数组求逆序数

		add(a[i]);

		op+=que(n)-que(a[i]);

		op%=mod;

	}

	LL tt=op;

	for(int i=n;i>=2;i--){

		tt+=(sum[a[i]-1]-sum[n]+sum[a[i]]+1000ll*mod)%mod;//移动后的逆序数变化

		tt%=mod;

		op*=tt;

		op%=mod;

	}

	cout<<op<<endl;

	return 0;

}