2019.2.16

长沙集训 $ Day 6 $

今天没有模拟赛，而是介绍了一种神奇的算法，现在让我们一起了解一下 $ CDQ $ 分治的魅力。

三维偏序问题：

共有 $ n $ 个元素，对于第 $ i $ 个元素，给出三个量：$ a_i \ \ , \ \ b_i \ \ ,\ \ c_i $ ,询问$ a_j<a_i , b_j<b_i , c_j<c_i $ 的元素有多少个。

如果 $ n $ 很小，我们可以用三维前缀和解决这个问题，但当 $ n=10000 $ 或者更大时，显然需要二维树形结构来维护，但树形结构消耗空间大，编程难度高，且处理时常数复杂度高。这时，我们便可以用 $ CDQ $ 分治来解决问题。

先从二位偏序看起:

要解决二维偏序，我们可以先使用快排将第一维处理为有序排列。之后再利用树状数组或分治在第二维上统计答案。（例如逆序对）

现在问题变成了三维，我们依然可以沿用解决二维偏序问题的思路。依然用快排处理第一维（例如将其从小到大排列），但这时不能直接将第二维再次排序，否则会打乱第一维的顺序。为解决这个问题，我们可以用分治将数列分成左右两份。注意到左边的 $ a_i $ 一定小于右边的 $ a_j $ ,此时我们将左右两边的 $ b $ 分别排成有序数列，虽然 $ a $ 的顺序会被打乱，但左边 $ a $ 一定是比右边 $ a $ 小。此时，我们便可以统计左边元素对右边元素的贡献。通过层层分治，可以求出所有贡献。

如何排序

对第二维元素可以用快排排序，这样的时间复杂度：

快排 $ O(n \log n) $
分治 $ O(\log n) $
处理答案 $ O(n) $

总时间复杂度接近 $ O(n \log^{2} n) $

这个速度已经可以解决大部分问题，但其实还有更快的处理方式。因为分治的过程类似归并排序，所以我们可以在处理答案时对b进行归并排序，这样的时间复杂度：

分治 $O(\log n) $
处理答案+排序 $ O(n) $

总时间复杂度接近 $ O(n \log n) $

处理答案

对答案的处理一般是使用树状数组进行统计，但其实我们可以再次利用 $ CDQ $ 分治的方法，继续对第三维进行分治，即在 $ b $ 排序后，再将区间分为两份，对 $ c $ 进行排序并统计答案。这种 $ CDQ $ 嵌套还可以继续进行，以解决四维、五维偏序问题。

程序（ $ CDQ $ 套 $ CDQ $ ）

program project1;
type tp=record
  a,b,c,tot,tf,ans:longint;
  tfp:boolean;
end;

var
   f,a,b:array[0..100005]of tp;
   ans:array[0..100005]of longint;
   n,k:longint;

function max(a,b:longint):longint;
begin
  if a>b then exit(a) else exit(b);
end;

procedure re;
var i:longint;
begin
  for i:=1 to n do
    read(f[i].a,f[i].b,f[i].c);
end;

procedure qsort(l,r:longint);
var i,j:longint;
    t,mid:tp;
begin
  i:=l;
  j:=r;
  mid:=f[(i+j) div 2];
  repeat
    while (f[i].a<mid.a) or ((f[i].a=mid.a) and (f[i].b<mid.b)) or ((f[i].a=mid.a) and (f[i].b=mid.b) and (f[i].c<mid.c)) do inc(i);
    while (f[j].a>mid.a) or ((f[j].a=mid.a) and (f[j].b>mid.b)) or ((f[j].a=mid.a) and (f[j].b=mid.b) and (f[j].c>mid.c)) do dec(j);
    if i<=j then begin
      t:=f[i];
      f[i]:=f[j];
      f[j]:=t;
      inc(i);
      dec(j);
    end;
  until i>j;
  if i<r then qsort(i,r);
  if l<j then qsort(l,j);
end;

procedure cdq_c(l,r:longint);
var i,j,mid,t,sum,ii:longint;
begin
  if l=r then begin
    if f[l].tfp=false then begin
      inc(ans[f[l].ans],f[l].tot-1);
      f[l].tfp:=true;
    end;  
    exit;
  end;
  mid:=(l+r) shr 1;
  cdq_c(l,mid);
  cdq_c(mid+1,r);
  i:=l;
  j:=mid+1;
  t:=l-1;
  sum:=0;
  while t<=r-1 do begin
    inc(t);          
    if ((a[i].c<=a[j].c) or (j>r)) and (i<=mid) then begin
      b[t]:=a[i];
      inc(sum,b[t].tf*b[t].tot);
      inc(i);
    end
      else begin
        b[t]:=a[j];        
        inc(j);
      end;
  end;
  for i:=l to r do a[i]:=b[i];
end;

procedure cdq_b(l,r:longint);
var i,mid,j,t:longint;
begin
  if l=r then begin
    cdq_c(l,r);
    exit;
  end;
  mid:=(l+r) shr 1;
  cdq_b(l,mid);
  cdq_b(mid+1,r);
  i:=l;
  j:=mid+1;
  t:=l-1;   
  while t<=r-1 do begin
    inc(t);
    if ((f[i].b<=f[j].b) or (j>r)) and (i<=mid) then begin
      a[t]:=f[i];
      a[t].tf:=1;
      inc(i);
    end
      else begin
        a[t]:=f[j];
        a[t].tf:=0;
        inc(j);
      end;
  end;
  for i:=l to r do f[i]:=a[i];
  cdq_c(l,r);
end;

procedure main;
var i,j:longint;
    sum:array[0..100005]of longint;
begin
  j:=1;
  f[1].tot:=1;
  for i:=2 to n do
    if ((f[i].a=f[j].a) and (f[i].b=f[j].b) and (f[i].c=f[j].c)) then inc(f[j].tot)
      else begin
        inc(j);
        f[j]:=f[i];
        f[j].tot:=1;
      end;
  for i:=1 to j do f[i].ans:=i;
  fillchar(sum,sizeof(sum),0);
  fillchar(ans,sizeof(ans),0);
  cdq_b(1,j);
  for i:=1 to j do inc(sum[ans[f[i].ans]],f[i].tot);
  for i:=0 to n-1 do writeln(sum[i]);
end;

begin
  read(n,k);
  re;
  qsort(1,n);
  main;
end.