BZOJ

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.