(三维偏序)陌上花开

Problem

有(n)个元素，每个元素有三个属性：(a_i),(b_i),(c_i)

定义(f[i])为满足(a_j < a_i) 且 (b_j < b_i) 且 (c_j < c_ i)的(j)的个数

(ans[i] = sum_{j = 1}^{j leq n} f[j] = i)

求所有的(ans[i]);

陌上花开，心忧梓桑。

Solution

(CDQ)分治模板题

首先以(a)为关键字排序，省略一维

再以(b)为关键字用类似于归并排序求逆序对的方法进行归并

最后用树状数组统计(c)这一维

简单来说就是归并排序套树状数组。

有点像点分治？

调了不知道多久，最后发现树状数组范围打错了(原地爆炸.jpg)

Code

#include <bits/stdc++.h>

using namespace std;

#define DEBUG(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define fst first
#define snd second

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

inline int read(){
	int res = 0, fl = 1;
	char r = getchar();
	for (; !isdigit(r); r = getchar()) if(r == '-') fl = -1;
	for (; isdigit(r); r = getchar()) res = (res << 3) + (res << 1) + r - 48;
	return res * fl;
}
typedef long long LL;
typedef pair<int, int> pii;
const int Maxn = 2e5 + 10;
vector <pii> G[Maxn];
map <pii, int> Map;
struct node{
	int fst, snd, val, id;
	bool operator < (const node &T) const{
		if(fst == T.fst) return snd < T.snd;
		return fst < T.fst;
	}
}P[Maxn], tmp[Maxn];
int cnt, f[Maxn], val[Maxn], top, num, ans[Maxn], K, v[Maxn];
pii del[Maxn];
bool ok;
namespace BIT{
	inline int lowbit(int x) {return x & -x;}
	int tre[Maxn];
	inline void Modify(int pos, int v){
		for (; pos <= K; pos += lowbit(pos)) tre[pos] += v;
	}
	inline int Query(int pos){
		int sum = 0; 
		for (; pos >= 1; pos -= lowbit(pos)) {
			sum += tre[pos]; 
		}
		return sum;
	}
}
void CDQ_div(int L, int R){
	if(L == R) return;
	int mid = L + R >> 1;
	num = L - 1;
	CDQ_div(L, mid), CDQ_div(mid + 1, R);
	int l = L, r = mid + 1;
	while(l <= mid && r <= R){
		if(P[l].fst <= P[r].fst){ 
			BIT::Modify(P[l].snd, P[l].val);
			del[++top] = mp(P[l].snd, P[l].val);
			l++;
		}
		else {
			f[P[r].id] += BIT::Query(P[r].snd);
			r++;
		}
	}
	while(r <= R) {
		f[P[r].id] += BIT::Query(P[r].snd);
		r++;
	}
	sort(P + L, P + R + 1);
	while(top){
		BIT::Modify(del[top].fst, -del[top].snd);
		top--;
	}
}
int id[Maxn];
int main()
{
#ifndef ONLINE_JUDGE
	freopen("a.in", "r", stdin);
	freopen("a.out", "w", stdout);
#endif
	int n = read(), k = read();
	K = k;
	for (int i = 1; i <= n; ++i){
		int a = read(), b = read(), c = read();
		G[a].push_back(mp(b,c));
	}
	for (int i = 1; i <= k; ++i) {
		sort(G[i].begin(), G[i].end());
		for (pii j : G[i]) Map[j]++;
		int sum = unique(G[i].begin(), G[i].end()) - G[i].begin();
		for (int j = 0; j < sum ; ++j) {
			pii nxt = G[i][j];
			P[++cnt].fst = nxt.fst, P[cnt].snd = nxt.snd;
			P[cnt].val = Map[nxt], P[cnt].id = cnt;
			v[cnt] = P[cnt].val;
		}
		Map.clear();
	}
	CDQ_div(1, cnt);
	for (int i = 1; i <= cnt; ++i) ans[f[P[i].id] + P[i].val - 1] += P[i].val;
	for (int i = 0; i < n; ++i) printf("%d
", ans[i]);
	return 0;
}