bzoj3289: Mato的文件管理【莫队算法+树状数组】

  • 内容
  • 评论
  • 相关

刚学了莫队,多做道题目巩固一下~


题目点击这里

易知按照最优策略交换每次可以减少一个逆序对,所以这题本质上是求区间逆序对数量。

关于逆序对的数量。如果我们在当前区间后面插入一个数,那么就会增加当前区间比插入的数字大的数的数量的逆序对;如果在区间后面插入一个数,那么就会增加比当前区间比插入的数字小的数的数量的逆序对,如果是去掉一个数就反过来。求逆序对有很多方法,但为了符合这题用的莫队算法,所以我们要选择能快速递推的方法。树状数组只要O(logN)的时间就能走一步,而且常数不大,那么就它了。

然后就套上莫队的模板,注意处理的时候l和r的加减和修改查询的顺序。


代码:

{$inline on}
var
  a:array[0..50000,1..3] of longint;
  t,y,p,ans:array[1..50000] of longint;
  n,m,i,j,k,block,l,r:longint;
procedure sort(l,r:longint);
var
  i,j,x,y:longint;
begin
  i:=l;
  j:=r;
  x:=a[(l+r) div 2,1];
  repeat
    while a[i,1]<x do
    inc(i);
    while x<a[j,1] do
    dec(j);
    if not(i>j) then
    begin
      a[0]:=a[i];
      a[i]:=a[j];
      a[j]:=a[0];
      inc(i);
      j:=j-1;
    end;
  until i>j;
  if l<j then
  sort(l,j);
  if i<r then
  sort(i,r);
end;
procedure sort2(l,r:longint);
var
  i,j,x,y,k:longint;
begin
  i:=l;
  j:=r;
  x:=p[a[(l+r) div 2,1]];
  y:=a[(l+r) div 2,2];
  repeat
    while (p[a[i,1]]<x) or (p[a[i,1]]=x) and (a[i,2]<y) do
    inc(i);
    while (x<p[a[j,1]]) or (x=p[a[j,1]]) and (y<a[j,2]) do
    dec(j);
    if not(i>j) then
    begin
      a[0]:=a[i];
      a[i]:=a[j];
      a[j]:=a[0];
      inc(i);
      j:=j-1;
    end;
  until i>j;
  if l<j then
  sort2(l,j);
  if i<r then
  sort2(i,r);
end;
function lb(x:longint):longint; inline;
begin
  exit(x and -x);
end;
procedure change(x,k:longint); inline;
var
  i:longint;
begin
  i:=x;
  while i<=n do
  begin
    t[i]:=t[i]+k;
    i:=i+lb(i);
  end;
end;
function query(x:longint):longint;   inline;
var
  i,ans:longint;
begin
  i:=x;
  ans:=0;
  while i>0 do
  begin
    ans:=ans+t[i];
    i:=i-lb(i);
  end;
  exit(ans);
end;
begin
  read(n);
  block:=trunc(sqrt(n));
  for i:=1 to n do
  begin
    read(a[i,1]);
    a[i,2]:=i;
    p[i]:=(i-1) div block;
  end;
  sort(1,n);
  for i:=1 to n do
  y[a[i,2]]:=i;
  read(m);
  for i:=1 to m do
  begin
    read(a[i,1],a[i,2]);
    a[i,3]:=i;
  end;
  sort2(1,m);
  k:=0;
  l:=1;
  r:=0;
  for i:=1 to m do
  begin
    if r<a[i,2] then
    for j:=r+1 to a[i,2] do
    begin
      inc(r);
      change(y[j],1);
      k:=k+r-l+1-query(y[j]);
    end;
    if r>a[i,2] then
    for j:=r downto a[i,2]+1 do
    begin
      change(y[j],-1);
      k:=k-(r-l-query(y[j]));
      dec(r);
    end;
    if l<a[i,1] then
    for j:=l to a[i,1]-1 do
    begin
      change(y[j],-1);
      k:=k-query(y[j]-1);
      inc(l);
    end;
    if l>a[i,1] then
    for j:=l-1 downto a[i,1] do
    begin
      dec(l);
      change(y[j],1);
      k:=k+query(y[j]-1);
    end;
    ans[a[i,3]]:=k;
  end;
  for i:=1 to m do writeln(ans[i]);
end.

ps:inline大法好,原来22S的程序硬生生变成了10S。。。
退役倒计时:26天

评论

0条评论

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.