Time Limit: 1 Sec Memory Limit: 162 MB
Submit: 1383 Solved: 902
给出1~n的一个排列,统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后,位于中间的数。
第一行为两个正整数n和b ,第二行为1~n 的排列。
输出一个整数,即中位数为b的连续子序列个数。
7 4 5 7 2 4 3 1 6
4
第三个样例解释:{4}, {7,2,4}, {5,7,2,4,3}和{5,7,2,4,3,1,6} N<=100000
题解:还是和前缀和有关——将大于中位数的值设为1,小于的设为-1,等于的设为0,则可以制造一个前缀和数组——在数组中只要某两个位置(注意:范围为0-N)中值相等,则说明存在一段和为0的段,只需要排个序统计下——特别注意:一定要考虑这个段的长度究竟是奇数还是偶数,因为假如是奇数的话,则一定是合法的子序列;假如是偶数的话,则一定不是合法的子序列——也就是说两者存在明确的必然联系,所以只有长度为奇数的才计入总数,千万注意(HansBug:网上的题解貌似都没提到这个额 phile:这还用说? HansBug:T T)
1 type arr=array[-200000..200000] of longint;
2 var
3 i,j,k,l,m,n:longint;
4 a,b,c,d:arr;
5 function xxx(x:longint):longint;
6 begin
7 exit(x*(x-1) div 2);
8 end;
9 procedure swap(var x,y:longint);
10 var z:longint;
11 begin
12 z:=x;x:=y;y:=z;
13 end;
14 procedure sort(l,r:longint;var a,b:arr);
15 var i,j,x,y:longint;
16 begin
17 i:=l;j:=r;x:=b[(l+r) div 2];
18 repeat
19 while b[i]<x do inc(i);
20 while b[j]>x do dec(j);
21 if i<=j then
22 begin
23 swap(b[i],b[j]);
24 swap(a[i],a[j]);
25 inc(i);dec(j);
26 end;
27 until i>j;
28 if l<j then sort(l,j,a,b);
29 if i<r then sort(i,r,a,b);
30 end;
31 begin
32 readln(n,m);
33 a[0]:=0;b[0]:=0;
34 for i:=1 to n do
35 begin
36 read(a[i]);
37 if a[i]>m then
38 a[i]:=1
39 else if a[i]=m then a[i]:=0 else a[i]:=-1;
40 b[i]:=b[i-1]+a[i];
41 end;
42 for i:=n downto 1 do b[i+1]:=b[i];
43 for i:=n+1 downto 1 do a[i]:=i-1;
44 b[1]:=0;
45 sort(1,n+1,a,b);
46 for i:=1 to n+1 do a[i]:=a[i] mod 2;
47 b[0]:=-maxlongint;
48 j:=0;
49 b[n+2]:=maxlongint;l:=0;
50 for i:=1 to n+2 do
51 if b[i]<>b[j] then
52 begin
53 sort(j,i-1,b,a);
54 j:=i;
55 end;
56 j:=0;
57 fillchar(c,sizeof(c),0);
58 fillchar(d,sizeof(d),0);
59 for i:=1 to n+2 do
60 begin
61 if not((b[i]=b[j]) and (a[i]=a[j])) then
62 begin
63 if j<>0 then if a[j]=0 then c[b[j]]:=c[b[j]]+i-j else d[b[j]]:=d[b[j]]+i-j;
64 j:=i;
65 end;
66 end;
67 for i:=-200000 to 200000 do l:=l+c[i]*d[i];
68 writeln(l);
69 end.
70