题目描述
给出1-n的一个排列,统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后,位于中间的数。
题解:
由于题目所给的是一个排列,即1~n每个数值出现一次,那么一个连续的子序列要想包含b只有3中情况,假设b在pos
- i ~ pos
- pos ~ j
- i ~ pos ~ j
并且由于中位数只可以 为b,那么所有数也可以分为3类,>b <b ==b,我们把 >b 看成1 ,< b 看成-1.
所以对于情况 1 2 只要从pos开始分别向前向后累加,和为0时即为一种有效情况。
对于情况 3 也只需要先统计一下,左边所有和能出现的情况,然后在扫描右边的时候假设当前和为 s ,我们只需要找到-s在左边出现了多少次就可以了
由于在统计过程中会出现和 小于 0 的情况,我们可以把所有和全加n,或者用map解决这个问题
代码;
#include<bits/stdc++.h> #define ls rt<<1 #define rs rt<<1|1 #define fi first #define se second #define pb push_back #define DEBUG(x) std::cerr << #x << '=' << x << std::endl using namespace std; typedef long long ll; typedef vector<int> VI; typedef pair<int,int> pii; typedef pair<ll,ll> pll; const ll inf = 0x3f3f3f3f3f3f3f3f; const int mod = 998244353; const int maxn = 2e6 + 4; const int N = 5e3 + 5; const double eps = 1e-6; const double pi = acos(-1); ll qpow(ll x,ll y){ll ans=1;x%=mod;while(y){ if(y&1) ans=ans*x%mod; x=x*x%mod; y>>=1;}return ans;} int n,b,a[maxn],pos,c[maxn],s,ans; int main(){ //freopen("a.in","r",stdin); scanf("%d%d",&n,&b); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); if(a[i]==b) pos=i; else if(a[i]>b) a[i]=1; else if(a[i]<b) a[i]=-1; } for(int i=pos-1;i>=1;i--){ s+=a[i]; c[s+n]++; if(!s) ans++; } s^=s; for(int i=pos+1;i<=n;i++){ s+=a[i]; ans+=c[n-s]; if(!s) ans++; } printf("%d\n",ans+1); } /* */