luogu4422 [COCI2017-2018#1] Deda[线段树二分]
2024-10-06 18:49:22
这题我一年前的模拟赛考场还切过,现在就不会了。。好菜啊。
显然直接线段树拆成$\log n$个区间,然后每个区间在进行线段树二分即可。
UPD:复杂度分析。貌似是$O(n\log n)$的/yiw。每个区间线段树二分,左儿子min小于查询的x就走左儿子,右儿子min小于x就走右儿子,否则就不走,直到找到最早的一个区间,后面的区间直接返回不找力~。所以找出log个区间,只有一个区间进行二分,总的是两倍log,所以还是单log级别的。
这是一年前的code。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=+,INF=0x3f7f3f7f;
inline int _min(int a,int b){return a<b?a:b;}
inline int read(){
char c;int f=,x=;while(!isdigit(c=getchar()))if(c==)f=;
while(isdigit(c))x=(x<<)+(x<<)+(c^),c=getchar();return f?-x:x;
}
int minv[N<<];
char s[];
int n,q,x,k,ans,qr,ql;
#define l i<<1
#define r i<<1|1
void Update(int i,int L,int R){
if(L==R){minv[i]=k;return;}
int mid=L+R>>;x<=mid?Update(l,L,mid):Update(r,mid+,R);
minv[i]=_min(minv[l],minv[r]);
}//维护最小站点位置
int Find(int i,int L,int R){
if(minv[i]>k)return INF;
else if(L==R) return L;
int mid=L+R>>;return minv[l]<=k?Find(l,L,mid):Find(r,mid+,R);
}//这里就是如果ql,qr覆盖了当前区间就在这区间里找满足要求最小岁数
void Query(int i,int L,int R){
if(ql<=L&&qr>=R){ans=Find(i,L,R);return;}
int mid=L+R>>;
if(ql<=mid){Query(l,L,mid);if(ans!=INF)return;}//小细节,年龄小的已经找到就不用找右边了.
if(qr>mid)Query(r,mid+,R);
}
#undef l
#undef r
int main(){
qr=n=read(),q=read();memset(minv,INF,sizeof minv);//注意清零,想想为什么
while(q--){
scanf("%s",s);
if(s[]=='M')k=read(),x=read(),Update(,,n);
else k=read(),ql=read(),ans=INF,Query(,,n),printf("%d\n",ans==INF?-:ans);
}
return ;
}
还有单log做法,是hkk教的。。首先对于权值从小到大排序,把每种权值建一棵树,树的下标是序列下标,(显然这个是一个可持久化线段树,注意这样一个以权值建立线段树的方法在想不出的时候可以往这个上想想!),然后对于查询区间小于x的,直接在主席树上找1~x-1这些树上(实际是前缀和)最早的[L,R]有值处,这个的做法和复杂度分析也同上。
最新文章
- J2EE 项目读写分离
- 【转】Java Web 项目获取运行时路径 classpath
- 软件工程(C编码实践篇)总结
- 手把手教你用python抓网页数据
- [PCL]2 点云法向量计算NormalEstimation
- 教程-Delphi源代码--后延函数
- 【转】android官方侧滑菜单DrawerLayout详解
- 仅当使用了列的列表 并且 identity_insert 为 on 时 才能在表 中为标识列指定显式值
- POJ 1146:ID Codes
- Json解析要点
- Linux 添加到环境变量
- 推荐好用的css调试工具,两个
- OO第一单元小结
- Spring的IOC注解开发入门1
- Traffic Management Gym - 101875G
- docker安装openwrt镜像(不完美案例)
- React 表单refs
- CRM 2016 请求";System.Security.Permissions.FilelOPermission,mscorlib,Version=4.0.0.0,Culture=neutral,PublicKeyToken=b77a5c561934e089";类型的权限已失败.
- VS2010启动多个实例调试
- 百度地图出现UnsatisfiedLinkError: Native method not found: com.baidu...