BZOJ 3192

传送门

感谢Keyhvw 什么破字符串 同学指出的错误

如果存到两个数组里面移来移去的一定很麻烦,那么就可以想一想能不能存到一起

题目上写着说移动方式只能从一个顶端移动到另一个顶端,底端是没法直接移动的

那么就可以把两个顶端挨在一起存起来(第一摞正着第二摞倒着),底端扔在两头,中间加一个分界点,对于这个存在一起的数组而言,移动操作就成了移动分界点

然后就可以上树状数组了,统计每个元素左边有几个

将权值从大到小排序依次删(别忘了记录每个元素原来的位置)

两堆物品的分界点在每次移动后记得更新,靠这个更新答案

初始在两摞中间,不要累计进答案

ans记得开long long

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
program bzoj_3192;
type rec=record k,p:longint; end;
var b:array[0..100000]of longint;
a:array[1..100001]of rec;
n1,n2,n,now,i:longint;
ans:int64;
function c(x:longint):longint;
begin
exit(x and (-x));
end;
procedure plus(p,d:longint);
begin
while p<=n do
begin
inc(b[p],d);
inc(p,c(p));
end;
end;
procedure qsort(l,r:longint);
var i,j:longint;
mid,p:rec;
begin
i:=l;
j:=r;
mid:=a[(l+r)>>1];
repeat
while a[i].k>mid.k do inc(i);
while a[j].k<mid.k do dec(j);
if i<=j then
begin
p:=a[i];
a[i]:=a[j];
a[j]:=p;
inc(i);
dec(j);
end;
until i>j;
if i<r then qsort(i,r);
if l<j then qsort(l,j);
end;
function query(p:longint):longint;
begin
query:=0;
while p>0 do
begin
inc(query,b[p]);
dec(p,c(p));
end;
end;
function ask(l,r:longint):longint;
var p:longint;
begin
if l>r then
begin
p:=l;
l:=r;
r:=p;
end;
exit(query(r)-query(l-1)-1);
end;
begin
fillchar(b,sizeof(b),0);
readln(n1,n2);
n:=n1+n2+1;
for i:=n1 downto 1 do readln(a[i].k);
for i:=n1+2 to n do readln(a[i].k);
now:=n1+1;
for i:=1 to n do
begin
if i<>now then plus(i,1);
a[i].p:=i;
end;
qsort(1,n);
ans:=0;
for i:=1 to n-1 do
begin
inc(ans,ask(a[i].p,now));
plus(a[i].p,-1);
now:=a[i].p;
end;
writeln(ans);
end.