p1081.pas

数据结构

Vijos p1081
题目是求区间的第k小数，如果区间没有“互不包含”的条件限制，那么只能用线段树O(nlognlognlogn)的算法统计，代码：
const
    maxn=100010;
    maxm=50010;
type
    node=record
        left,right,father,deep:longint;
        l,r,m:longint;
    end;
var
    i,j,k,m,n,p,p1,p2,p3,total,mid,s,r,t,l,ans,top,max,min,w:longint;
    c:array[0..maxn] of longint;
    a:array[0..2*maxn] of node;
    sort:array[0..100,0..maxn] of longint;
    data:array[0..maxn] of longint;
procedure buildtree(t:longint);
var
    i,j,k,x,y,p:longint;
begin
    a[t].deep:=a[a[t].father].deep+1;
    a[t].m:=(a[t].l+a[t].r) shr 1;
    if a[t].l=a[t].r-1 then
    begin
        sort[a[t].deep,a[t].l]:=data[a[t].l];
        exit;
    end;
    inc(top);
    a[top].father:=t;
    a[top].l:=a[t].l;
    a[top].r:=a[t].m;
    a[t].left:=top;
    buildtree(top);
    inc(top);
    a[top].father:=t;
    a[top].l:=a[t].m;
    a[top].r:=a[t].r;
    a[t].right:=top;
    buildtree(top);

    i:=a[t].l;j:=a[t].m;
    x:=a[t].deep;
    k:=a[t].l-1;
    while (i<a[t].m) or (j<a[t].r) do
    begin
        if i=a[t].m then
        begin
            inc(k);
            sort[x,k]:=sort[x+1,j];
            inc(j);
        end
        else if j=a[t].r then
        begin
            inc(k);
            sort[x,k]:=sort[x+1,i];
            inc(i);
        end
        else
        if sort[x+1,i]<sort[x+1,j] then
        begin
            inc(k);
            sort[x,k]:=sort[x+1,i];
            inc(i);
        end
        else begin
            inc(k);
            sort[x,k]:=sort[x+1,j];
            inc(j);
        end;
    end;
end;
procedure swap(var a,b:longint);
var tmp:longint;
begin
    tmp:=a;
    a:=b;
    b:=tmp;
end;
procedure find(t,i,j:longint);
var
    mid:longint;
begin
    mid:=(a[t].l+a[t].r) shr 1;
    if (a[t].l=i) and (a[t].r=j) then
    begin
        if sort[a[t].deep,a[t].l]<min then min:=sort[a[t].deep,a[t].l];
        if sort[a[t].deep,a[t].r-1]>max then max:=sort[a[t].deep,a[t].r-1];
        inc(total);
        c[total]:=t;
        exit;
    end;
    if j<=mid then find(a[t].left,i,j)
    else if i>=mid then find(a[t].right,i,j)
    else begin
        find(a[t].left,i,mid);
        find(a[t].right,mid,j);
    end;
end;
begin
    readln(n,m);
    for i:=1 to n do read(data[i]);
    readln;
    a[0].l:=1;a[0].r:=n+1;
    buildtree(0);

    for i:=1 to m do
    begin
        readln(p1,p2,p3);
        if p1>p2 then swap(p1,p2);
        min:=maxlongint;max:=0;
        total:=0;
        fillchar(c,sizeof(c),0);
        find(0,p1,p2+1);

        while min<=max do
        begin
            w:=(max+min) shr 1;
            k:=0;ans:=0;
            for j:=1 to total do
            begin
                t:=c[j];
                l:=a[t].l;r:=a[t].r-1;
                while l<=r do
                begin
                    mid:=(l+r) div 2;
                    if sort[a[t].deep,mid]<=w then l:=mid+1 else r:=mid-1;
                end;
                ans:=ans+l-a[t].l;
                if (l<>a[t].l) and (k<sort[a[t].deep,l-1]) then k:=sort[a[t].deep,l-1];
            end;
            if ans=p3 then break;
            if ans<p3 then min:=w+1;
            if ans>p3 then max:=w-1;
        end;
        writeln(k);
    end;
end.

但是由于区间互不包含，就有一些特殊算法，可以先按区间的开头顺序从小到大排序。接下来，对于每次操作，先把上一个操作后没用的区间删除掉，再把新加入的元素插入进来。对于每棵树做一次全体的第k小。
要拿一个数组记录一下原始位置。
综上所述,ac了。

uses math;
type
    link=^node;
    node=record
        father,left,right:link;
        key,l:longint;
    end;
    rnode=record
        l,r,k,x:longint;
    end;
var
    i,j,k,m,n,s,r,t:longint;
    a:array[0..500000] of longint;
    b:array[0..100000] of rnode;
    f:array[0..100000] of longint;
    p,q,root,tmp:link;
procedure splay(p:link);
    procedure zig(p:link);
    var
        q:link;
    begin
        q:=p^.father;
        q^.l:=q^.l-1-p^.l;
        p^.father:=q^.father;
        if q=root then root:=p
            else if q=q^.father^.left then q^.father^.left:=p
                else q^.father^.right:=p;
        q^.left:=p^.right;
        if p^.right<>nil then p^.right^.father:=q;
        p^.right:=q;
        q^.father:=p;
    end;
    procedure zag(p:link);
    var
        q:link;
    begin
        q:=p^.father;
        p^.l:=p^.l+q^.l+1;
        p^.father:=q^.father;
        if q=root then root:=p
            else if q=q^.father^.left then q^.father^.left:=p
                else q^.father^.right:=p;
        q^.right:=p^.left;
        if p^.left<>nil then p^.left^.father:=q;
        p^.left:=q;
        q^.father:=p;
    end;
begin
    while p<>root do
    begin
        if p=p^.father^.left then
        begin
            if p^.father=root then zig(p)
            else if p^.father=p^.father^.father^.left then begin zig(p^.father);zig(p)end
            else begin zig(p);zag(p);end;
        end
        else begin
            if p^.father=root then zag(p)
            else if p^.father=p^.father^.father^.right then begin zag(p^.father);zag(p)end
            else begin zag(p);zig(p);end;
        end;
    end;
end;
procedure insert(num:longint);
var
    tmp,p,q:link;
begin
    new(tmp);
    tmp^.key:=num;
    tmp^.l:=0;
    tmp^.left:=nil;tmp^.right:=nil;tmp^.father:=nil;
    if root=nil then root:=tmp
    else begin
        p:=root;
        while p<>nil do
        begin
            q:=p;
            if num<=p^.key then begin
                inc(p^.l);
                p:=p^.left;
            end
            else p:=p^.right;
        end;
        tmp^.father:=q;
        if num<=q^.key then q^.left:=tmp
        else q^.right:=tmp;
        splay(tmp);
    end;
end;
procedure delete(num:longint);
var
    p,q,tmp:link;
begin
    p:=root;
    while (p<>nil) and (p^.key<>num) do
        if p^.key>num then p:=p^.left
        else p:=p^.right;
    splay(p);
    if root^.left=nil then begin root:=root^.right;exit;end;
    if root^.right=nil then begin root:=root^.left;exit;end;
    p:=root^.right;
    root:=root^.left;
    q:=root;
    while q^.right<>nil do q:=q^.right;
    splay(q);
    root^.right:=p;
    p^.father:=q;
end;
procedure sort(l,r:longint);
var
    i,j,x:longint;
    p:rnode;
begin
    i:=l;j:=r;x:=b[(l+r) div 2].l;
    repeat
        while b[i].l<x do inc(i);
        while b[j].l>x do dec(j);
        if i<=j then begin
            p:=b[i];
            b[i]:=b[j];
            b[j]:=p;
            inc(i);
            dec(j);
        end;
    until i>j;
    if i<r then sort(i,r);
    if l<j then sort(l,j);
end;
function find(k:longint):longint;
var
    p,q,tmp:link;
begin
    p:=root;
    while (p^.l<>k) and (p<>nil) do
 if k<p^.l then p:=p^.left
 else begin
  k:=k-p^.l-1;
  p:=p^.right;
 end;
    find:=(p^.key);
end;
procedure swap(var a,b:longint);
var
    tmp:longint;
begin
    tmp:=a;
    a:=b;
    b:=tmp;
end;
begin
    readln(n,m);
    for i:=1 to n do read(a[i]);
    readln;
    for i:=1 to m do
    begin
        readln(b[i].l,b[i].r,b[i].k);
        if b[i].l>b[i].r then swap(b[i].l,b[i].r);
        b[i].x:=i;
    end;
    sort(1,m);
    root:=nil;
    for i:=b[1].l to b[1].r do insert(a[i]);
    f[b[1].x]:=find(b[1].k-1);
    for i:=2 to m do
    begin
        for j:=b[i-1].l to min(b[i-1].r,b[i].l-1) do delete(a[j]);
        for j:=max(b[i].l,b[i-1].r+1) to b[i].r do insert(a[j]);
        f[b[i].x]:=find(b[i].k-1);
    end;
    for i:=1 to m do writeln(f[i]);
end.