动态最值

动态最值

题目描述

有一个包含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;
}