链接
[https://ac.nowcoder.com/acm/contest/358/D]
题意
链接：https://ac.nowcoder.com/acm/contest/358/D
来源：牛客网
题目描述
出题人的妹子送了出题人一个手环，这个手环上有 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，-109。
分析
首先我们知道用树状数组求，逆序数
那么这题由于数据范围是-109。
开一个数组必然是不够的，所以首先离散化一下,就可以求出第一次的逆序数
那么每次变化一个顺序，可以把第一个元素弄到最后，那么逆序数会变为多少呢？
首先对于某个数，求出小于它的数的个数
int pos1 = lower_bound(d,d+n,a[i+1].va) - d;
x[i] = pos1; //比b[i]小的总个数
以及大于它的数的个数。
int pos2 = upper_bound(d,d+n,a[i+1].va) - d;
y[i] = n - pos2; //比b[i]大的总个数
这里用了lower_bound和upper_bound,
for(int i = 0; i < n; ++i)
{
int pos1 = lower_bound(d,d+n,a[i+1].va) - d;
int pos2 = upper_bound(d,d+n,a[i+1].va) - d;
x[i] = pos1; //比b[i]小的总个数
y[i] = n - pos2; //比b[i]大的总个数
//cout<<x[i]<<' '<<y[i]<<endl;
}
后面遍历剩下乘积取模即可
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=1e9+7;
const int N=2e5+10;
int n;
int b[N];
int c[N];
int d[N];
int x[N];
int y[N];
struct node{
int va,pos;
}a[N];
bool cmp(node x,node y){
return x.va<y.va;
}
void update(int i,int va){
for(int j=i;j<=n;j+=j&-j)
c[j]+=va;
}
int getsum(int x){
int ans=0;
for(int i=x;i;i-=i&-i)
ans+=c[i];
return ans;
}
int main(){
//freopen("in.txt","r",stdin);
while(cin>>n){
memset(c,0,sizeof(c));
for(int i=1;i<=n;i++){
cin>>a[i].va;
d[i-1]=a[i].va;
a[i].pos=i;
}
sort(d,d+n);
for(int i = 0; i < n; ++i)
{
int pos1 = lower_bound(d,d+n,a[i+1].va) - d;
int pos2 = upper_bound(d,d+n,a[i+1].va) - d;
x[i] = pos1; //比b[i]小的总个数
y[i] = n - pos2; //比b[i]大的总个数
//cout<<x[i]<<' '<<y[i]<<endl;
}
sort(a+1,a+n+1,cmp);
int cnt=1;
for(int i=1;i<=n;i++){
if(i!=1&&a[i].va!=a[i-1].va)
cnt++;
b[a[i].pos]=cnt;
}
ll sum=0;
for(int i=1;i<=n;i++){
update(b[i],1);
sum+=i-getsum(b[i]);
sum%=mod;
}
//cout<<sum<<endl;
ll ans=sum;
for(int i=0;i<n-1;i++){
sum=((sum-x[i]+y[i])%mod+mod)%mod;
ans=ans*sum%mod;
}
cout<<ans<<endl;
}
return 0;
}