【NOI六连测】[D1T1] 比赛

题目传送门: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就直接结构体写了吧! 有图有真相:
struct_iterator