萌新第一次用树套树写三维偏序，来谈一谈心得。
首先根据基本套路，我们通过排序忽略掉第一维对答案的影响。
但是注意要同时按照三维（三关键字）排序。
然后就是用树状数组维护第二维，再套 FHQ Treap 维护第三维。
一交，woc 爆 0？
找了个数据发现是没有考虑重复情况。
于是我把重复的放到一起，乱搞一下就好了。
代码： 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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
using namespace std;
const int N = 1e5;
const int K = 2e5;
int n,k;
struct note
{
int a,b,c,cnt;
inline bool operator<(const note &o) const
{
if(a ^ o.a)
return a < o.a;
if(b ^ o.b)
return b < o.b;
return c < o.c;
}
inline bool operator==(const note &o) const
{
return a == o.a && b == o.b && c == o.c;
}
} a[N + 5],b[N + 5];
struct node
{
int val,rnd,sz;
node *lson,*rson;
} *rt[K + 5];
inline node *new_node(int v)
{
node *ret = new node();
ret->val = v;
ret->rnd = rand();
ret->sz = 1;
return ret;
}
inline void up(node *p)
{
p->sz = 1;
if(ls(p))
p->sz += ls(p)->sz;
if(rs(p))
p->sz += rs(p)->sz;
}
node *merge(node *x,node *y)
{
if(!x)
return y;
if(!y)
return x;
if(x->rnd < y->rnd)
{
rs(x) = merge(rs(x),y);
up(x);
return x;
}
else
{
ls(y) = merge(x,ls(y));
up(y);
return y;
}
}
void split(node *p,int v,node *&x,node *&y)
{
if(!p)
{
x = y = NULL;
return ;
}
if(p->val <= v)
x = p,split(rs(p),v,rs(p),y);
else
y = p,split(ls(p),v,x,ls(p));
up(p);
}
void update(int x,int y)
{
node *a,*b;
for(;x <= k;x += lowbit(x))
{
split(rt[x],y,a,b);
rt[x] = merge(merge(a,new_node(y)),b);
}
}
int query(int x,int y)
{
int ret = 0;
node *a,*b;
for(;x;x -= lowbit(x))
{
split(rt[x],y,a,b);
if(a)
ret += a->sz;
rt[x] = merge(a,b);
}
return ret;
}
int ans[N + 5];
int main()
{
srand(19260817);
scanf("%d%d",&n,&k);
for(register int i = 1;i <= n;++i)
scanf("%d%d%d",&b[i].a,&b[i].b,&b[i].c),b[i].cnt = 1;
sort(b + 1,b + n + 1);
a[1] = b[1];
for(register int i = 2,j = 1;i <= n;++i)
if(b[i] == b[i - 1])
++a[j].cnt;
else
a[++j] = b[i];
for(register int i = 1;i <= n;++i)
{
ans[query(a[i].b,a[i].c) + a[i].cnt - 1] += a[i].cnt;
for(register int j = 1;j <= a[i].cnt;++j)
update(a[i].b,a[i].c);
}
for(register int i = 0;i < n;++i)
printf("%d\n",ans[i]);
}