首页 > 代码库 > bzoj1303 [CQOI2009]中位数图
bzoj1303 [CQOI2009]中位数图
Description
给出1~n的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后，位于中间的数。
Input
第一行为两个正整数n和b ，第二行为1~n 的排列。
Output
输出一个整数，即中位数为b的连续子序列个数。
Sample Input
7 4
5 7 2 4 3 1 6
5 7 2 4 3 1 6
Sample Output
4
HINT
第三个样例解释：{4}, {7,2,4}, {5,7,2,4,3}和{5,7,2,4,3,1,6}
N<=100000
因为是1到n的全排列，所以m有且只有出现一次。首先先把m的位置抓出来
考虑从m的位置开始往左统计区间中m在中位数左边（右边）k位的区间的个数，再往右统计m在中位数右边（左边）k位的区间的个数，那么他们对答案的贡献就是乘起来的数
比如样例中从4开始往左有2个区间{4}、{7、2、4}刚好m是中位数，右边只有一个区间{4}刚好m是中位数，他们对答案的贡献是2*1=2
往左有1个区间{5、7、2、4}刚好有2个比m大1个比m小，往右有2个区间{4、3}、{4、3、1、6}刚好有1个比m大2个比m小，所以他们对答案的贡献是1*2=2
为区分大小时避免负数直接从100w开始多加少减
#include<cstdio>#include<iostream>#include<cstring>#include<cstdlib>#include<algorithm>#include<cmath>#include<queue>#include<deque>#include<set>#include<map>#include<ctime>#define LL long long#define inf 0x7ffffff#define pa pair<int,int>#define pi 3.1415926535897932384626433832795028841971using namespace std;inline LL read(){ LL x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f;}int n,m,pos,now;int a[1000010];int f[2000010];int g[2000010];LL ans;int main(){ n=read();m=read(); for (int i=1;i<=n;i++) { a[i]=read(); if (a[i]==m)pos=i; } now=1000000; for (int i=pos;i<=n;i++) { if (a[i]<m)now--; if (a[i]>m)now++; f[now]++; } now=1000000; for (int i=pos;i>=1;i--) { if(a[i]<m)now--; if(a[i]>m)now++; g[now]++; } for (int i=1;i<2000000;i++) { ans+=(LL)f[i]*g[2000000-i]; } printf("%lld\n",ans);}
bzoj1303 [CQOI2009]中位数图
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。