orz JZP神new的二分加线段树套SBT。

把maintain去掉后的时间如下：

编译通过...

├ 测试数据 01：答案正确... 759ms

├ 测试数据 02：答案正确... 1291ms

├ 测试数据 03：答案正确... 9ms

├ 测试数据 04：答案正确... 619ms

├ 测试数据 05：答案正确... 712ms

├ 测试数据 06：答案正确... 869ms

├ 测试数据 07：答案正确... 1338ms

├ 测试数据 08：答案正确... 1181ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 291ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：7069ms

看来数据的确没有卡平衡树。

不过我还有一个疑问：能不能不用二分？直接把若干个SBT暴力接起来？询问结束后直接暴力切开？这样不是少了一个log？

澳淄楼下神牛！

先离散化序列中所有的数（包括询问时需要改的数），离散化后建立一棵线段树，然后在每个线段树中的节点里套一个平衡树，平衡树中存的是当前整个序列中的数值范围在该线段树节点所代表的区间内的所有的位置，这样就可以做成O(Mlog^2N)

（囧，这个貌似比三次方的慢。。。。）

const maxn=2000000;

maxm= 200000;

maxv= 20000;

var left,right,size,sb:array[0..maxn]of longint;

lt,rt,l,r,t,a,c:array[0..maxm]of longint;

ch:array[1..maxv]of char;

b:array[1..maxv,1..3]of longint;

j,num,nj,k,n,m,i,mj,p,l1,l2:longint;

cc:char;

procedure xp(var a,b:longint);

var t:longint;

begin

t:=a; a:=b; b:=t;

end;

procedure quicksort(s,t:longint);

var i,j,k:longint;

begin

i:=s; j:=t; k:=c[(s+t) shr 1];

repeat

while kc[i] do inc(i);

if ij;

if ssize[left[t]] then begin

rightr(right[t]); leftr(t);

end else exit;

end;

maintain(left[t],false);

maintain(right[t],true);

maintain(t,false);

maintain(t,true);

end;

procedure insert(var t:longint; k:longint);

begin

if t=0 then begin

inc(nj); t:=nj;

size[t]:=1; sb[t]:=k;

exit;

end;

inc(size[t]);

if k=sb[t]);

end;

function small(t,k:longint):longint;

begin

if t=0 then exit(0);

if sb[t]>=k then exit(small(left[t],k));

small:=size[left[t]]+1+small(right[t],k);

end;

procedure getin(v,p,i:longint);

begin

insert(t[v],i);

if l[v]

做了一节信息课+一节体育课+一个晚上,这足可见我是一个超级大沙茶......

在提交前经过千次万次的检查和测试后终于一次AC......

VJ真不给面子,有Vivid Puppy最后一个点就可以秒杀了......

ZOJ 2112弱弱版.内存限制没ZOJ2112那么紧

前十

ps:下面代码已坐过手脚~

program Project1;

const

maxn=50000;

type

pnode=^node;

node=record

data,size:longint;

lch,rch:pnode;

end;

treenode=record

root:pnode;

l,r,lch,rch:longint;

end;

var

tree:array[0..maxn*2+1]of treenode;

a:array[0..maxn]of longint;

m,n,i,j,k,tot,w,t,b,mid:longint;

ch,ch1:char;

null:pnode;

ttt:longint;

procedure lrotate(var x:pnode);

var

y:pnode;

begin

if x=null

then exit;

y:=x^.rch;

x^.rch:=y^.lch;

y^.lch:=x;

y^.size:=x^.size;

x^.size:=x^.lch^.size+x^.rch^.size+1;

x:=y;

end;

procedure rrotate(var x:pnode);

var

y:pnode;

begin

if x=null

then exit;

y:=x^.lch;

x^.lch:=y^.rch;

y^.rch:=x;

y^.size:=x^.size;

x^.size:=x^.lch^.size+x^.rch^.size+1;

x:=y;

end;

procedure maintain(var t:pnode;flag:boolean);

begin

if t=null

then exit;

if not flag

then if t^.lch^.lch^.size>t^.rch^.size

then rrotate(t)

else if t^.lch^.rch^.size>t^.rch^.size

then begin

lrotate(t^.lch);

rrotate(t);

end

else exit

else if t^.rch^.rch^.size>t^.lch^.size

then lrotate(t)

else if t^.rch^.lch^.size>t^.lch^.size

then begin

rrotate(t^.rch);

lrotate(t);

end

else exit;

maintain(t^.lch,false);

maintain(t^.rch,true);

maintain(t,false);

maintain(t,true);

end;

procedure insert(var t:pnode;v:longint);

begin

if t=null

then begin

new(t);

t^.data:=v;

t^.size:=1;

t^.lch:=null;

t^.rch:=null;

end

else begin

inc(t^.size);

if v=t^.data);

end;

end;

function rank(var t:pnode;v:longint):longint;

begin

if t=null

then exit(0);

if v>=t^.data

then exit(rank(t^.rch,v))

else exit(t^.rch^.size+1+rank(t^.lch,v));

end;

function delete(var t:pnode;v:longint):longint;

var

tmp:pnode;

begin

if t=null

then exit;;

dec(t^.size);

if((v=t^.data)or((vt^.data)and(t^.rch=null))

then begin

delete:=t^.data;

if((t^.lch=null)or(t^.rch=null))

then begin

if t^.lch=null

then begin

tmp:=t;

t:=tmp^.rch;

dispose(tmp);

end

else if t^.rch=null

then begin

tmp:=t;

t:=tmp^.lch;

dispose(tmp);

end;

end

else delete:=delete(t^.lch,t^.data+1);

end

else if v=a)and(tree[t].r=a)

then inc(res,query(tree[t].lch,a,b,v));

if(tree[tree[t].rch].l

• -! 二分+树套树`o(m\*logN\*logN*logN)\``居然一次性提交AC

这道题是原始的线段树题目改了一下

终于AC了。。调试了3节晚自习+1晚上+1早晨+1早自习+第一节课+一中午+半个午休时间。。。。用的线段树套sbt。。第一次写啊。。激动。。

线段树经典例题！

原来新的评测机这么牛叉：

编译通过...

├ 测试数据 01：答案正确... 25ms

├ 测试数据 02：答案正确... 41ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 72ms

├ 测试数据 07：答案正确... 25ms

├ 测试数据 08：答案正确... 41ms

├ 测试数据 09：答案正确... 88ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：292ms

线段树套平衡树

出题人不要装B

难度4是我改的

这难道不是平衡树吗？

刚看我以为是银河英雄传说。。。

jiong

我写过的最长的程序 305行

楼下说的没错

真蛋疼

这几天都是经典题目出现...

树 套 树 牛B

参见jzp神new的文章、yxy神new的文章

PS:此题是后者出的...（yxy别BS我）

( 2009-10-6 20:19:08 )

---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|--

Accepted 有效得分：100 有效耗时：5907ms

终于AC了~

二分答案+SBT+线段树，85行2.2KB的程序，速度还是可以的！

太烦了。。做不了

树套树。。。zoj有原题