题目传送门：http://pan.baidu.com/s/1kVjNeeV
离线版题目：http://paste.ubuntu.com/18236489/
数据传送门：http://pan.baidu.com/s/1kUR6kTL
哎呀，绍兴一中的NOIP模拟题，第一眼拿到都一脸懵逼QAQ
想了一会儿发现，不就是总方案数减掉一个三位偏序吗？这个我会！
于是开开心心写完BIT+动态建点的线段树。然后小数据对拍，欸！居然没错 (～￣▽￣)→))*￣▽￣*)o
然后一跑大数据，哎呀，空间简直炸的飞起！ 然后再接下来的一个半小时里一直想办法压空间。
什么unsign short配合char之类的都用上了，然而还是不行QAQ，再加上时间复杂度也不一定过得去，于是弃疗
测完程序，发现CDQ+归并就可以卡过QAQ，然而不会CDQ，于是下午学了一学，还是比较好学的。
然而这还不是高潮！高潮在：这货可以降到一维，然后O（nlogn）轻松过 QAQ
对于任意一个符合条件的（x,y）只会有一种情况(在把A,B,C看成一样的情况下)：
A[x] < A[y] B[x] > B[y] C[x] > C[y]
然后不难发现，如果我们把[A,B]&[A,C]拿出来统计一次逆序对的话，这货相当于每一个符合要求的(x,y)被算了2次
于是，跑三遍一维逆序对就好了QAQ 这个能算简单的容斥吗？
BIT + 线段树：http://paste.ubuntu.com/18236197/
CDQ分治：http://paste.ubuntu.com/18236240/
逆序对虐场代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;
const int MAXN = 200000+9;
int n,a[MAXN],b[MAXN],c[MAXN],ord[MAXN];
LL vout;
namespace Fenwick_Tree{
#define BIT Fenwick_Tree
#define low(x) (x&(-x))
int arr[MAXN],sum;
inline void init(){
memset(arr,0,sizeof(arr));
sum = 0;}
inline void modify(int pos){
for (int i=pos;i<=n;i+=low(i))
arr[i] += 1; sum++;
}
inline int query(int pos){
int ret = 0;
for (int i=pos;i;i-=low(i))
ret += arr[i];
return sum-ret;
}
};
inline void itv(int *A, int *B){
BIT::init();
for (int i=1;i<=n;i++) ord[A[i]] = i;
for (int j=1,i=ord[j];j<=n;i=ord[++j])
vout += BIT::query(B[i]),
BIT::modify(B[i]);
}
int main(){
freopen("contest.in","r",stdin);
freopen("contest.out","w",stdout);
scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%d%d%d",&a[i],&b[i],&c[i]);
itv(a,b); itv(b,c); itv(a,c);
printf("%lld\n",vout/2LL);
return 0;
}
另外，这题做的时候，发现对于小的结构体，貌似直接排序比排指针还要快一点QAQ
可能是因为后期指针寻址也要花时间吧！所以以后CDQ就直接结构体写了吧！ 有图有真相：
Greetings! I’ve been reading your weblog for a while now and finally got the bravery to go ahead and give you a shout out from Houston Tx!
Just wanted to tell you keep up the great work!
wonderful issues altogether, you just gained a logo new reader.
What could you recommend in regards to your submit that you simply made some days in the past?
Any positive?
I have read several just right stuff here. Definitely worth bookmarking for revisiting.
I surprise how so much attempt you put to make one of these wonderful
informative web site.
Thank you for the good writeup. It in fact was
a amusement account it. Look advanced to far added agreeable
from you! By the way, how could we communicate?
As the admin of this web page is working, no question very shortly it will be renowned, due to its quality contents.
Thanks to my father who informed me concerning this webpage, this website is genuinely amazing.
Hi, I do think this is a great site. I stumbledupon it
😉 I am going to revisit yet again since I bookmarked
it. Money and freedom is the greatest way to
change, may you be rich and continue to help others.
Thanks for another informative website. The place else could
I get that kind of info written in such an ideal manner? I’ve
a venture that I’m simply now working on, and I’ve been at the glance out for
such info.
WOW just what I was searching for. Came here by searching for plenty of fish dating site
I always emailed this weblog post page to all my friends, for the
reason that if like to read it next my friends will too.
I pay a quick visit every day a few web pages and blogs to read posts,
except this blog presents feature based articles.
Please let me know if you’re looking for a article writer for your blog.
You have some really good posts and I feel I would be a good asset.
If you ever want to take some of the load off, I’d really like
to write some material for your blog in exchange for
a link back to mine. Please blast me an email if interested.
Thanks!
Ahaa, its fastidious dialogue regarding this piece of writing
at this place at this web site, I have read all that, so now
me also commenting here.
Hello! This is kind of off topic but I need some guidance from an established
blog. Is it hard to set up your own blog? I’m not very techincal but I can figure things out pretty quick.
I’m thinking about creating my own but I’m not sure where to begin. Do you have any points or
suggestions? Thanks
hi!,I love your writing very much! share we keep in touch more about your post
on AOL? I need a specialist on this house to solve my problem.
May be that’s you! Having a look ahead to look you.
Thanks on your marvelous posting! I truly enjoyed reading it, you will be a
great author.I will ensure that I bookmark your blog and will come back
very soon. I want to encourage you to definitely continue your
great writing, have a nice holiday weekend!
Wonderful beat ! I would like to apprentice while you amend your web site, how could i subscribe for a blog web site?
The account helped me a acceptable deal. I
had been a little bit acquainted of this your broadcast offered bright clear concept
I just couldn’t depart your web site before suggesting that I really loved
the usual info a person supply on your guests? Is gonna be back often to check
up on new posts
Hi there! I could have sworn I’ve been to this blog before
but after reading through some of the post I realized it’s new to me.
Anyhow, I’m definitely glad I found it and I’ll
be bookmarking and checking back frequently! natalielise pof
Hello There. I found your blog using msn. This is a really
well written article. I’ll be sure to bookmark it and
return to read more of your useful information. Thanks for the post.
I will certainly comeback.
My brother recommended I might like this blog.
He was totally right. This post truly made my day.
You cann’t imagine just how much time I had spent for this info!
Thanks!
I think this is among the most important info for me.
And i’m glad reading your article. But want to remark on few general things,
The web site style is perfect, the articles is really excellent : D.
Good job, cheers natalielise pof
When someone writes an piece of writing he/she retains
the plan of a user in his/her mind that how a user can be aware of it.
So that’s why this article is perfect. Thanks!
Wonderful beat ! I would like to apprentice while you amend
your web site, how could i subscribe for a blog site?
The account helped me a acceptable deal. I had been tiny bit acquainted of this your broadcast offered
bright clear idea
I know this website gives quality depending
posts and additional information, is there any other site which presents such things
in quality?
I’ve been surfing on-line more than three hours lately, but I never discovered any interesting article like yours.
It is lovely worth enough for me. In my opinion,
if all webmasters and bloggers made good content material
as you did, the web will be much more useful than ever before.
plenty of fish natalielise
Excellent pieces. Keep writing such kind of info on your page.
Im really impressed by it.
Hello there, You’ve done a fantastic job. I’ll certainly
digg it and in my view recommend to my friends.
I am confident they will be benefited from this website.
Magnificent beat ! I wish to apprentice while you amend your site, how can i subscribe for a
blog web site? The account helped me a acceptable deal.
I had been a little bit acquainted of this your broadcast offered bright clear idea
We stumbled over here different page and thought I might as well
check things out. I like what I see so now
i’m following you. Look forward to checking out your web page for a second
time.
Wow, that’s what I was seeking for, what a material!
existing here at this webpage, thanks admin of this site.
Hey very nice web site!! Man .. Beautiful .. Amazing ..
I’ll bookmark your web site and take the feeds additionally?
I’m happy to find so many helpful information right here in the publish, we’d like develop more strategies in this regard, thanks for sharing.
. . . . .
Wonderful, what a blog it is! This web site gives helpful information to us, keep it up.
There’s definately a lot to learn about this topic.
I love all of the points you’ve made.
My partner and I stumbled over here by a different web page and thought I should check things out.
I like what I see so now i’m following you. Look forward to checking out your web page yet again.
Thanks a lot for sharing this with all folks you really recognize what you’re talking about!
Bookmarked. Please additionally talk over with my website =).
We could have a link alternate contract among us
I read this article completely about the difference of hottest and earlier technologies, it’s amazing article.
I am regular visitor, how are you everybody?
This paragraph posted at this web site is in fact good.
Helpful info. Fortunate me I found your site accidentally, and I am
stunned why this coincidence did not happened in advance!
I bookmarked it.
Hi there colleagues, its fantastic post about cultureand completely defined,
keep it up all the time.
Good information. Lucky me I recently found your website by chance (stumbleupon).
I have book marked it for later!
If some one wants expert view concerning blogging then i advise
him/her to go to see this webpage, Keep up the pleasant work.
Hello! Do you know if they make any plugins to help with SEO?
I’m trying to get my blog to rank for some targeted keywords but I’m not seeing very good results.
If you know of any please share. Thank you!
It’s an awesome post in favor of all the web users; they will get advantage
from it I am sure.
Thanks for the auspicious writeup. It if truth be told was once a leisure account it.
Look complex to more introduced agreeable from
you! By the way, how could we communicate?
Asking questions are genuinely pleasant thing if you are not understanding something totally, but this
article provides nice understanding even.
Wonderful goods from you, man. I have understand your stuff previous to and you’re just too excellent.
I really like what you’ve acquired here, certainly like
what you’re saying and the way in which you say it.
You make it entertaining and you still take care of to keep it wise.
I can not wait to read much more from you. This is actually a tremendous web site.
Hello! I know this is kinda off topic but I’d figured I’d ask.
Would you be interested in trading links or maybe guest authoring a blog post
or vice-versa? My blog addresses a lot of the same subjects as yours
and I think we could greatly benefit from each other.
If you happen to be interested feel free to send me an email.
I look forward to hearing from you! Wonderful blog by the way!
you are really a good webmaster. The web site loading pace is incredible.
It sort of feels that you are doing any distinctive trick.
Furthermore, The contents are masterpiece. you’ve
done a wonderful task in this matter!
I’m impressed, I have to admit. Rarely do I come across a blog that’s both educative and
amusing, and let me tell you, you have hit the nail on the head.
The problem is something that too few men and women are speaking
intelligently about. I am very happy that I came across this in my search for something regarding this.
Write more, thats all I have to say. Literally, it seems as though you relied on the video to make your point.
You clearly know what youre talking about, why throw away your intelligence on just posting videos
to your weblog when you could be giving us something
informative to read?
When I originally commented I clicked the “Notify me when new comments are added”
checkbox and now each time a comment is added I get
four e-mails with the same comment. Is there any way you can remove people from that service?
Cheers!
I think that what you said made a bunch of sense. However,
what about this? what if you added a little content?
I mean, I don’t want to tell you how to run your blog, however
what if you added something that makes people want more? I mean 【NOI六连测】[D1T1] 比赛 – Qizy's Database is a little vanilla.
You should peek at Yahoo’s home page and watch how they write news headlines
to get viewers interested. You might try adding a video or a related pic or
two to grab readers excited about what you’ve written. In my opinion, it could make
your blog a little bit more interesting.
Do you have a spam problem on this website; I also am a blogger,
and I was wondering your situation; we have developed some nice procedures and we
are looking to trade techniques with others, please shoot me an e-mail if interested.
This blog was… how do I say it? Relevant!! Finally I have found something which helped me.
Cheers!
Terrific work! That is the type of information that should be shared around the web.
Disgrace on Google for not positioning this submit upper!
Come on over and seek advice from my site . Thanks =)
Hi there friends, its fantastic article regarding tutoringand completely defined,
keep it up all the time.
Hi, Neat post. There is a problem along with your
web site in web explorer, might check this? IE nonetheless is the market chief and a
good portion of people will omit your fantastic writing due to this problem.
I think the admin of this web page is in fact working
hard in favor of his web page, for the reason that here every information is quality based material.
Great delivery. Solid arguments. Keep up the good spirit.
Appreciate the recommendation. Let me try it out.
We are a group of volunteers and starting a new scheme in our community.
Your web site provided us with valuable information to work on. You’ve done an impressive job and our entire
community will be thankful to you.
I’ve been surfing online more than three hours today,
yet I never found any interesting article like yours. It’s pretty worth enough for me.
In my opinion, if all web owners and bloggers made good content as you did,
the web will be a lot more useful than ever before.
It’s remarkable to pay a visit this web site and reading the views of all friends regarding this article, while I am also eager of getting know-how.
Hey there just wanted to give you a quick heads up.
The words in your content seem to be running
off the screen in Firefox. I’m not sure if this is a format issue or something to
do with internet browser compatibility but I
figured I’d post to let you know. The design look great though!
Hope you get the problem solved soon. Many thanks
naturally like your web-site but you need to take a look at the spelling on quite a few of your posts. Several of them are rife with spelling issues and I find it very troublesome to inform the reality however I¦ll surely come back again.
Hi! I’m at work browsing your blog from my new apple
iphone! Just wanted to say I love reading your blog and look forward to all your posts!
Keep up the superb work!
I appreciate, result in I found exactly what I used to be looking for.
You have ended my four day long hunt! God Bless you
man. Have a great day. Bye
I will immediately take hold of your rss feed as I can’t in finding your email
subscription hyperlink or newsletter service. Do you have any?
Please let me recognize so that I may just subscribe. Thanks.
Howdy are using WordPress for your site platform?
I’m new to the blog world but I’m trying to get started and create my own. Do you
need any html coding expertise to make your
own blog? Any help would be really appreciated!
Hello There. I discovered your blog the use of msn. This
is a very smartly written article. I will be sure to bookmark it and return to learn more
of your helpful info. Thank you for the post. I’ll certainly comeback.
We stumbled over here from a different web address and thought I might as well check things
out. I like what I see so now i’m following you. Look forward to looking into your web page again.
Appreciation to my father who informed me about this webpage, this web site is truly awesome.
Fantastic goods from you, man. I’ve take into accout your stuff
prior to and you’re just too excellent. I actually like what
you’ve bought right here, really like what you are saying
and the way through which you are saying it.
You’re making it entertaining and you continue to take care of to stay it wise.
I can not wait to learn much more from you. That is really
a great website.
That is a very good tip especially to those fresh to the blogosphere.
Simple but very precise info… Many thanks for
sharing this one. A must read article!
Write more, thats all I have to say. Literally, it seems as though
you relied on the video to make your point. You clearly know what youre talking about, why waste your intelligence on just posting videos to your weblog when you could be giving us something enlightening to read?
Thanks very nice blog!
I have read a few good stuff here. Certainly worth bookmarking
for revisiting. I wonder how so much effort you put to create the sort of wonderful informative web site.
Great site. Plenty of helpful information here. I’m sending it to a few buddies ans additionally sharing in delicious.
And of course, thanks to your sweat!
I’m not sure where you are getting your information, but good topic. I needs to spend some time learning more or understanding more. Thanks for great info I was looking for this information for my mission.