BZOJ 3192: [JLOI2013]删除物品 奇淫技巧&树状数组
这题十分奇淫技巧...QAQ因为知道是树状数组的题QAQ刚开始以为维护两个数组的树状数组然后模拟从大到小，然后发现不会打QAQ
于是悄悄咪咪翻开题解了。
实际上两个数组可以看做一个数组
如 1 4 5
2 7 3
实际上就是 5 4 1 | 2 7 3
“|”这个地方就是假设成一个指标，然后每次把这个指标移到某一个位置，这个位置左右两个边的数就可以删除。
所以就模拟从大到小删数。
第一次 5 4 1 2 | 7 3
指标移动1次就可以删掉“7”
第二次 5 | 4 1 2 3
指标移动3次就可以删掉“5”
第三次 |4 1 2 3
指标不需要移动就可以删除“4”
......
然后就把这些移动的次数加起来就是答案~(≧▽≦)/~啦啦啦
把删掉的数的位置 置0 有数的位置 置1 然后树状数组维护一下就好了~
1 var a,c,tree:array[0..200500]of int64; 2 i,n,m,p:longint; 3 x,ans:int64; 4 5 procedure qs(l,r:longint); 6 var i,j:longint; 7 m,t:int64; 8 begin 9 i:=l; 10 j:=r; 11 m:=a[(l+r)>>1]; 12 repeat 13 while a[i]>m do inc(i); 14 while a[j]<m do dec(j); 15 if i<=j then 16 begin 17 t:=a[i];a[i]:=a[j];a[j]:=t; 18 t:=c[i];c[i]:=c[j];c[j]:=t; 19 inc(i); 20 dec(j); 21 end; 22 until i>j; 23 if l<j then qs(l,j); 24 if i<r then qs(i,r); 25 end; 26 function low(x:longint):longint; 27 begin 28 exit(x and -x); 29 end; 30 procedure adde(x,d:longint); 31 begin 32 while x<=p do 33 begin 34 inc(tree[x],d); 35 inc(x,low(x)); 36 end; 37 end; 38 function sum(x:longint):int64; 39 var s:int64; 40 begin 41 s:=0; 42 while x>0 do 43 begin 44 inc(s,tree[x]); 45 dec(x,low(x)); 46 end; 47 exit(s); 48 end; 49 begin 50 read(n,m); 51 p:=n+m; 52 for i:=n downto 1 do 53 begin 54 read(a[i]); 55 c[i]:=i; 56 adde(i,1); 57 end; 58 for i:=n+1 to p do 59 begin 60 read(a[i]); 61 c[i]:=i; 62 adde(i,1); 63 end; 64 qs(1,p); 65 if c[1]>n then x:=n+1 else x:=n; 66 ans:=0; 67 for i:=1 to p do 68 begin 69 adde(c[i],-1); 70 if c[i]>x then ans:=ans+sum(c[i])-sum(x-1) else 71 ans:=ans+sum(x)-sum(c[i]-1); 72 x:=c[i]; 73 end; 74 writeln(ans); 75 end.