思路：统计当前数左边比它小|大 i个人，相应右边就应该是比它大|小i个人
l数组表示左边i个人的方案
r表示右边i个人的方案
数组下标不可能是负数所以要加n
1 //#pragma comment(linker, "/STACK:167772160")//手动扩栈~~~~hdu 用c++交 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <iostream> 6 #include <queue> 7 #include <stack> 8 #include <cmath> 9 #include <set> 10 #include <algorithm> 11 #include <vector> 12 // #include<malloc.h> 13 using namespace std; 14 #define clc(a,b) memset(a,b,sizeof(a)) 15 #define LL long long 16 const int inf = 0x3f3f3f3f; 17 const double eps = 1e-5; 18 const double pi = acos(-1); 19 const LL MOD = 1e9+7; 20 // const LL p = 1e9+7; 21 // inline int r(){ 22 // int x=0,f=1;char ch=getchar(); 23 // while(ch>'9'||ch<'0'){if(ch=='-') f=-1;ch=getchar();} 24 // while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 25 // return x*f; 26 // } 27 28 int numm[8005],sum[8005],l[20001],r[20001]; 29 int n,point,ans,b; 30 int a[8002]; 31 32 int main() { 33 while(~scanf("%d",&n)) { 34 for(int i=1; i<=n; i++) scanf("%d",&a[i]); 35 36 for(int j=1; j<=n; j++) { 37 b=a[j]; 38 for(int i=1;i<=n;i++) numm[i]=a[i]; 39 // for(int i=0;i<=n;i++) l[i]=0; 40 // for(int i=0;i<=n;i++) r[i]=0; 41 // for(int i=0;i<=n;i++) sum[i]=0; 42 clc(l,0); 43 clc(r,0); 44 clc(sum,0); 45 ans=0; 46 for(int i=1; i<=n; i++) { 47 if(numm[i]>b) numm[i]=1; 48 else if(numm[i]==b) { 49 numm[i]=0; 50 point=i; 51 } else numm[i]=-1; 52 } 53 l[n]=1; 54 r[n]=1; 55 for(int i=point-1; i>=1; i--) { 56 sum[i]=sum[i+1]+numm[i]; 57 l[sum[i]+n]++; 58 } 59 for(int i=point+1; i<=n; i++) { 60 sum[i]=sum[i-1]+numm[i]; 61 r[sum[i]+n]++; 62 } 63 for(int i=0; i<=2*n-1; i++) ans+=l[i]*r[2*n-i]; 64 65 if(j==1) 66 printf("%d",ans); 67 else 68 printf(" %d",ans); 69 } 70 printf(" "); 71 } 72 return 0; 73 }