1303. [CQOI2009]中位数【前缀和+乱搞】
2024-10-16 12:56:11
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,大于的设为1
显然若区间[l,r]包含中位数且值和为0,那么就是满足条件的
(为什么能保证是奇数长?因为偶数不可能加出和为0的……)
若要判断[l,r]区间,需要sum[r]-sum[l-1]=0,即sum[r]=sum[l-1]
我们将[0,pos-1]的sum值放到一个桶里,然后枚举右端点统计答案即可。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<map>
#define N (100000+100)
using namespace std; int n,m,t,a[N],mid,sum[N];
long long ans;
map<int,int>Keg; int main()
{
scanf("%d%d",&n,&m);
for (int i=; i<=n; ++i)
{
scanf("%d",&a[i]);
if (a[i]==m) t=i,a[i]=;
else a[i]=(a[i]<m)?-:;
sum[i]=sum[i-]+a[i];
if (!t) Keg[sum[i]]++;
}
Keg[]++;//注意这里
for (int i=t; i<=n; ++i)
ans+=Keg[sum[i]];
printf("%lld",ans);
}
最新文章
- [转]oracle设计数据库应选择正确的数据类型
- LightSpeed 之Sql和存储过程的使用
- oracle的用户
- Codeforces Round #376 (Div. 2) F. Video Cards 数学,前缀和
- leetcode 239 Sliding Window Maximum
- WebApi(一)-实现跨域返回格式支持json
- How can I create an Asynchronous function in Javascript?
- Java ArrayList小程序理解
- WPF 文本滚动效果 渐变效果
- 如何使用 Bootstrap 搭建更合理的 HTML 结构
- Demonstration of DB Query Analyzer 6.03 Installation and Running on Microsoft Windows 8
- SLAM+语音机器人DIY系列:(三)感知与大脑——6.做一个能走路和对话的机器人
- Android内嵌PDF预览
- HDU 5178 pairs【二分】||【尺取】
- 虚拟机oom
- webpack之proxyTable配置
- web前端优化
- 使用git初始化本地仓库并提交到远程分支
- TOYS(叉积)
- 小tip: 某简单的字符重叠与图形生成----张鑫旭