记录编号 |
205192 |
评测结果 |
AAAAAAAAAA |
题目名称 |
学数数 |
最终得分 |
100 |
用户昵称 |
slongle |
是否通过 |
通过 |
代码语言 |
Pascal |
运行时间 |
1.324 s |
提交时间 |
2015-11-04 21:31:59 |
内存使用 |
4.36 MiB |
显示代码纯文本
const
maxn=100050;
var
t,l,r,x,z:array[0..maxn]of longint;
sum,y,ans:array[0..maxn]of int64;
i,j,k:longint;
n,q,len,tt,ll,rr,mid,pp:longint;
ch:char;
procedure sort(l,r:longint);
var i,j,a,b:longint; c:int64;
begin
i:=l; j:=r; a:=x[(l+r) div 2];
repeat
while x[i]<a do inc(i);
while a<x[j] do dec(j);
if not(i>j) then
begin
b:=x[i]; x[i]:=x[j]; x[j]:=b;
c:=y[i]; y[i]:=y[j]; y[j]:=c;
inc(i); dec(j);
end;
until i>j;
if l<j then sort(l,j);
if i<r then sort(i,r);
end;
begin
assign(input,'jxthree.in'); assign(output,'jxthree.out'); reset(input); rewrite(output);
readln(n,q);
for i:=1 to n do
read(x[i]);
readln;
t[1]:=1; l[1]:=1; len:=1; t[0]:=0; x[0]:=maxlongint;
for i:=2 to n do
begin
tt:=0;
for j:=len downto 0 do
if x[i]<x[t[j]]
then begin l[i]:=i-t[j]; tt:=j; break; end
else r[t[j]]:=i-t[j];
len:=tt+1; t[len]:=i;
end;
for i:=1 to len do
r[t[i]]:=n+1-t[i];
for i:=1 to n do
y[i]:=int64(l[i])*int64(r[i]);
sort(1,n); len:=0; x[0]:=-1;
for i:=1 to n do
if x[i]<>x[i-1] then begin inc(len); z[len]:=x[i]; end;
tt:=0;
for i:=1 to n do
begin
if x[i]<>x[i-1] then inc(tt);
inc(ans[tt],y[i]);
end;
sum[0]:=0;
for i:=1 to n do
sum[i]:=sum[i-1]+ans[i];
{for i:=1 to len do
writeln(z[i],' ',ans[i]);}
for i:=1 to q do
begin
readln(ch,k); pp:=0;
if k>z[len] then begin
case ch of
'<':writeln(sum[len]);
'=':writeln(0);
'>':writeln(0);
end;
continue;
end;
ll:=1; rr:=len; j:=0;
while ll<=rr do
begin
mid:=(ll+rr)>>1;
if z[mid]=k then begin
case ch of
'<':writeln(sum[mid-1]);
'=':writeln(ans[mid]);
'>':writeln(sum[len]-sum[mid]);
end;
j:=1; break;
end;
if z[mid]<k
then ll:=mid
else rr:=mid;
inc(pp); if pp=20 then break;
end;
if j=1 then continue;
if (z[ll]=k)or(z[rr]=k) then begin
if z[ll]=k then mid:=ll;
if z[rr]=k then mid:=rr;
case ch of
'<':writeln(sum[mid-1]);
'=':writeln(ans[mid]);
'>':writeln(sum[len]-sum[mid]);
end;
continue;
end;
if k<z[ll]
then dec(ll)
else if k>z[rr] then inc(ll);
case ch of
'<':writeln(sum[ll]);
'=':writeln(0);
'>':writeln(sum[len]-sum[ll]);
end;
end;
close(input); close(output);
end.