思路

四维偏序

\(CDQ\)套\(CDQ\)，第一维默认有序。第二维用第一个\(CDQ\)变成有序的。并且对每个点标记上第一维属于左边还是右边。第二个\(CDQ\)处理第三维，注意两个\(CDQ\)不能用同一个数组，否则第二维就变成无序的了。最后一维用个树状数组统计答案。

代码

/*

* @Author: wxyww

* @Date:   2019-02-16 16:39:12

* @Last Modified time: 2019-02-17 08:18:59

*/

#include<cstdio>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<queue>

#include<vector>

#include<ctime>

using namespace std;

typedef long long ll;

const int N = 50010;

ll read() {

	ll x=0,f=1;char c=getchar();

	while(c<'0'||c>'9') {

		if(c=='-') f=-1;

		c=getchar();

	}

	while(c>='0'&&c<='9') {

		x=x*10+c-'0';

		c=getchar();

	}

	return x*f;

}

int n;

struct node {

	int a,b,c,d,opt;

}a[N],tmp[N],tt[N];

bool cmp(const node &x,const node &y) {

	return x.a <= y.a;

}

int tree[N];

int mx;

void update(int pos,int c) {

	while(pos <= mx) {

		tree[pos] += c;

		pos += pos & -pos;

	}

}

int query(int pos) {

	int ret = 0;

	while(pos) {

		ret += tree[pos];

		pos -= pos & -pos;

	}

	return ret;

}

vector<int>v;

int ans;

void cdq2(int l,int r) {

	if(r <= l) return;

	int mid = (l + r) >> 1;

	cdq2(l,mid);

	cdq2(mid + 1,r);

	int L = l,R = mid + 1,now = l;

	while(L <= mid && R <= r) {

		if(tmp[L].c < tmp[R].c) {

			if(tmp[L].opt == 1) update(tmp[L].d,1),v.push_back(tmp[L].d);

			tt[now++] = tmp[L++];

		}

		else {

			if(tmp[R].opt == 2)	ans += query(tmp[R].d - 1);

			tt[now++] = tmp[R++];

		}

	}

	while(L <= mid) tt[now++] = tmp[L++];

	while(R <= r) {

		if(tmp[R].opt == 2) ans += query(tmp[R].d - 1);

		tt[now++] = tmp[R++];

	}

	for(int i = l;i <= r;++i) tmp[i] = tt[i];

	int k = v.size();

	for(int i = 0;i < k;++i) update(v[i],-1);

	v.clear();

}

void cdq(int l,int r) {

	if(r <= l) return;

	int mid = (l + r) >> 1;

	cdq(l,mid);

	cdq(mid + 1,r);

	int L = l,R = mid + 1,now = l;

	while(L <= mid && R <= r) {

		if(a[L].b < a[R].b) tmp[now] = a[L++],tmp[now++].opt = 1;

		else tmp[now] = a[R++],tmp[now++].opt = 2;

	}

	while(L <= mid) tmp[now] = a[L++],tmp[now++].opt = 1;

	while(R <= r) tmp[now] = a[R++],tmp[now++].opt = 2;

	for(int i = l;i <= r;++i) a[i] = tmp[i];

	cdq2(l,r);

}

int main() {

	n = read();

	for(int i = 1;i <= n;++i) mx = max(mx,(a[i].a = i));

	for(int i = 1;i <= n;++i) mx = max(mx,(a[i].b = read()));

	for(int i = 1;i <= n;++i) mx = max(mx,(a[i].c = read()));

	for(int i = 1;i <= n;++i) mx = max(mx,(a[i].d = read()));

	cdq(1,n);

	cout<<ans;

	return 0;

}

巴特西

cogs2479 偏序(CDQ套CDQ)

思路

代码

最新文章

热门文章