链接：https://ac.nowcoder.com/acm/contest/26896/1020
来源：牛客网
来源：牛客网
题目描述
牛牛为了减（吃）肥（好），希望对他的零食序列有更深刻的了解，所以他把他的零食排成一列，然后对每一个零食的美味程度都打了分，现在他有可能执行两种操作：
eat k：吃掉当前的第k个零食。右边的零食全部往左移动一位（编号减一）。
query i j：查询当前第i个零食到第j个零食里面美味度最高的和最低的零食的美味度。
输入描述:
第一行包含两个数n, m，表示原始数组的元素个数和操作的个数。第二行包括n个数，表示原始数组。以下m行，每行格式为1 k或者2 i j，其中第一个数为1表示吃掉，为2表示询问。
输出描述:
对每个询问操作输出一行，包括两个数，表示该范围内的最小值和最大值。
题型：
线段树--单点修改与区间查询（最值）
思路：
单点修改与区间查询不需要多说，直接套板子即可。关键在于这个修改之后，右边的值都需要往左移动一位（编号减一）
考虑假删除，即保留该节点，首先需要消除其的最值影响，即将已经被删除的节点的最大值设为-1e9-10，最小值设为1e9+10，这样这个节点就不影响最值的判断。
然后需要消除其的区间占位影响，考虑新开一个cnt数组维护树上每一个tree节点的剩下的未被删除的点的个数，当某个元素被假删除时，将其的cnt值变为0
对于消除其的区间移动影响，考虑新开一个函数专门用于将输入的绝对位置转化成相对位置，即代码二中的posfind函数
如何转化呢？分类讨论
一.当前的查找区间已经变成单点了，即l=r，那么相对位置=l=r;
二.当前的查找区间未变成单点（l<r），此时，我们知道，当前的线段树（tree[p]）的左子树（tree[p*2]）和右子树（tree[p*2+1]）都存储着cnt，即左子树（cnt[p*2]），右子树（tree[p*2+1]）分别剩余的元素的个数。
如果输入的绝对位置的值<=cnt[p*2]，那么这个绝对位置一定在左子树
如果输入的绝对位置的值>cnt[p*2]，那么这个绝对位置一定在右子树
即 if(cnt[p*2]>=num) return posfind(p*2,l,mid,num);
else return posfind(p*2+1,mid+1,r,num-cnt[p*2]); //注意此处num要减去cnt[p*2]，因为这里代表着在右子树中查找，而右子树中的值是从1编号的，需要减去左子树的剩余值才等于右子树中的节点的值
else return posfind(p*2+1,mid+1,r,num-cnt[p*2]); //注意此处num要减去cnt[p*2]，因为这里代表着在右子树中查找，而右子树中的值是从1编号的，需要减去左子树的剩余值才等于右子树中的节点的值
总体思路大概就是这样，难度主要在于位置的转化，可以新开一个函数专门转化（代码二），也可以把转化的代码并入修改/查询的函数中（代码一），个人认为代码二比代码一要清晰易懂一些，可能是因为代码二更贴近板子吧
代码（在修改与查询的函数中改变位置）：
#include<bits/stdc++.h>
#define INF 0x3f3f3f
using namespace std;
const int N=1000000;
int a[N],tree[N*4],tree2[N*4],cnt[N*4];
void build(int p,int l,int r){
if(l==r){
cnt[p]=1;
tree[p]=a[l];
tree2[p]=a[l];
return;
}
int mid=(l+r)/2;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
tree[p]=max(tree[p*2],tree[p*2+1]);
tree2[p]=min(tree2[p*2],tree2[p*2+1]);
cnt[p]=cnt[p*2]+cnt[p*2+1];
}
void eat(int p,int l,int r,int num){
if(l==r){
cnt[p]=0;
tree[p]=-1e9-10;
tree2[p]=1e9+10;
return;
}
int mid=(l+r)/2;
if(cnt[p*2]>=num) eat(p*2,l,mid,num);
else eat(p*2+1,mid+1,r,num-cnt[p*2]);
tree[p]=max(tree[p*2],tree[p*2+1]);
tree2[p]=min(tree2[p*2],tree2[p*2+1]);
cnt[p]=cnt[p*2]+cnt[p*2+1];
}
int calc(int p,int l,int r,int x,int y){
if(x==1 && y==cnt[p]){
return tree[p];
}
int mid=(l+r)/2;
if(cnt[p*2]>=y) return calc(p*2,l,mid,x,y);
if(cnt[p*2]<x) return calc(p*2+1,mid+1,r,x-cnt[p*2],y-cnt[p*2]);
return max(calc(p*2,l,mid,x,cnt[p*2]),calc(p*2+1,mid+1,r,1,y-cnt[p*2]));
}
int calc2(int p,int l,int r,int x,int y){
if(x==1 && y==cnt[p]){
return tree2[p];
}
int mid=(l+r)/2;
if(cnt[p*2]>=y) return calc2(p*2,l,mid,x,y);
if(cnt[p*2]<x) return calc2(p*2+1,mid+1,r,x-cnt[p*2],y-cnt[p*2]);
return min(calc2(p*2,l,mid,x,cnt[p*2]),calc2(p*2+1,mid+1,r,1,y-cnt[p*2]));
}
int main(){
int n,m;
//memset(tree2,INF,sizeof(tree2));
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
build(1,1,n);
while(m--){
int x,y,z;
scanf("%d",&x);
if(x==1){
scanf("%d",&y);
eat(1,1,n,y);
}else{
scanf("%d%d",&y,&z);
printf("%d %d\n",calc2(1,1,n,y,z),calc(1,1,n,y,z));
}
}
return 0;
}
代码（新开一个函数专门用于查询位置，修改与查询的函数不变）：
#include<bits/stdc++.h>
#define INF 0x3f3f3f
using namespace std;
const int N=1000000;
int a[N],tree[N*4],tree2[N*4],cnt[N*4];
void build(int p,int l,int r){
if(l==r){
cnt[p]=1;
tree[p]=a[l];
tree2[p]=a[l];
return;
}
int mid=(l+r)/2;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
tree[p]=max(tree[p*2],tree[p*2+1]);
tree2[p]=min(tree2[p*2],tree2[p*2+1]);
cnt[p]=cnt[p*2]+cnt[p*2+1];
}
void eat(int p,int l,int r,int num){
if(l==r){
cnt[p]=0;
tree[p]=-1e9-10;
tree2[p]=1e9+10;
return;
}
int mid=(l+r)/2;
if(num<=mid) eat(p*2,l,mid,num);
else eat(p*2+1,mid+1,r,num);
tree[p]=max(tree[p*2],tree[p*2+1]);
tree2[p]=min(tree2[p*2],tree2[p*2+1]);
cnt[p]=cnt[p*2]+cnt[p*2+1];
}
int calc(int p,int l,int r,int x,int y){
if(x<=l && y>=r){
return tree[p];
}
int mid=(l+r)/2;
if(y<=mid) return calc(p*2,l,mid,x,y);
if(x>=mid+1) return calc(p*2+1,mid+1,r,x,y);
return max(calc(p*2,l,mid,x,mid),calc(p*2+1,mid+1,r,mid+1,y));
}
int calc2(int p,int l,int r,int x,int y){
if(x<=l && y>=r){
return tree2[p];
}
int mid=(l+r)/2;
if(y<=mid) return calc2(p*2,l,mid,x,y);
if(x>=mid+1) return calc2(p*2+1,mid+1,r,x,y);
return min(calc2(p*2,l,mid,x,mid),calc2(p*2+1,mid+1,r,mid+1,y));
}
int posfind(int p,int l,int r,int num){ //专门用于查询位置的函数
if(l==r) return l;
int mid=(l+r)/2;
if(cnt[p*2]>=num) return posfind(p*2,l,mid,num);
else return posfind(p*2+1,mid+1,r,num-cnt[p*2]);
}
int main(){
int n,m;
//memset(tree2,INF,sizeof(tree2));
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
build(1,1,n);
while(m--){
int x,y,z;
scanf("%d",&x);
if(x==1){
scanf("%d",&y);
y=posfind(1,1,n,y);
eat(1,1,n,y);
}else{
scanf("%d%d",&y,&z);
y=posfind(1,1,n,y);
z=posfind(1,1,n,z);
printf("%d %d\n",calc2(1,1,n,y,z),calc(1,1,n,y,z));
}
}
return 0;
}
京公网安备 11010502036488号