小a的排列（线段树维护）

网友投稿 277 2022-08-30

小a的排列（线段树维护）

题目描述

小a有一个长度为nn的排列。定义一段区间是"萌"的，当且仅当把区间中各个数排序后相邻元素的差为11 现在他想知道包含数x,yx,y的长度最小的"萌"区间的左右端点

也就是说，我们需要找到长度最小的区间[l,r][l,r]，满足区间[l,r][l,r]是"萌"的，且同时包含数xx和数yy

如果有多个合法的区间，输出左端点最靠左的方案。

输入描述:

第一行三个整数N,x,yN,x,y，分别表示序列长度，询问的两个数 第二行有nn个整数表示序列内的元素，保证输入为一个排列

输出描述:

输出两个整数，表示长度最小"萌"区间的左右端点

示例1

输入

复制

5 2 3 5 2 1 3 4

输出

复制

2 4

说明

区间[2,4]={2,1,3}[2,4]={2,1,3}包含了2,32,3且为“萌”区间，可以证明没有比这更优的方案

示例2

输入

复制

8 3 5 6 7 1 8 5 2 4 3

输出

复制

5 8

备注:

保证2⩽n⩽105,1⩽x,y⩽n

思路：

可以先找到x，y的区间范围st，end。

然后再找st，end区间范围内的最小值x和最大值y。

再在x，y区间内找到区间范围st，end。

不断这样进行，直到end-st==y-x。

最大值和最小值，我是用线段树维护的。由于没有修改操作，所以用RMQ更好。

代码：

#include #include #include #include using namespace std;#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define root 1,N,1#define LL long longconst int maxn=1e5+10;const int INF=0x3f3f3f3f; int cnt=0;LL max_[maxn<<2][2];LL min_[maxn<<2][2];int a[maxn];int b[maxn];void pushup0(int rt){ max_[rt][0]=max(max_[rt<<1][0],max_[rt<<1|1][0]); min_[rt][0]=min(min_[rt<<1][0],min_[rt<<1|1][0]);} void pushup1(int rt){ max_[rt][1]=max(max_[rt<<1][1],max_[rt<<1|1][1]); min_[rt][1]=min(min_[rt<<1][1],min_[rt<<1|1][1]);} void build0(int l,int r,int rt){ if(l==r) { max_[rt][0]=a[cnt]; min_[rt][0]=a[cnt++]; return; } int m=(l+r)>>1; build0(lson); build0(rson); pushup0(rt);} void build1(int l,int r,int rt){ if(l==r) { max_[rt][1]=b[cnt]; min_[rt][1]=b[cnt++]; return; } int m=(l+r)>>1; build1(lson); build1(rson); pushup1(rt);} int quert0_min(int L,int R,int l,int r,int rt){ if(L<=l&&r<=R) { return min_[rt][0]; } int m=(l+r)>>1; int ret=INF; if(L<=m)ret=min(ret,quert0_min(L,R,lson)); if(R>m)ret=min(ret,quert0_min(L,R,rson)); return ret;} int quert0_max(int L,int R,int l,int r,int rt){ if(L<=l&&r<=R) { return max_[rt][0]; } int m=(l+r)>>1; int ret=0; if(L<=m)ret=max(ret,quert0_max(L,R,lson)); if(R>m)ret=max(ret,quert0_max(L,R,rson)); return ret;}int quert1_min(int L,int R,int l,int r,int rt){ if(L<=l&&r<=R) { return min_[rt][1]; } int m=(l+r)>>1; int ret=INF; if(L<=m)ret=min(ret,quert1_min(L,R,lson)); if(R>m)ret=min(ret,quert1_min(L,R,rson)); return ret;} int quert1_max(int L,int R,int l,int r,int rt){ if(L<=l&&r<=R) { return max_[rt][1]; } int m=(l+r)>>1; int ret=0; if(L<=m)ret=max(ret,quert1_max(L,R,lson)); if(R>m)ret=max(ret,quert1_max(L,R,rson)); return ret;} struct node{ int w,id;}G[maxn]; int cmp(node a,node b){ return a.wMap;bool vis[maxn]; int main(){ int n; scanf("%d%d%d",&n,&x,&y); int st=1,end=n; for(int i=1;i<=n;i++) { scanf("%d",&a[i]); G[i].w=a[i]; G[i].id=i; if(a[i]==x)st=i; if(a[i]==y)end=i; Map[a[i]]=i; } sort(G+1,G+1+n,cmp); for(int i=1;i<=n;i++) { b[i]=G[i].id; } cnt=1; build0(1,n,1); cnt=1; build1(1,n,1); if(st>end)swap(st,end); x=quert0_min(st,end,1,n,1); y=quert0_max(st,end,1,n,1); int pst=st,pend=end; while(y-x!=end-st) { st=quert1_min(x,y,1,n,1); end=quert1_max(x,y,1,n,1); x=quert0_min(st,end,1,n,1); y=quert0_max(st,end,1,n,1); } printf("%d %d\n",st,end); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。

标签：排序
上一篇:Codeforces 890 D. Restoration of string （技巧）
下一篇:Codeforces 890 D. Boxes And Balls （哈夫曼）
相关文章

 发表评论

暂时没有评论，来抢沙发吧~