题解 P2709 【小B的询问】

题目描述见此处：传送门https://www.luogu.org/problemnew/show/P2709 我交了n遍才过，所以评测记录几乎被我占了1页，求 管理大大不要怪我...... -------------------------------------分割线 解题思路：

此题第一眼：数据结构; 第二眼：暴力O*(n^3); 第三遍(线段树TLE);

最后一眼：莫队似乎可以做哦。

于是我们考虑听y大所说的莫涛队长发明的算法——莫队。

我们还是从暴力写起：

第一遍，无序，让l和r乱跳，时间O(n^2q)爆TLE！

第二遍，排序后莫队，让l有序，r乱跳，时间O(NQ*LG(N)) 还是TLE！

第三遍，考虑分块优化，如果快排时的左端点i和右端点j在同一区间内，即i div sqrt(n)=j div sqrt(n)

那么i，j在同一区间，直接以y数组排序为第一关键字排序即可。

否则以x数组为第一关键字排序。（具体见代码）

我来发个p的题解，也算是为p党做个小贡献。

(现在用p的人真得不多了)

var
  n,k,m,l,r,j,i,p:longint;
  ans:int64;
  a,x,y,c,b,f:array[0..500005] of longint;
procedure sort(l,r:longint);//库里自带的快排
做了些小改动。(这点p真的比不上c++的STL)
      var
         i,j,xx,yy,yyy:longint;
      begin
         i:=l;
         j:=r;
         xx:=x[(l+r) div 2];
         yy:=y[(l+r) div 2];//多关键字排序
         repeat
           if i div p=j div p then//判断i，j是否在同一块内
           begin
           while (x[i]<xx) do
            inc(i);
           while (xx<x[j]) do
            dec(j);
           if not(i>j) then//别忘记交换3个而不是1个数组
             begin
                yyy:=x[i];
                x[i]:=x[j];
                x[j]:=yyy;
                yyy:=y[i];
                y[i]:=y[j];
                y[j]:=yyy;
                yyy:=c[i];
                c[i]:=c[j];
                c[j]:=yyy;
                inc(i);
                j:=j-1;
             end;
           end else
           begin//这部分作用同上
             while (y[i]<yy) do
            inc(i);
           while (yy<y[j]) do
            dec(j);
           if not(i>j) then
             begin
                yyy:=x[i];
                x[i]:=x[j];
                x[j]:=yyy;
                yyy:=y[i];
                y[i]:=y[j];
                y[j]:=yyy;
                yyy:=c[i];
                c[i]:=c[j];
                c[j]:=yyy;
                inc(i);
                j:=j-1;
             end;
           end;
         until i>j;
         if l<j then
           sort(l,j);
         if i<r then
           sort(i,r);
      end;
begin
  readln(n,m,k);
  p:=trunc(sqrt(n));//把序列分成sqrt(n)块
  for i:=1 to n do read(a[i]);
  for i:=1 to m do
  begin
    readln(x[i],y[i]);//莫队作为离线算法，当然要保存每个询问啦
    c[i]:=i;//c[i]表示当前读入的是第i个数
  end;
  sort(1,m);
  l:=1;
  r:=0;
  ans:=0;
  fillchar(b,sizeof(b),0);
  for i:=1 to m do//莫队基本思想(本人喜欢while)
  begin
    while l>x[i] do begin dec(l); inc(b[a[l]]); ans:=ans+(2*b[a[l]]-1); end;
    while r<y[i] do begin inc(r); inc(b[a[r]]); ans:=ans+(2*b[a[r]]-1); end;
    while l<x[i] do begin dec(b[a[l]]); ans:=ans-(2*b[a[l]]+1); inc(l); end;
    while r>y[i] do begin dec(b[a[r]]); ans:=ans-(2*b[a[r]]+1); dec(r); end;
    f[c[i]]:=ans;//用f数组记录读进来时第1-n个答案
  end;
  for i:=1 to m do writeln(f[i]);
end.