相关链接
题目传送门: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; }
楼下是疯子。哈哈
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.
This is a topic that is near to my heart…
Many thanks! Where are your contact details though?
whoah this blog is great i really like studying your articles.
Stay up the great work! You already know, lots of people are searching around for this information, you can aid
them greatly.
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?
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.
Awesome article.
Hello There. I found your blog using msn. This is an extremely well written article.
I’ll be sure to bookmark it and return to read more
of your useful info. Thanks for the post. I will definitely return.
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.
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.
If you wish for to improve your know-how only keep visiting
this site and be updated with the most up-to-date news update posted
here.
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!
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!
Great wordpress blog here.. It’s hard to find quality writing like yours these days. I really appreciate people like you! take care
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.
I’m curious to find out what blog system you have been working with?
I’m experiencing some small security issues with my latest website and I’d like to find something
more safeguarded. Do you have any recommendations?
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!
Thanks for finally writing about >【Codeforces 749E】Inversions After
Shuffle – Qizy’s Database <Loved it!
I really like what you guys are up too. This type of clever work
and reporting! Keep up the superb works guys I’ve included you guys
to my personal blogroll.
Awesome article.
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
If some one needs to be updated with most up-to-date technologies then he must be go to see
this web page and be up to date daily.
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!
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!
Genuinely when someone doesn’t know after that its up to
other visitors that they will help, so here it occurs.
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!