AC日记——中庸之道 codevs 2021
2024-08-30 00:22:06
题目描述 Description
给定一个长度为N的序列,有Q次询问,每次询问区间[L,R]的中位数。
数据保证序列中任意两个数不相同,且询问的所有区间长度为奇数。
输入描述 Input Description
第一行为N,Q。
第二行N个数表示序列。
接下来Q行,每行为L,R,表示一次询问。
输出描述 Output Description
输出Q行,对应每次询问的中位数。
样例输入 Sample Input
5 3
1 4 8 16 2
1 5
3 5
3 3
样例输出 Sample Output
4
8
8
数据范围及提示 Data Size & Hint
40%的数据,N,Q≤100;
70%的数据,N≤100;
100%的数据,N≤1000,Q≤100000,序列中的元素为1到10^9之间的整数。
思路:
主席树裸题;
来,上代码:
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm> using namespace std; struct TreeNodeType {
int l,r,dis; TreeNodeType *left,*right;
};
struct TreeNodeType *root[]; int n,q,if_z,num[],num_[],size; char Cget; inline void read_int(int &now)
{
now=,if_z=,Cget=getchar();
while(Cget>''||Cget<'')
{
if(Cget=='-') if_z=-;
Cget=getchar();
}
while(Cget>=''&&Cget<='')
{
now=now*+Cget-'';
Cget=getchar();
}
now*=if_z;
} void tree_build(TreeNodeType *&now,int l,int r)
{
now=new TreeNodeType;
now->l=l,now->r=r,now->dis=;
if(l==r) return ;
int mid=(l+r)>>;
tree_build(now->left,l,mid);
tree_build(now->right,mid+,r);
} void tree_change(TreeNodeType *&pre,int to,TreeNodeType *&now)
{
now=new TreeNodeType;
now->l=pre->l,now->r=pre->r,now->dis=pre->dis+;
if(now->l==now->r) return ;
int mid=(now->l+now->r)>>;
if(to<=mid)
{
now->right=pre->right;
tree_change(pre->left,to,now->left);
}
else
{
now->left=pre->left;
tree_change(pre->right,to,now->right);
}
} int tree_query(TreeNodeType *pre,TreeNodeType *now,int to)
{
if(now->l==now->r) return now->l;
int dis=now->left->dis-pre->left->dis;
if(to<=dis) return tree_query(pre->left,now->left,to);
else return tree_query(pre->right,now->right,to-dis);
} int main()
{
read_int(n),read_int(q);
for(int i=;i<=n;i++)
{
read_int(num[i]);
num_[i]=num[i];
}
sort(num+,num+n+);
size=unique(num+,num+n+)-num-;
tree_build(root[],,size);
for(int i=;i<=n;i++)
{
num_[i]=lower_bound(num+,num+size+,num_[i])-num;
tree_change(root[i-],num_[i],root[i]);
}
int l,r;
for(int i=;i<=q;i++)
{
read_int(l),read_int(r);
int mid=((r-l+)>>)+;
printf("%d\n",num[tree_query(root[l-],root[r],mid)]);
}
return ;
}
最新文章
- Android软件开发之ListView 详解【转】
- LinQ递归查询
- 当安装好oracle后关机后, 电脑重启发现登录不了解决
- 读取txt文件加DevExpress之进度条progressBarControl
- 【HTTP权威指南】第三章-HTTP报文
- Unity相对于Cocos2d-x的比较
- Again Stone Game
- mac下通过mdfind命令搜索文件
- windows server 2008 R2服务器安装IIS并添加网站
- call是什么?一次说个明白
- Java JWT: JSON Web Token
- 简述Java变量和强制转换类型
- Hadoop生态圈-Ranger数据安全管理框架
- (转)搭建Maven私服(使用Nexus)
- 删除GitHub或者GitLab 上的文件夹,git rm -r --ceched 文件夹名 ,提交commit,git push
- Lua脚本语法说明(转):
- Java异常体系和异常处理机制
- 21.拉取&;删除远程分支
- 解决可以Ping通ip地址,但Ping不通域名的思路
- eclipse for php 开发环境配置