(三维偏序)陌上花开

Posted on |

Problem

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

定义$f[i]$为满足$aj < 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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#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\n", ans[i]);
	return 0;
}