学步园

http://www.tsinsen.com/ViewGProblem.html?gpid=-1000001310

　　对于全部数据
　　1<=n,m<=200
　　q<=100000
　　|矩阵元素大小|<=2*10⁹

首先考虑颜色少于200种的解法

对于每种颜色开一个n*m的矩阵,f[i,j]表示以(1,1)为左上角,(i,j)为右下角的举行中包含这种颜色的有多少个

这样就可以在O(1)的时间内求出来一个举行中有该种颜色多少个了

设颜色种类为c，复杂度为O(cq)

颜色多了自然不可解……

如何解决呢

假设有一个划分标准p

在矩阵中出现次数多于p次的颜色按上面的做法来做，那么回答一次询问的复杂度为n*m/p

少于的我们采用另外一种做法

一个矩阵里一种颜色的出现次数的平方等于以两个相同颜色的点为顶点形成的在询问的矩形里的矩形个数

所以可以预先把这些矩形生成出来，查询当前矩形包含多少个矩形

矩形个数最多为n*m/p*p^2=nmp个

查询矩形内有多少个矩形，满足的条件为x1<=x1i,x2i<=x2,y1<=y1i,y2i<=y2

这个可以用四维树状数组来求

但是四维树状数组复杂度为log^4 n，这道题又不存在修改，询问之间也没有关系

所以可以离线来做，按询问x1从大到小来回答询问，然后按x1从大到小来插入矩形，这样用三维树状数组即可完成

（为什么不用线段树……因为线段树空间复杂度为(2n)^3，常数还较大……会爆空间）

至此，这道题完全解决，虽然复杂度算下来要超时，但实际上是跑得过的……

顺道一提，这个颜色少于200种用这个方法跑的比较慢……直接用最初的方法就好了

我的p取值为sqrt((n*m+q)/2)

{$inline on}
program t2;
type
  node=record
         x1,x2,y1,y2:longint;
       end;
const
  maxn=400001;

var
  w:longint;
  o,sum,p,all,tot,n,m,i,j,k,q,x1,y1,x2,y2,u,v:longint;
  num,count,new:array [0..40001] of longint;
  map:array [0..201,0..201] of longint;
  quick:array [0..401,0..201,0..201] of longint;
  tree:array [0..201,0..201,0..201] of longint;
  ans:array [0..100001] of longint;
  dl:array [0..100001] of longint;
  que:array [0..100001] of node;
  four:array [0..maxn] of node;
  x,y:array [0..40001] of longint;

procedure swap (var a,b:longint);inline;
begin
  if a=b then exit;
  b:=a xor b;
  a:=a xor b;
  b:=a xor b;
end;

procedure disp;

  procedure qsort (s,e:longint);
  var
    i,j,k:longint;
  begin
    if s>=e then exit;
    i:=s;
    j:=e;
    k:=dl[(s+e) div 2];
    while i<=j do
      begin
        while dl[i]<k do inc(i);
        while dl[j]>k do dec(j);
        if i>j then break;
        swap(dl[i],dl[j]);
        inc(i);
        dec(j);
      end;
    qsort(s,j);
    qsort(i,e);
  end;

begin
  qsort(1,tot);
  all:=0;
  i:=1;
  while i<=tot do
    begin
      k:=i;
      while dl[i]=dl[k] do inc(i);
      inc(all);
      new[all]:=dl[k];
    end;
end;

procedure renum;inline;

  function convert (now:longint):longint;inline;
  var
    mid,s,e:longint;
  begin
    s:=1;
    e:=all;
    while s<>e do
      begin
        mid:=(s+e) div 2;
        if new[mid]<now then s:=mid+1
                        else e:=mid;
      end;
    exit(s);
  end;

begin
  for i:=1 to n do
    for j:=1 to m do
      begin
        map[i,j]:=convert(map[i,j]);
        inc(count[map[i,j]]);
      end;
end;

procedure case1;inline;
var
  ans,w:longint;
begin
  tot:=0;
  for i:=1 to all do
    if count[i]>=p then
      begin
        inc(tot);
        for j:=1 to n do
          for k:=1 to m do
            begin
              quick[tot,j,k]:=quick[tot,j-1,k]
                             +quick[tot,j,k-1]
                             -quick[tot,j-1,k-1];
              if map[j,k]=i then inc(quick[tot,j,k]);
            end;
      end;
  if p<>0 then exit;
  read(q);
  for i:=1 to q do
    begin
      read(x1,y1,x2,y2);
      if x1>x2 then swap(x1,x2);
      if y1>y2 then swap(y1,y2);
      ans:=0;
      for k:=1 to tot do
        begin
          w:=quick[k,x2,y2]
            -quick[k,x1-1,y2]
            -quick[k,x2,y1-1]
            +quick[k,x1-1,y1-1];
          ans:=ans+w*w;
        end;
      writeln(ans);
    end;
  halt;
end;

procedure case2;

  procedure qsort (s,e:longint);
  var
    i,j,k:longint;
  begin
    if s>=e then exit;
    i:=s;
    j:=e;
    k:=map[x[(s+e) div 2],y[(s+e) div 2]];
    while i<=j do
      begin
        while map[x[i],y[i]]<k do inc(i);
        while map[x[j],y[j]]>k do dec(j);
        if i>j then break;
        swap(x[i],x[j]);
        swap(y[i],y[j]);
        inc(i);
        dec(j);
      end;
    qsort(s,j);
    qsort(i,e);
  end;

  procedure qsort1 (s,e:longint);
  var
    i,j,k:longint;

    procedure swap (var a,b:node);inline;
    var
      i:node;
    begin
      i:=a;
      a:=b;
      b:=i;
    end;

  begin
    if s>=e then exit;
    i:=s;
    j:=e;
    k:=four[(s+e) div 2].x1;
    while i<=j do
      begin
        while four[i].x1<k do inc(i);
        while four[j].x1>k do dec(j);
        if i>j then break;
        swap(four[i],four[j]);
        inc(i);
        dec(j);
      end;
    qsort1(s,j);
    qsort1(i,e);
  end;

begin
  o:=0;
  for i:=1 to n do
    for j:=1 to m do
      if count[map[i,j]]<p then
        begin
          inc(o);
          x[o]:=i;
          y[o]:=j;
        end;
  qsort(1,o);
  sum:=0;
  i:=1;
  while i<=o do
    begin
      k:=i;
      while (i<=o)and(map[x[i],y[i]]=map[x[k],y[k]]) do inc(i);
      for u:=k to i-1 do
        for v:=k to i-1 do
          begin
            x1:=x[u];
            y1:=y[u];
            x2:=x[v];
            y2:=y[v];
            if x1>x2 then swap(x1,x2);
            if y1>y2 then swap(y1,y2);
            inc(sum);
            four[sum].x1:=x1;
            four[sum].x2:=x2;
            four[sum].y1:=y1;
            four[sum].y2:=y2;
          end;
    end;
  qsort1(1,sum);
end;

procedure question;

  procedure qsort (s,e:longint);
  var
    i,j,k:longint;
  begin
    if s>=e then exit;
    i:=s;
    j:=e;
    k:=dl[(s+e) div 2];
    while i<=j do
      begin
        while que[dl[i]].x1<que[k].x1 do inc(i);
        while que[dl[j]].x1>que[k].x1 do dec(j);
        if i>j then break;
        swap(dl[i],dl[j]);
        inc(i);
        dec(j);
      end;
    qsort(s,j);
    qsort(i,e);
  end;

begin
  read(q);
  for i:=1 to q do
    begin
      read(x1,y1,x2,y2);
      if x1>x2 then swap(x1,x2);
      if y1>y2 then swap(y1,y2);
      que[i].x1:=x1;
      que[i].x2:=x2;
      que[i].y1:=y1;

      que[i].y2:=y2;
      dl[i]:=i;
    end;
  qsort(1,q);
end;

function lowbit (x:longint):longint;inline;
begin
  exit(x and (x xor (x-1)));
end;

procedure insert (x2,y1,y2:longint);
var
  i,j,k:longint;
begin
  i:=x2;
  while i<=n do
    begin
      j:=y1;
      while j<=m do
        begin
          k:=y2;
          while k<=m do
            begin
              inc(tree[i,j,k]);
              k:=k+lowbit(k);
            end;
          j:=j+lowbit(j);
        end;
      i:=i+lowbit(i);
    end;
end;

function find (x2,y1,y2:longint):longint;
var
  ans:longint;
  i,j,k:longint;
begin
  ans:=0;
  i:=x2;
  while i>0 do
    begin
      j:=m;
      while j>0 do
        begin
          k:=y2;
          while k>0 do
            begin
              ans:=ans+tree[i,j,k];
              k:=k-lowbit(k);
            end;
          j:=j-lowbit(j);
        end;
      j:=y1-1;
      while j>0 do
        begin
          k:=y2;
          while k>0 do
            begin
              ans:=ans-tree[i,j,k];
              k:=k-lowbit(k);
            end;
          j:=j-lowbit(j);
        end;
      i:=i-lowbit(i);
    end;
  exit(ans);
end;

procedure solve;
begin
  k:=sum;
  for i:=q downto 1 do
    begin
      x1:=que[dl[i]].x1;
      x2:=que[dl[i]].x2;
      y1:=que[dl[i]].y1;
      y2:=que[dl[i]].y2;
      for j:=1 to tot do
        begin
          w:=quick[j,x2,y2]
            -quick[j,x1-1,y2]
            -quick[j,x2,y1-1]
            +quick[j,x1-1,y1-1];
          ans[dl[i]]:=ans[dl[i]]+w*w;
        end;
      while (k>0)and(four[k].x1>=x1) do
        begin
          insert(four[k].x2,four[k].y1,four[k].y2);
          dec(k);
        end;
      w:=find(x2,y1,y2);
      ans[dl[i]]:=ans[dl[i]]+w;
    end;
end;

begin
  read(n,m);
  for i:=1 to n do
    for j:=1 to m do
      begin
        read(map[i,j]);
        inc(tot);
        dl[tot]:=map[i,j];
      end;
  disp;
////////////////////////////////////////////
  renum;
////////////////////////////////////////////
  if all<=200 then p:=0
              else p:=trunc(sqrt((n*m+q))/2);
  case1;
  case2;
////////////////////////////////////////////
  question;
////////////////////////////////////////////
  solve;
////////////////////////////////////////////
  for i:=1 to q do
    writeln(ans[i]);
end.