题目描述

牛牛为了减（吃）肥（好），希望对他的零食序列有更深刻的了解，所以他把他的零食排成一列，然后对每一个零食的美味程度都打了分，现在他有可能执行两种操作：
eat k：吃掉当前的第k个零食。右边的零食全部往左移动一位（编号减一）。
query i j：查询当前第i个零食到第j个零食里面美味度最高的和最低的零食的美味度。

输入描述:

第一行包含两个数n, m，表示原始数组的元素个数和操作的个数。第二行包括n个数，表示原始数组。以下m行，每行格式为1 k或者2 i j，其中第一个数为1表示吃掉，为2表示询问。

输出描述:

对每个询问操作输出一行，包括两个数，表示该范围内的最小值和最大值。

题解

这道题的难度所在就是我们怎么处理吃掉零食的右边的零食全部往左移动一位的问题。
我们知道，线段树是没有左移操作的，如果每次暴力的话复杂度有爆炸，这时候我们思考利用一个属性来解决左移问题。我们可以记录每个区间的元素个数，利用我们找的下标和当前的数量进行对比（跟区间第k大思想有些相似），下面我用图来说明一下
假如我们有一个数列是这样的
图片说明
下面我们删除第三个元素就变成了下面这个样子
图片说明
我们再查询区间2到4
图片说明
大概就是这个意思，剩下的我就不仔细画了，可以好好体会体会。

代码

#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#include<stack>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pb push_back
#define pii pair<int,int>
#define all(A) A.begin(), A.end()
#define fi first
#define se second
#define MP make_pair
#define rep(i,n) for(register int i=0;i<(n);++i)
#define repi(i,a,b) for(register int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(register int i=int(b);i>=(a);--i)
template<typename T>
inline T read(){
    T s=0,f=1; char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') f=-1;ch = getchar();}
    while(isdigit(ch)) {s=(s<<3)+(s<<1)+ch-48;ch = getchar();}
    return s*f;
}
#define gn() read<int>()
#define gl() read<ll>()
template<typename T>
inline void print(T x) {
    if(x<0) putchar('-'), x=-x;
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
////////////////////////////////////////////////////////////////////////
const int N=1e6+100;
int a[N];
struct node{
    int maxn,minx,num;
    #define maxn(n) tree[n].maxn
    #define minx(n) tree[n].minx
    #define num(n) tree[n].num
}tree[N<<2];
void build(int node,int l,int r){
    if(l==r){
        maxn(node)=minx(node)=a[l];
        num(node)=1;
        return ;
    }
    int mid=(l+r)>>1;
    build(node<<1,l,mid);
    build(node<<1|1,mid+1,r);
    maxn(node)=max(maxn(node<<1),maxn(node<<1|1));
    minx(node)=min(minx(node<<1),minx(node<<1|1));
    num(node)=num(node<<1)+num(node<<1|1);
}
void del(int node,int l,int r,int k){
    if(l==r){
        num(node)=0;
        maxn(node)=-0x7f7f7f7f;
        minx(node)=0x7f7f7f7f;
        return ;
    }
    int mid=(l+r)>>1;
    if(k<=num(node<<1))del(node<<1,l,mid,k);
    else del(node<<1|1,mid+1,r,k-num(node<<1));
    maxn(node)=max(maxn(node<<1),maxn(node<<1|1));
    minx(node)=min(minx(node<<1),minx(node<<1|1));
    num(node)=num(node<<1)+num(node<<1|1);
}
pii query(int node,int l,int r,int x,int y){
    if(x<=1&&num(node)<=y){
        return MP(maxn(node),minx(node));
    }
    int mid=(l+r)>>1;
    pii a={-0x7f7f7f7f,0x7f7f7f7f},b={-0x7f7f7f7f,0x7f7f7f7f};
    if(x<=num(node<<1))a=query(node<<1,l,mid,x,y);
    if(y>num(node<<1))b=query(node<<1|1,mid+1,r,x-num(node<<1),y-num(node<<1));
    return MP(max(a.fi,b.fi),min(a.se,b.se));
}
////////////////////////////////////////////////////////////////////////
int main(){
    int n=gn(),m=gn();
    repi(i,1,n)a[i]=gn();
    build(1,1,n);
    while(m--){
        int cmd=gn();
        if(cmd==1){
            int k=gn();
            del(1,1,n,k);
        }
        else{
            int l=gn(),r=gn();
            pii now=query(1,1,n,l,r);
            printf("%d %d\n",now.se,now.fi);
        }
    }
}
/**
* In every life we have some trouble
* When you worry you make it double
* Don't worry,be happy.
**/

祝大家AC愉快~