【Codeforces 749E】Inversions After Shuffle

相关链接

题目传送门:http://codeforces.com/contest/749/problem/E
官方题解:http://codeforces.com/blog/entry/49186

解题报告

考虑从期望的定义下手
就是要求所有区间的逆序对的和
于是我们枚举右端点,然后算贡献
用$BIT$来维护,时间复杂度:$O(n \log n)$

Code

#include<bits/stdc++.h>
#define LL long long
#define lowbit(x) ((x)&-(x))
using namespace std;

const int N = 100009;

int n, p[N]; 

inline int read() {
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

class Fenwick_Tree{
	double sum[N];
	public:
		inline void init() {
			memset(sum, 0, sizeof(sum));
		}
		inline void modify(int p, int d = 1) {
			for (int i = p; i <= n; i += lowbit(i)) {
				sum[i] += d;
			}
		}
		inline double query(int p) {
			double ret = 0;
			for (int i = p; i; i -= lowbit(i)) {
				ret += sum[i];
			}
			return ret;
		}
}BIT;

int main() {
	n = read();
	for (int i = 1; i <= n; i++) {
		p[i] = read();
	}
	double ans = 0, psm = 0;
	for (int i = n; i; i--) {
		ans += BIT.query(p[i]);
		BIT.modify(p[i]);	
	}	
	ans *= n * (n + 1ll);
	BIT.init();
	for (int i = 1; i <= n; i++) {
		LL t1 = BIT.query(p[i]);
		LL t2 = i * (i - 1ll) / 2 - t1;
		ans += (psm += t1 - t2);
		BIT.modify(p[i], i);
	}
	printf("%.15lf\n", ans / n / (n + 1));
	return 0;
}

26 thoughts to “【Codeforces 749E】Inversions After Shuffle”

  1. I have been surfing online more than 4 hours today, yet I never found any interesting article like yours.
    It is pretty worth enough for me. In my opinion, if
    all webmasters and bloggers made good content as you did, the internet will be much more useful than ever before.

  2. Hello! I just wanted to ask if you ever have any problems
    with hackers? My last blog (wordpress) was hacked and I
    ended up losing several weeks of hard work due to no backup.
    Do you have any methods to prevent hackers?

  3. We are a group of volunteers and opening a new scheme in our community.

    Your web site provided us with helpful information to work on. You have
    done a formidable process and our entire neighborhood might be grateful to you.

  4. Thank you for every other wonderful post. Where else could anyone get that type
    of info in such an ideal approach of writing? I’ve a presentation next week, and I’m at the search for such
    information.

  5. Nice post. I learn something new and challenging on blogs
    I stumbleupon on a daily basis. It’s always useful to read through articles
    from other writers and practice a little something from their web sites.

  6. My brother recommended I might like this website. He was totally
    right. This post actually made my day. You cann’t imagine simply how much time I had spent for this info!
    Thanks!

  7. I like the valuable information you supply in your articles.
    I’ll bookmark your blog and test again here frequently.
    I’m relatively certain I will be told plenty of new stuff proper right
    here! Best of luck for the following!

  8. Attractive element of content. I just stumbled upon your web site and in accession capital
    to claim that I get actually loved account your blog posts.
    Anyway I’ll be subscribing for your augment or even I
    fulfillment you get right of entry to persistently fast.

  9. Hey there! This post could not be written any better!
    Reading this post reminds me of my good old room mate!
    He always kept talking about this. I will forward this page to him.
    Pretty sure he will have a good read. Thanks for sharing!

  10. Hello just wanted to give you a quick heads up. The text in your article seem
    to be running off the screen in Opera. I’m not sure if this is a format issue or something to do with
    browser compatibility but I thought I’d post to let you know.
    The layout look great though! Hope you get the issue resolved soon. Kudos

  11. It’s a pity you don’t have a donate button! I’d most certainly donate to this outstanding blog!
    I guess for now i’ll settle for book-marking and adding your RSS
    feed to my Google account. I look forward to brand new updates and will talk
    about this website with my Facebook group. Chat soon!

  12. Hey, I think your blog might be having browser compatibility issues.
    When I look at your blog site in Safari, it looks
    fine but when opening in Internet Explorer, it has some overlapping.
    I just wanted to give you a quick heads up! Other then that, wonderful blog!

  13. Hello there! I know this is kinda off topic however I’d figured I’d ask. Would you be interested in trading links or maybe guest writing a blog article or vice-versa? My site discusses a lot of the same topics as yours and I believe we could greatly benefit from each other. If you are interested feel free to shoot me an email. I look forward to hearing from you! Fantastic blog by the way!

Leave a Reply

Your email address will not be published. Required fields are marked *