洛谷 P4747 [CERC2017]Intrinsic Interval 线段树维护连续区间
2024-08-30 01:38:34
题目描述
分析
考虑对于 \([l,r]\),如何求出包住它的长度最短的好区间
做法就是用一个指针从 \(r\) 向右扫,每次查询以当前指针为右端点的最短的能包住 \([l,r]\) 的好区间
第一个查询到的就是想要的区间
一定不会存在一个与这个区间交叉的区间更优的情况
因为这种情况两个区间交叉的部分一定会在之前被查询到
这样的话就可以把所有的询问离线下来,按照右端点从小到大排序依次处理
只需要快速地查询长度最短的好区间即可
这可以用线段树去维护
我们把线段树的节点定义为以某个点为左端点,以扫到的点为右端点的区间中连续区间的个数
线段树要维护的信息就是连续区间个数的最小值以及区间加和操作中的 \(lazy\) 标记
每次从右边新加入一个点 \(i\) 时,我们把区间 \([1,i]\) 整体加 \(1\)
代表此时又多了一个不连续的区间
此时我们去找 \(a[i]+1\) 和 \(a[i]-1\) 的位置,如果它们的位置在 \(i\) 的左边,我们就把 \([1,wz[a[i]-1]]\) 或者 \([1,wz[a[i]+1]]\) 整体减一,代表包含 \(a[i]+1\) 或者 \(a[i]-1\) 的区间可以与 \(a[i]\) 合并形成一个大区间
如果一个区间是合法的,那么连续区间个数就是一,线段树上记录的最小值就是一
在线段树上二分查找即可
代码
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#define rg register
inline int read(){
rg int x=0,fh=1;
rg char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') fh=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*fh;
}
const int maxn=1e5+5;
struct trr{
int l,r,mmin,laz;
}tr[maxn<<2];
void push_up(rg int da){
tr[da].mmin=std::min(tr[da<<1].mmin,tr[da<<1|1].mmin);
}
void push_down(rg int da){
if(tr[da].laz){
tr[da<<1].laz+=tr[da].laz;
tr[da<<1|1].laz+=tr[da].laz;
tr[da<<1].mmin+=tr[da].laz;
tr[da<<1|1].mmin+=tr[da].laz;
tr[da].laz=0;
}
}
void build(rg int da,rg int l,rg int r){
tr[da].l=l,tr[da].r=r;
if(l==r) return;
rg int mids=(l+r)>>1;
build(da<<1,l,mids),build(da<<1|1,mids+1,r);
}
void xg(rg int da,rg int l,rg int r,rg int val){
if(tr[da].l>=l && tr[da].r<=r){
tr[da].laz+=val,tr[da].mmin+=val;
return;
}
push_down(da);
rg int mids=(tr[da].l+tr[da].r)>>1;
if(l<=mids) xg(da<<1,l,r,val);
if(r>mids) xg(da<<1|1,l,r,val);
push_up(da);
}
int cx(rg int da,rg int l,rg int r){
if(tr[da].l!=tr[da].r) push_down(da);
if(tr[da].l>=l && tr[da].r<=r){
if(tr[da].mmin==1){
if(tr[da].l==tr[da].r) return tr[da].l;
else if(tr[da<<1|1].mmin==1) return cx(da<<1|1,l,r);
else return cx(da<<1,l,r);
} else {
return -1;
}
}
rg int mids=(tr[da].l+tr[da].r)>>1,tmp1=-1,tmp2=-1;
if(l<=mids) tmp1=cx(da<<1,l,r);
if(r>mids) tmp2=cx(da<<1|1,l,r);
if(tmp2!=-1) return tmp2;
else return tmp1;
}
int n,a[maxn],wz[maxn],ansl[maxn],ansr[maxn],m;
struct jie{
int l,r,id;
}b[maxn];
bool cmp(rg jie aa,rg jie bb){
return aa.r<bb.r;
}
struct asd{
int l,id;
asd(){}
asd(rg int aa,rg int bb){
l=aa,id=bb;
}
friend bool operator <(const asd& A,const asd& B){
if(A.l==B.l) return A.id<B.id;
return A.l>B.l;
}
};
std::set<asd> s;
int main(){
n=read();
for(rg int i=1;i<=n;i++) a[i]=read();
for(rg int i=1;i<=n;i++) wz[a[i]]=i;
m=read();
for(rg int i=1;i<=m;i++){
b[i].l=read(),b[i].r=read(),b[i].id=i;
}
std::sort(b+1,b+m+1,cmp);
build(1,1,n);
rg int now=1;
for(rg int i=1;i<=n;i++){
xg(1,1,i,1);
if(a[i]>1 && wz[a[i]-1]<i) xg(1,1,wz[a[i]-1],-1);
if(a[i]<n && wz[a[i]+1]<i) xg(1,1,wz[a[i]+1],-1);
while(now<=m && b[now].r==i){
s.insert(asd(b[now].l,b[now].id));
now++;
}
while(!s.empty()){
rg int tmp1=s.begin()->l,tmp2=s.begin()->id,tmp3;
tmp3=cx(1,1,tmp1);
if(tmp3==-1) break;
s.erase(s.begin());
ansl[tmp2]=tmp3,ansr[tmp2]=i;
}
}
for(rg int i=1;i<=m;i++) printf("%d %d\n",ansl[i],ansr[i]);
return 0;
}
最新文章
- heart beat/心跳包
- Log4J日志管理类使用详解 (转)
- UOJ 151 斗地主“加强”版
- DualPivotQuicksort 排序算法解析
- 【转】android 开发 命名规范
- I/O多路复用之select
- C# DataTable几个常用的查询表达式【转】
- PySide——Python图形化界面
- ORACLE:plsql优化
- stl_algorithm算法之排序算法
- Document 对象
- re模块的结果小练习题
- Sql Server——约束
- Opencv出现“_pFirstBlock == pHead”错误的解决方法
- LeetCode算法题-Search in a Binary Search Tree(Java实现)
- 关于config文件中AppSettings和ConnectionStrings的用法跟区别(转)
- java中之内存溢出说明
- OpenStack上搭建Q版的公共环境准备(step1)
- Windows平台的rop exp编写
- Android Studio体验(二)--创建项目和Genymotion试用
热门文章
- HDU4622 Reincarnation【SAM】
- zjnu1716 NEKAMELEONI (线段树)
- Codeforces Round #540 (Div. 3) B. Tanya and Candies (后缀和)
- cmd控制台Windows服务相关
- VS Code 搭建合适的 markdown 文档编写环境
- 【应急响应】Windows应急响应入门手册
- 安装jdk并配置环境变量
- CODE_TEST-- gtest
- Gitlab日常维护(三)之Gitlab的备份、迁移、升级
- iTerm2终端工具在Mac OS上使用详解