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天
发表回复