Inversions After Shuffle CodeForces

大意: 给定一个$n$排列, 随机选一个区间, 求将区间随机重排后整个序列的逆序对期望.

考虑对区间$[l,r]$重排后逆序对的变化, 显然只有区间[l,r]内部会发生改变

而长为$k$的随机排列期望逆序为$\frac{k(k-1)}{4}$(证明考虑逆序与顺序对称性)

所以$[l,r]$的贡献即为$inv(1,n)-inv(l,r)+\frac{(r-l+1)(r-l)}{4}$

所以就转化为求$\sum\limits_{1\le l\le r\le n}inv(l,r)$

对于逆序对$(x,y)$, 我们枚举$y$, 就有贡献$(n-y+1)\sum\limits_{\substack{1\le x< y\\ a_y<a_x}}x$

就转化为二维数点问题, 可以用树状数组解决.

用$long\space double$不知道为什么会WA, 改成$double$直接过了

#include <iostream>

#include <sstream>

#include <algorithm>

#include <cstdio>

#include <math.h>

#include <set>

#include <map>

#include <queue>

#include <string>

#include <string.h>

#include <bitset>

#define REP(i,a,n) for(int i=a;i<=n;++i)

#define PER(i,a,n) for(int i=n;i>=a;--i)

#define hr putchar(10)

#define pb push_back

#define lc (o<<1)

#define rc (lc|1)

#define mid ((l+r)>>1)

#define ls lc,l,mid

#define rs rc,mid+1,r

#define x first

#define y second

#define io std::ios::sync_with_stdio(false)

#define endl '\n'

#define DB(a) ({REP(__i,1,n) cout<<a[__i]<<' ';hr;})

using namespace std;

typedef long long ll;

typedef double db;

const int N = 1e5+10;

int n;

db c[2][N];

void add(int id, int x, int v) {

	for (; x; x^=x&-x) c[id][x]+=v;

}

db qry(int id, int x) {

	db ret = 0;

	for (; x<=n; x+=x&-x) ret+=c[id][x];

	return ret;

}

int main() {

	scanf("%d", &n);

	db ans = 0;

	REP(i,1,n) {

		int t;

		scanf("%d", &t);

		ans += qry(0,t)*n*(n+1)/2-(n-i+1)*qry(1,t)+((db)i*i*i-i)/12;

		add(0,t,1), add(1,t,i);

	}

	ans /= (db)n*(n+1)/2;

	printf("%.12lf\n", ans);

}

巴特西

Inversions After Shuffle CodeForces - 749E (概率,期望)

最新文章

热门文章