BZOJ

BZOJ 3289

传送门

莫队尼玛26s才过

因为这题没给数据范围，树状数组不知道开多大，所以先离散化一下 P党程序里写了俩快排真长…TAT

首先还是分块+排序，节省转移时的消耗，然后转移时要注意这些：

  • 修改区间左端点就查询比左端点的数小的，右端点就查询比右端点的数大的（逆序对判断条件：$i<j且a[i]>a[j]$）

  • 当前区间向询问的区间转移时要注意for循环的顺序，一定是当前区间端点向询问区间端点逐个转移，否则有的情况会考虑不到（例如样例这样）

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
program bzoj_3289;
type qu=record l,r,id,ans:longint; end;
var bit,pos,bl,a,s:array[1..50000]of longint;
    ask:array[1..50000]of qu;
    n,q,i,block,tot,cnt:longint;
 
function c(x:longint):longint;
begin
  exit(x and -x);
end;
 
function sml(a,b:qu):boolean;
begin
  if bl[a.l]=bl[b.l] then exit(a.r<b.r);
  exit(a.l<b.l);
end;
 
procedure qsort(l,r:longint);
var i,j:longint;
    mid,p:qu;
begin
  i:=l;
  j:=r;
  mid:=ask[(l+r)>>1];
  repeat
    while sml(ask[i],mid) do inc(i);
    while sml(mid,ask[j]) do dec(j);
    if i<=j then
    begin
      p:=ask[i];
      ask[i]:=ask[j];
      ask[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;
 
procedure qsort_(l,r:longint);
var i,j,mid,p:longint;
begin
  i:=l;
  j:=r;
  mid:=a[(l+r)>>1];
  repeat
    while a[i]<mid do inc(i);
    while a[j]>mid do dec(j);
    if i<=j then
    begin
      p:=a[i];
      a[i]:=a[j];
      a[j]:=p;
      p:=pos[i];
      pos[i]:=pos[j];
      pos[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,bit[p]);
    dec(p,c(p));
  end;
end;
 
procedure modify(p,d:longint);
begin
  while p<=cnt do
  begin
    inc(bit[p],d);
    inc(p,c(p));
  end;
end;
 
procedure solve;
var i,j,l,r:longint;
begin
  fillchar(bit,sizeof(bit),0);
  l:=1;
  r:=0;
  tot:=0;
  for i:=1 to q do
  begin
    for j:=l to ask[i].l-1 do
    begin
      dec(tot,query(s[j]-1));
      modify(s[j],-1);
    end;
    for j:=l-1 downto ask[i].l do
    begin
      inc(tot,query(s[j]-1));
      modify(s[j],1);
    end;
    for j:=r+1 to ask[i].r do
    begin
      inc(tot,query(cnt)-query(s[j]));
      modify(s[j],1);
    end;
    for j:=r downto ask[i].r+1 do
    begin
      dec(tot,query(cnt)-query(s[j]));
      modify(s[j],-1);
    end;
    l:=ask[i].l;
    r:=ask[i].r;
    ask[i].ans:=tot;
  end;
end;
 
begin
  readln(n);
  block:=trunc(sqrt(n));
  for i:=1 to n do bl[i]:=(i-1) div block+1;
  for i:=1 to n do read(a[i]);
  for i:=1 to n do pos[i]:=i;
  qsort_(1,n);
  cnt:=0;
  for i:=1 to n do
  begin
    if (i=1)or(a[i]<>a[i-1]) then inc(cnt);
    s[pos[i]]:=cnt;
  end;
  readln(q);
  for i:=1 to q do with ask[i] do
  begin
    readln(l,r);
    id:=i;
  end;
  qsort(1,q);
  for i:=1 to q do pos[ask[i].id]:=i;
  solve;
  for i:=1 to q do writeln(ask[pos[i]].ans);
end.