BZOJ

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.