第三个样例解释：{4}, {7,2,4}, {5,7,2,4,3}和{5,7,2,4,3,1,6}
N<=100000
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
原文：http://www.cnblogs.com/HansBug/p/4172994.html