动态最值
题目描述
有一个包含n个元素的数组,要求实现以下操作:
DELETE k:删除位置k上的数。右边的数往左移一个位置。
QUERY i j:查询位置i~j上所有数的最小值和最大值。
例如有10个元素:
位置 1 2 3 4 5 6 7 8 9 10 元素 1 5 2 6 7 4 9 3 1 5
QUERY 2 8的结果为2 9。
依次执行DELETE 3和DELETE
6(注意这时删除的是原始数组的元素7)后数组变为:
位置 1 2 3 4 5 6 7 8
元素 1 5 6 7 4 3 1 5
QUERY 2 8的结果为1 7。
输入格式:
第一行包含两个数n,m
表示原始数组的元素个数和操作的个数。第二行包括n个数,表示原始数组。以下m行,每行格式为1 k或者2 i j,其中第一个数为1表示删除操作,为2表示询问操作。
输出格式:
对每个询问操作输出一行,包括两个数,表示该范围内的最小值和最大值。time 2.5s
思路:
用链式线段树解决,每次维护当前cur的元素个数,因为操作只有删除,所以不会存在分配不均匀使得复杂度爆炸的情况。
找数的时候根据当前区间包含元素来确定具体区间
可以提高代码能力
CODE
// luogu-judger-enable-o2
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#define lls S[cur].ls
#define rrs S[cur].rs
struct Segmenttree{
int cur,ls,rs,max,min,size;
Segmenttree(){
cur=ls=rs=max=min=size=0;
}
}S[1010100<<2];
int n,m,tot,root,max,min;
int a[1010010];
inline int check(int cur){
printf("Debug::%d %d %d %d\n",cur,S[cur].size,S[lls].size,S[rrs].size);
}
inline int pushup(int cur){
S[cur].max=std::max(S[S[cur].ls].max,S[S[cur].rs].max);
S[cur].min=std::min(S[S[cur].ls].min,S[S[cur].rs].min);
S[cur].size=S[lls].size+S[rrs].size;
}
inline int build(int l,int r,int cur){
if(l==r){
tot++;
S[tot].cur=tot;S[tot].max=S[tot].min=a[l];
S[tot].size=1;
return tot;
}
int mid=l+r>>1;
cur=++tot;S[cur].cur=cur;
if(root==0) root=tot;
S[cur].ls=build(l,mid,cur);
S[cur].rs=build(mid+1,r,cur);
pushup(cur);
return cur;
}
inline int del(int x,int cur){
if(S[cur].size==1){
S[cur].size=0;
S[cur].min=0x3f3f3f3f;
S[cur].max=-(0x3f3f3f3f);
return 0;
}
if(x<=S[lls].size)del(x,lls);
else del(x-S[lls].size,rrs);
pushup(cur);
}
inline int ask(int l,int r,int cur){
//check(cur);
if(cur==0) return 0;
if(r-l+1>=S[cur].size){
max=std::max(max,S[cur].max);
min=std::min(min,S[cur].min);
return 0;
}
int mid=l+r>>1;
if(l<=S[lls].size) ask(l,std::min(r,S[lls].size),lls);
if(r>S[lls].size) ask(std::max(l-S[lls].size,1),r-S[lls].size,rrs);
pushup(cur);
}
int main (){
scanf("%d %d",&n,&m);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
}
S[0].min=0x3f3f3f3f;S[0].max=-(int)(0x3f3f3f3f);
build(1,n,0);
while(m--){
int od,x,y;
scanf("%d",&od);
if(od==1){
scanf("%d",&x);
del(x,root);
}
if(od==2){
max=-(0x3f3f3f3f),min=0x3f3f3f3f;
scanf("%d %d",&x,&y);
ask(x,y,root);
printf("%d %d\n",min,max);
}
}
return 0;
}
0 条评论