1303: [CQOI2009]中位数图

Time Limit: 1 Sec  Memory Limit: 162 MB

Submit: 1383  Solved: 902

[][]

Description

给出1~n的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后，位于中间的数。

Input

第一行为两个正整数n和b ，第二行为1~n 的排列。

Output

输出一个整数，即中位数为b的连续子序列个数。

Sample Input

7 4

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 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
       
        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