一开始看错题意了!!没注意到整个数列是1~n的一个排列!
很水的一道题,找到b在数列中的位置设为point,比b大的赋值为-1,比b小的赋值为1;
然后求出sum[i,point]的值出现了几次记为lfre[sum[i,point]]++; ans += lfre[sum[i,point]]*rfre[-sum[i,point]];
由于c++数组不能是负数,所以稍微处理一下
1 /* 2 ID:WULALA 3 PROB:bzoj1303 4 LANG:C++ 5 */ 6 #include7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #define N 10000814 #define M15 #define mod16 #define mid(l,r) ((l+r) >> 1)17 #define INF 0x7ffffff18 using namespace std;19 20 int b,point,n,num[N],sum[N],lfre[2 * N],rfre[2 * N],ans;21 22 int main()23 {24 scanf("%d%d",&n,&b);25 for (int i = 1;i <= n;i++)26 {27 scanf("%d",&num[i]);28 if (num[i] < b) num[i] = -1;29 else if (num[i] > b) num[i] = 1;30 else if (num[i] == b) point = i,num[i] = 0;31 }32 lfre[n] = 1; rfre[n] = 1;33 for (int i = point - 1;i >= 1;i--) sum[i] = sum[i+1] + num[i],lfre[sum[i]+n]++;34 for (int i = point + 1;i <= n;i++) sum[i] = sum[i-1] + num[i],rfre[sum[i]+n]++;35 for (int i = 0;i <= 2 * n - 1;i++) ans += lfre[i] * rfre[2*n-i];36 printf("%d\n",ans);37 return 0; 38 }