题解 P4168 【[Violet]蒲公英】

· · 题解

犹豫了很久还是决定来写一篇Pascal题解。

经典的分块入门题。

简单介绍一下分块：

把数据分成一些块，然后预处理。

维护或查询数据时，中间连续的几个块一起操作，边角暴力。

小于两个块的话就直接暴力了。

一般每个块的大小为\sqrt{n}。

当题目强制在线的话用分块，离线就可以用莫队了。

先看题目，1\le a_i\le 10^9。肯定要离散化。

然后就是预处理。这是分块里面很重要的一步。这个想出来以后做题就不难了。

求区间众数需要每个数出现的数量。考虑用前缀和对每一个块维护。

我们还需要维护连续的几个块的众数。

查询的时候直接枚举边角的数就好了（边角暴力）。

详细还是见代码吧：

{P4168}
var
  a,d,p,sum,temp:array[1..40000]of longint;//a是原始数组（后来被离散化了），p是离散化前原始的数值，d和temp用来离散化（具体看主程序），sum是查询过程中统计数量的
  s:array[0..200,1..40000]of longint;//预处理的前缀和
  m:array[1..200,1..200]of longint;//区间众数
  n,q,i,x,l,r,num,size,last:longint;
function min(x,y:longint):longint;//不解释
begin
  if x<y then
    exit(x)
  else
    exit(y);
end;
procedure swap(var x,y:longint);//不解释
var
  t:longint;
begin
  t:=x;
  x:=y;
  y:=t;
end;
procedure quicksort(l,r:longint);//不解释
var
  i,j,m,t:longint;
begin
  i:=l;
  j:=r;
  m:=a[(l+r) div 2];
  repeat
    while a[i]<m do
      inc(i);
    while a[j]>m do
      dec(j);
    if i<=j then
    begin
      t:=a[i];
      a[i]:=a[j];
      a[j]:=t;
      t:=d[i];
      d[i]:=d[j];
      d[j]:=t;
      inc(i);
      dec(j);
    end;
  until i>j;
  if l<j then
    quicksort(l,j);
  if i<r then
    quicksort(i,r);
end;
procedure init;                //初始化
var
  i,j,k:longint;
begin
  for i:=1 to num do
  begin
    for j:=1 to x do
      s[i,j]:=s[i-1,j];
    for j:=(i-1)*size+1 to min(n,i*size) do//计算前缀和
      inc(s[i,a[j]]);
    for j:=1 to i do           //计算从第j个块到第i个块的区间众数
    begin
      m[j,i]:=1;
      for k:=2 to x do         //暴力枚举
        if s[i,k]-s[j-1,k]>s[i,m[j,i]]-s[j-1,m[j,i]] then
          m[j,i]:=k;
    end;
  end;
end;
function query(l,r:longint):longint;//查询
var
  i,tl,tr:longint;
begin
  tl:=(l-1) div size+1;        //l所在的块
  tr:=(r-1) div size+1;        //r所在的块
  if tr-tl<=1 then             //小于2个块直接暴力
  begin
    for i:=l to r do
      sum[a[i]]:=0;
    for i:=l to r do           //把所有数的数量都统计出来
      inc(sum[a[i]]);
    query:=a[l];
    for i:=l+1 to r do         //暴力枚举
      if (sum[a[i]]>sum[query]) or (sum[a[i]]=sum[query]) and (a[i]<query) then
        query:=a[i];
  end
  else
  begin
    sum[m[tl+1,tr-1]]:=s[tr-1,m[tl+1,tr-1]]-s[tl,m[tl+1,tr-1]];//先把区间众数的数量统计好
    for i:=l to min(n,tl*size) do//统计每个边角的数在块内的数量
      sum[a[i]]:=s[tr-1,a[i]]-s[tl,a[i]];
    for i:=(tr-1)*size+1 to r do
      sum[a[i]]:=s[tr-1,a[i]]-s[tl,a[i]];
    for i:=l to min(n,tl*size) do//统计边角的数量
      inc(sum[a[i]]);
    for i:=(tr-1)*size+1 to r do
      inc(sum[a[i]]);
    query:=m[tl+1,tr-1];
    for i:=l to min(n,tl*size) do//暴力枚举
      if (sum[a[i]]>sum[query]) or (sum[a[i]]=sum[query]) and (a[i]<query) then
        query:=a[i];
    for i:=(tr-1)*size+1 to r do
      if (sum[a[i]]>sum[query]) or (sum[a[i]]=sum[query]) and (a[i]<query) then
        query:=a[i];
  end;
  query:=p[query];             //注意离散化过，要把答案转回去
end;
begin
  read(n,q);
  size:=trunc(sqrt(n));        //块的大小
  num:=(n-1) div size+1;       //一共有几块
  for i:=1 to n do
  begin
    read(a[i]);                //读入
    d[i]:=i;                   //把序号记下来，方便离散化
  end;
  quicksort(1,n);              //排序
  x:=a[1];                     //写的极丑的离散化
  a[1]:=1;
  p[1]:=x;
  for i:=2 to n do
    if a[i]=x then
      a[i]:=a[i-1]
    else
    begin
      x:=a[i];
      a[i]:=a[i-1]+1;
      p[a[i]]:=x;
    end;
  x:=a[n];
  temp:=a;
  for i:=1 to n do
    a[d[i]]:=temp[i];
  init;
  last:=0;
  for i:=1 to q do             //查询部分
  begin
    read(l,r);
    l:=(l+last-1) mod n+1;     //强制在线
    r:=(r+last-1) mod n+1;
    if l>r then
      swap(l,r);
    last:=query(l,r);
    writeln(last);
  end;
end.