BZOJ3289 Mato文件管理 - Hoblovski's Blog - 想拿Ag的蒟蒻.已经Ag滚出.
BZOJ3288 Mato矩阵
BZOJ1509 NOI2003 Hookey

BZOJ3289 Mato文件管理

Hoblovski posted @ 2014年7月13日 00:31 in Solutions with tags bzoj 主席树 莫队算法 逆序对 , 1177 阅读
题意
    一种排序,每次操作只能交换某相邻两元素,本题中你使用这种排序,排升序.
    给定序列A,每次询问排序某区间最小操作数目.
    N,M!>50000,不强制在线,Time Limit 4s
 
Tag 莫队算法,主席树,逆序对
 
排序某序列最小操作数便是序列逆序对数
    1.操作一次至多减少一个逆序对
    2.直到有序,每次我们总能找到一个操作减少一个逆序对.
于是本题就是区间逆序对,听起来比3295还神(事实上两题都不神).
N,M看起来不大不需要O(nlg^?n)的神算法,不强制在线.好,莫队算法能上了.
莫队算法之后我们需要快速统计区间rank.主席树上,O(lgn)区间rank.
于是本题可以在O(N^1.5lgN)时间内解决,由于主席树在这里相对常数较大所以勉强能过
 
其实完全没有必要动用主席树,对于当前区间维护一个BIT即可,常数小一大半.
 
Mato三题终于全部A掉了,全部是独立A掉真开心\(^_^)/,从人数少切到人数多逗比.回顾一下,一道找规律+FFT,一道行列式变换+线性筛,一道莫队算法+主席树,也能算是NOI水平了吧.顺便后两题都是在Linux下面写的,幸好1A不然调成狗....,参见某zkw费用流因为少打了一个if v[i] then..就调了20分钟的事迹
 
program bzoj3289;
 
type tquery=record
        l,r,b,p:longint;
     end;
     tnode=record
        v,l,r:longint;
     end;
 
const maxn=50017;
      maxalloc=8000017;
 
var q:array[0..maxn] of tquery;
    a,node,val:array[0..maxn] of longint;
    ans:array[0..maxn] of dword;
    mem:array[0..maxalloc] of tnode;
    n,m,bs,vc,memsize:longint;
    curans:dword;
 
procedure chair_init;                               begin
memsize:=0; mem[0].v:=0; mem[0].l:=0; mem[0].r:=0;  end;
 
function insert(i,j,d:longint):longint;
var k,l,r,mid:longint;
begin
inc(memsize); insert:=memsize; k:=memsize; l:=1; r:=vc;
while l<>r do begin
        mem[k].v:=mem[i].v+1; mid:=(l+r)>>1;
        if j<=mid then begin
                mem[k].r:=mem[i].r; i:=mem[i].l; inc(memsize); mem[k].l:=memsize; k:=memsize; r:=mid;
        end else begin
                mem[k].l:=mem[i].l; i:=mem[i].r; inc(memsize); mem[k].r:=memsize; k:=memsize; l:=mid+1;
        end;
end; mem[k].v:=mem[i].v+1; mem[k].l:=0; mem[k].r:=0;
end;
 
function intrank(l,r,i:longint):longint;
var mid,u,v:longint;
begin
if l>r then exit(0); intrank:=0; u:=node[l-1]; v:=node[r]; l:=1; r:=vc; while l<>r do begin
        mid:=(l+r)>>1; if i<=mid then begin
                u:=mem[u].l; v:=mem[v].l; r:=mid;
        end else begin inc(intrank,mem[mem[v].l].v-mem[mem[u].l].v);
                u:=mem[u].r; v:=mem[v].r; l:=mid+1;
        end;
end;
end;
 
function inttank(l,r,i:longint):longint;
var mid,u,v:longint;
begin
if l>r then exit(0); inttank:=0; u:=node[l-1]; v:=node[r]; l:=1; r:=vc; while l<>r do begin
        mid:=(l+r)>>1; if i>mid then begin
                u:=mem[u].r; v:=mem[v].r; l:=mid+1;
        end else begin inc(inttank,mem[mem[v].r].v-mem[mem[u].r].v);
                u:=mem[u].l; v:=mem[v].l; r:=mid;
        end;
end;
end;
 
procedure qsort2(l,r:longint);
var i,j,k1,k2:longint;
        o:tquery;
begin
i:=l; j:=r; with q[l+random(r-l+1)] do begin k1:=b; k2:=r; end;
repeat
        while (q[i].b<k1)or((q[i].b=k1)and(q[i].r<k2)) do inc(i);
        while (q[j].b>k1)or((q[j].b=k1)and(q[j].r>k2)) do dec(j);
        if i<=j then begin
                o:=q[i]; q[i]:=q[j]; q[j]:=o;
                inc(i); dec(j);
        end;
until i>j;
if i<r then qsort2(i,r);
if j>l then qsort2(l,j);
end;
 
procedure qsort1(l,r:longint);
var i,j,k,o:longint;
begin
i:=l; j:=r; k:=val[l+random(r-l+1)];
repeat
        while val[i]<k do inc(i);
        while val[j]>k do dec(j);
        if i<=j then begin
                o:=val[i]; val[i]:=val[j]; val[j]:=o;
                inc(i); dec(j);
        end;
until i>j;
if i<r then qsort1(i,r);
if j>l then qsort1(l,j);
end;
 
function binfind(i:longint):longint;
var l,r,mid:longint;
begin
l:=1; r:=vc; while l<>r do begin
        mid:=(l+r)>>1; if val[mid]<i then l:=mid+1 else r:=mid;
end; exit(l);
end;
 
procedure discret;
var i,j:longint;
begin
qsort1(1,vc); j:=1; for i:=2 to vc do if val[i]<>val[j] then begin
        inc(j); val[j]:=val[i];
end; vc:=j; for i:=1 to n do a[i]:=binfind(a[i]);
end;
 
procedure init;
var i,j,k:longint;
begin
readln(n); for i:=1 to n do begin
        read(a[i]); inc(vc); val[vc]:=a[i];
end; readln; discret; for i:=1 to n do node[i]:=insert(node[i-1],a[i],1);  bs:=trunc(sqrt(n));
readln(m); for i:=1 to m do begin readln(q[i].l,q[i].r); q[i].p:=i; q[i].b:=q[i].l div bs; end;
qsort2(1,m);
end;
 
procedure moteam;
var i,j,l,r:longint;
begin
l:=1; r:=1; curans:=0; for i:=1 to m do begin
        while l<q[i].l do begin dec(curans,intrank(l,r,a[l])); inc(l); end;
        while r>q[i].r do begin dec(curans,inttank(l,r,a[r])); dec(r); end;
        while l>q[i].l do begin dec(l); inc(curans,intrank(l,r,a[l])); end;
        while r<q[i].r do begin inc(r); inc(curans,inttank(l,r,a[r])); end;
        ans[q[i].p]:=curans;
end;
end;
 
procedure answer;
var i:longint;
begin
for i:=1 to m do writeln(ans[i]);
end;
 
begin
init;
moteam;
answer;
end.

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter