首页 > 代码库 > 1303: [CQOI2009]中位数图
1303: [CQOI2009]中位数图
1303: [CQOI2009]中位数图
Time Limit: 1 Sec Memory Limit: 162 MBSubmit: 1383 Solved: 902
[Submit][Status]
Description
给出1~n的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后，位于中间的数。
Input
第一行为两个正整数n和b ，第二行为1~n 的排列。
Output
输出一个整数，即中位数为b的连续子序列个数。
Sample Input
7 4
5 7 2 4 3 1 6
5 7 2 4 3 1 6
Sample Output
4
HINT
第三个样例解释：{4}, {7,2,4}, {5,7,2,4,3}和{5,7,2,4,3,1,6}
N<=100000
Source
题解：还是和前缀和有关——将大于中位数的值设为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 begin12 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 begin17 i:=l;j:=r;x:=b[(l+r) div 2];18 repeat19 while b[i]<x do inc(i);20 while b[j]>x do dec(j);21 if i<=j then22 begin23 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 begin32 readln(n,m);33 a[0]:=0;b[0]:=0;34 for i:=1 to n do35 begin36 read(a[i]);37 if a[i]>m then38 a[i]:=139 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 do51 if b[i]<>b[j] then52 begin53 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 do60 begin61 if not((b[i]=b[j]) and (a[i]=a[j])) then62 begin63 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
1303: [CQOI2009]中位数图
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。