1.Ai下界?

2.下标错了

3.ai<=2^31 意思是Ai=2^31可能?那longint就存不下了?

Tag 维护平衡树

反正归并什么的都没有平衡树灵活吧

A序列可以有重复,这时一般的平衡树就不行了

考虑递推

f[i]:i..n区间内小于Ai的Aj的个数

每个i开始的三元逆序对计数=sigma(f[j]) (j>i,Aj<Ai)

如果直接开数组时间仍然O(n²)故把f放在平衡树里面维护

为什么每次都要吞我的缩进...

/* 可能我想的太复杂了 反正40分钟里写出来了就对了... */

program rq305;

type pnode=^tnode;

tnode=record

v:int64;

p,size,w:longint;

inv,sum:int64;

l,r:pnode;

end;

const limit=longint($3f3f3f3f);

var pnil,root:pnode;

n:longint;

sequ:array[1..2517] of int64;

ans:int64;

procedure lrot(var i:pnode);

var rkid,tmp:pnode;

begin

rkid:=i^.r;

i^.r:=rkid^.l;

rkid^.l:=i;

tmp:=rkid; rkid:=i; i:=tmp;

rkid^.size:=rkid^.w+rkid^.l^.size+rkid^.r^.size;

i^.size:=i^.w+i^.l^.size+i^.r^.size;

rkid^.sum:=rkid^.inv+rkid^.l^.sum+rkid^.r^.sum;

i^.sum:=i^.inv+i^.l^.sum+i^.r^.sum;

end;

procedure rrot(var i:pnode);

var lkid,tmp:pnode;

begin

lkid:=i^.l;

i^.l:=lkid^.r;

lkid^.r:=i;

tmp:=lkid; lkid:=i; i:=tmp;

lkid^.size:=lkid^.w+lkid^.l^.size+lkid^.r^.size;

i^.size:=i^.w+i^.l^.size+i^.r^.size;

lkid^.sum:=lkid^.inv+lkid^.l^.sum+lkid^.r^.sum;

i^.sum:=i^.inv+i^.l^.sum+i^.r^.sum;

end;

procedure ins(var i:pnode;j:int64;rank:longint);

begin

if i=pnil then begin

new(i);

with i^ do begin

v:=j; p:=random(limit);

l:=pnil; r:=pnil;

size:=1; w:=1;

inv:=rank; sum:=rank;

end;

end else

if j<i^.v then begin

ins(i^.l,j,rank);

inc(i^.size);

i^.sum:=i^.inv+i^.l^.sum+i^.r^.sum;

if i^.l^.p<i^.p then rrot(i);

end else

if j>i^.v then begin

ins(i^.r,j,rank+i^.l^.size+i^.w);

inc(i^.size);

i^.sum:=i^.inv+i^.l^.sum+i^.r^.sum;

if i^.r^.p<i^.p then lrot(i);

end else begin

inc(i^.w);

inc(i^.size);

inc(i^.inv,rank+i^.l^.size);

inc(i^.sum,rank+i^.l^.size);

end;

end;

procedure treap_init;

begin

new(pnil);

with pnil^ do begin

p:=maxlongint;

v:=0;

w:=0; size:=0;

l:=pnil; r:=pnil;

sum:=0; inv:=0;

end;

root:=pnil;

end;

procedure getrank(var rank,totinv:int64;i:int64);

var t:pnode;

begin

t:=root; rank:=0; totinv:=0;

while t^.v<>i do begin

if i<t^.v then t:=t^.l

else begin

inc(rank,t^.l^.size+t^.w);

inc(totinv,t^.l^.sum+t^.inv);

t:=t^.r;

end;

end;

inc(rank,t^.l^.size);

inc(totinv,t^.l^.sum)

end;

procedure init;

var i,j:longint;

begin

readln(n);

for i:=1 to n do read(sequ[i]);

readln;

end;

procedure work;

var i,j:longint;

totinv,rank:int64;

t1:pnode;

begin

ans:=0;

for i:=n downto 1 do begin

ins(root,sequ[i],0);

getrank(rank,totinv,sequ[i]);

ans:=ans+totinv;

end;

end;

begin

init;

treap_init;

work;

writeln(ans);

end.