BZOJ 3262

不稳定的传送门

感觉整个人都CDQ了…尼玛这么多维闹哪样啊

对第一维进行排序然后扔掉,问题变成了依次向一个$k\times k$的矩阵中插入$n$个点,每次插入时需统计横纵坐标均$\leq$该点坐标的点数,这样一个三维无序的问题变成了一个二维有序的问题

然后对于这个问题,直接CDQ分治,每次$solve(l,r)$中统计$[l,mid]$对$[mid+1,r]$造成的影响,然后继续递归处理$[l,mid],[mid+1,r]$

因为题意是三个恶心的$\leq$,所以要把一样的花合在一起存…


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
125
126
127
128
129
130
131
132
133
program bzoj_3262;
type flower=record s,c,m,id,ans,cnt:longint; end;
var n,i,tot,m:longint;
f,swp:array[1..100000]of flower;
bit,cnt:array[0..200000]of longint;
procedure swap(var a,b:flower);
var p:flower;
begin
p:=a;
a:=b;
b:=p;
end;
function cmp(a,b:flower;flag:boolean):boolean;
begin
if flag and(a.s<>b.s) then exit(a.s<b.s);
if a.c<>b.c then exit(a.c<b.c);
exit(a.m<b.m);
end;
function diff(a,b:flower):boolean;
begin
exit((a.s<>b.s)or(a.c<>b.c)or(a.m<>b.m));
end;
procedure qsort(l,r:longint;flag:boolean);
var i,j:longint;
mid:flower;
begin
i:=l;
j:=r;
mid:=f[(l+r)>>1];
repeat
while cmp(f[i],mid,flag) do inc(i);
while cmp(mid,f[j],flag) do dec(j);
if i<=j then
begin
swap(f[i],f[j]);
inc(i);
dec(j);
end;
until i>j;
if l<j then qsort(l,j,flag);
if i<r then qsort(i,r,flag);
end;
procedure modify(p,d:longint);
begin
while p<=m do
begin
inc(bit[p],d);
inc(p,p and -p);
end;
end;
function query(p:longint):longint;
begin
query:=0;
while p>0 do
begin
inc(query,bit[p]);
dec(p,p and -p);
end;
end;
procedure solve(l,r:longint);
var l1,l2,mid,i,j:longint;
begin
if l>=r then
begin
inc(f[l].ans,f[l].cnt-1);
exit;
end;
mid:=(l+r)>>1;
l1:=l-1;
l2:=mid;
for i:=l to r do if f[i].id<=mid then
begin
inc(l1);
swp[l1]:=f[i];
end else
begin
inc(l2);
swp[l2]:=f[i];
end;
for i:=l to r do f[i]:=swp[i];
j:=l;
for i:=mid+1 to r do
begin
while (j<=mid)and(f[j].c<=f[i].c) do
begin
modify(f[j].m,f[j].cnt);
inc(j);
end;
inc(f[i].ans,query(f[i].m));
end;
for i:=l to j-1 do modify(f[i].m,-f[i].cnt);
solve(l,mid);
solve(mid+1,r);
l1:=l;
l2:=mid+1;
for i:=l to r do
if (l1<=mid)and(cmp(f[l1],f[l2],false))or(l2>r) then
begin
swp[i]:=f[l1];
inc(l1);
end else
begin
swp[i]:=f[l2];
inc(l2);
end;
for i:=l to r do f[i]:=swp[i];
end;
begin
readln(n,m);
for i:=1 to n do with f[i] do readln(s,c,m);
qsort(1,n,true);
tot:=0;
for i:=1 to n do
if (i=1)or(diff(f[tot],f[i])) then
begin
inc(tot);
f[tot]:=f[i];
f[tot].cnt:=1;
end else inc(f[tot].cnt);
for i:=1 to tot do f[i].id:=i;
qsort(1,tot,false);
solve(1,tot);
for i:=1 to tot do inc(cnt[f[i].ans],f[i].cnt);
for i:=0 to n-1 do writeln(cnt[i]);
end.