P6011 [SCOI2006]动态最值

单点更新，区间查询，适合用线段树来解决。其中注意删除操作的实现。查询区间最大最小值时，注意右子树的标号控制。

更多注释详见代码

#include <bits/stdc++.h>
#define L(u) (u<<1)
#define R(u) (u<<1|1)
using namespace std;
const int mx=1000001;
struct Tree
{
    int lch,rch,Min,Max,num;
} tree[mx<<2];//Min:区间最小值 Max:区间最大值 num:区间内尚存的，即未被删除的元素数目
int d[mx],m,n,l,r,ans1,ans2;
char s;
void read(int &k)
{
    int f=1;
    char c=getchar();
    while ((c<48||c>57)&&c!='-') c=getchar();
    if (c=='-') f=-1,c=getchar();
    k = 0;
    while (48<=c&&c<=57) k=k*10+c-48,c=getchar();
    k=f*k;
}
void Pushup(int u)
{
    tree[u].Max=max(tree[L(u)].Max,tree[R(u)].Max);
    tree[u].Min=min(tree[L(u)].Min,tree[R(u)].Min);
    tree[u].num=tree[L(u)].num+tree[R(u)].num;
}
void Build(int u,int l,int r)
{//建树。根节点编号是1
    tree[u].lch=l;
    tree[u].rch=r;
    if (l==r)
	{//叶节点
        tree[u].Max=tree[u].Min=d[l];
        tree[u].num=1;
        return ;
    }
    int mid=(l+r)>>1;
    Build(L(u),l,mid);//递归，建左子树
    Build(R(u),mid+1,r);//递归，建右子树
    Pushup(u);//建完两棵子树，向上更新一下
}
void Delete(int u,int num)
{//删除节点的操作实现。这个num是待删元素的标号
    if((tree[u].lch==tree[u].rch))
	{//叶节点。删的就是它
        tree[u].num--;//没有元素了
        tree[u].Min=2147483647;
        tree[u].Max=-2147483648;
        return;
    }
    int n1=tree[L(u)].num;
    if(num<=n1) Delete(L(u),num);//标号≤左子树所含元素个数，则待删元素在左子树上，递归找它
    else Delete(R(u),num-n1);//不是左子树就是右子树啦。注意这里往右子树递归的时候，标号减去左子树所含元素数目
    Pushup(u);//少了元素了，需要更新
}
void Query(int u,int l,int r)
{
    if (l==1&&tree[u].num==r)
	{
        ans1=min(ans1,tree[u].Min);
        ans2=max(ans2,tree[u].Max);
        return ;
    }
    int n1=tree[L(u)].num,n2=tree[R(u)].num;
    if (l<=n1&&r>n1)
	{//待查询区间跨了左右两棵子树
        Query(L(u),l,n1);
        Query(R(u),1,r-n1);
    } else if (l<=n1&&r<=n1) Query(L(u),l,r);//左子树
    else if (l>n1&&r<=n1+n2) Query(R(u),l-n1,r-n1);//右子树
}
int main()
{
    read(n);
    read(m);
    for (int i=1; i<=n; ++i) read(d[i]);
    for (int i=1; i<=4*n; ++i) tree[i].Min=2147483647,tree[i].Max=-2147483648;
    Build(1,1,n);
    while (m--)
	{
        scanf(" %c",&s);
        if (s=='1')
		{
            scanf("%d",&l);
            Delete(1,l);
        }
		else
		{
            scanf("%d%d",&l,&r);
            ans1=2147483647,ans2=-2147483648;
            Query(1,l,r);
            printf("%d %d\n",ans1,ans2);
        }
    }
    return 0;
}