AC日记——[POI2014]KUR-Couriers 洛谷 P3567
2024-10-18 21:23:38
思路:
卡空间,sb题;
代码:
#include <bits/stdc++.h>
using namespace std;
#define maxn 500005
#define maxn_ maxn*19
int n,m,lc[maxn_],rc[maxn_],dis[maxn_],ans;
int ai[maxn],bi[maxn],root[maxn],tot,size;
inline void in(int &now)
{
char Cget=getchar();now=;
while(Cget>''||Cget<'') Cget=getchar();
while(Cget>=''&&Cget<='')
{
now=now*+Cget-'';
Cget=getchar();
}
}
void build(int &now,int l,int r)
{
now=++tot;
if(l==r) return;
int mid=l+r>>;
build(lc[now],l,mid);
build(rc[now],mid+,r);
}
inline void add(int &now,int pre,int l,int r,int to)
{
now=++tot,dis[now]=dis[pre]+;
if(l==r) return;
int mid=l+r>>;
if(to<=mid) add(lc[now],lc[pre],l,mid,to),rc[now]=rc[pre];
else add(rc[now],rc[pre],mid+,r,to),lc[now]=lc[pre];
}
inline void query(int now,int pre,int l,int r,int k)
{
if(l==r) {ans=l;return;};
int mid=l+r>>,di=dis[lc[now]]-dis[lc[pre]];
if(di>=k) {query(lc[now],lc[pre],l,mid,k);return;}
di=dis[rc[now]]-dis[rc[pre]];
if(di>=k) {query(rc[now],rc[pre],mid+,r,k);return;}
ans=;return;
}
int main()
{
in(n),in(m);int l,r,to;
for(int i=;i<=n;i++) in(ai[i]),bi[i]=ai[i];
sort(bi+,bi+n+),size=unique(bi+,bi+n+)-bi-;
build(root[],,size);
for(int i=;i<=n;i++)
{
to=lower_bound(bi+,bi+size+,ai[i])-bi;
add(root[i],root[i-],,size,to);
}
while(m--)
{
in(l),in(r);
query(root[r],root[l-],,size,(r-l+>>)+);
printf("%d\n",bi[ans]);
}
return ;
}
最新文章
- JVM学习笔记(二)------Java代码编译和执行的整个过程【转】
- 从零开始学JAVA(02)-用Eclipse写hello World
- centos卸载自带的apache(httpd)
- Azure IoT 技术研究系列2-起步示例之设备注册到Azure IoT Hub
- 利用JavaScript数组动态写入HTML数据节点
- easyui+ztree 后台管理系统模板
- 流API--初体验
- [Jenkins]IOS构建机配置记录
- Crash工具实战-变量解析【转】
- office 安装
- Java的三种代理模式(Spring动态代理对象)
- Unity3D中播放视频的方法
- ios 百度地图使用
- 洛谷 P1158 导弹拦截(不是那个DP) 解题报告
- Ubuntu14.04配置jdk1.8.0_25,可切换版本
- 【290】Python 函数
- GIS的核心价值——服务
- cf1072D. Minimum path(BFS)
- python系列十五:Python3 错误和异常
- 100211D Police Cities