出题人的手环(牛客练习赛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;
}
