10.17T4 位置前后缀+map查询

2393 -- 【CQOI2009】中位数

Description

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

Input

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

Output

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

Sample Input

【输入1】

5 4

1 2 3 4 5

【输入2】

6 3

1 2 4 5 6 3

【输入3】

7 4

5 7 2 4 3 1 6

Sample Output

【输出1】

【输出2】

【输出3】

第三个样例解释：{4}, {7,2,4}, {5,7,2,4,3}和{5,7,2,4,3,1,6}。

Hint

在所有数里面，比m大的赋值1，比它小的赋值-1，然后找到这个m的位置，然后求出以它为最后一个元素的所有子段的和放进map里面维护

然后每次求出以这个元素为第一个元素的所有子段和，在map里面查找它的相反数个数加上就是答案，emmm算乱搞吧

code:

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<map>
 4 using namespace std;
 5 map<int,int>leftt,right;
 6 int a[100005];
 7 int main(){
 8     int n,m;
 9     cin>>n>>m;
10     int pos;
11     for(int i=1;i<=n;i++){
12         cin>>a[i];
13         if(a[i]==m){
14             pos=i;
15             a[i]=0;
16             continue;
17         }
18         a[i]=a[i]>m?1:-1;
19     }
20     int sum=0;
21     for(int i=pos;i>=1;i--){
22         sum+=a[i];
23         leftt[sum]++;
24     }
25     sum=0;
26     int ans=0;
27     for(int i=pos;i<=n;i++){
28         sum+=a[i];
29         ans+=leftt[-sum];    
30     }
31     cout<<ans;
32     return 0;
33 }

over