刷题记录:牛客NC208250牛牛的最美味和最不美味的零食

传送门:牛客

题目描述:

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

一道线段树维护区间和的题目.

对于本题,最难解决显然是如何解决消除第$k$个位置的物品,显然我们是不能暴力维护的.我们的解决方案是记录每一个区间的实际的物品的数量.

那么对于我们的$update$来说,我们此时的参数$pos$的含义就不在是原本的大区间的第$pos$个数了.此时就变成了本区间第$pos$个数了

对于我们的$query$来说,此时我们的参数$l,r$的含义变成了本区间第$l$个数字开始到第$r$个数字之间的区间和.那么当我们的$r$<=$tree[ls].cnt$时,此时显然是在左区间,并且此时我们的$l,r$应不变;当我们的$l>tree[ls].cnt$时,显然我们此时的区间是在右区间,并且注意,此时我们的$l.r$应该是变化的,因为是在$rt$区间的$l,r$,这就意味着是在$rs$区间的$l-lcnt,r-lcnt$的位置.当然如果是横跨两个区间,我们按照上述的方式进行一个分类即可

下面是具体的代码部分:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {ll x=0,w=1;char ch=getchar();for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';return x*w;
}
#define int long long
#define maxn 1000100
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
int n,m;
struct Segment_tree{int l,r,mx,mn,cnt;
}tree[maxn*4];
int a[maxn];
void pushup(int rt) {tree[rt].mx=max(tree[ls].mx,tree[rs].mx);tree[rt].mn=min(tree[ls].mn,tree[rs].mn);tree[rt].cnt=tree[ls].cnt+tree[rs].cnt;
}
void build(int l,int r,int rt) {tree[rt].l=l;tree[rt].r=r;tree[rt].mx=-ll_INF;tree[rt].mn=ll_INF;if(l==r) {tree[rt].mx=tree[rt].mn=a[l];tree[rt].cnt=1;return ;}int mid=(l+r)>>1;build(lson);build(rson);pushup(rt);
}
void update(int pos,int rt) {if(tree[rt].l==tree[rt].r) {tree[rt].mx=-ll_INF;tree[rt].mn=ll_INF;tree[rt].cnt=0;return ;}if(pos<=tree[ls].cnt) update(pos,ls);else update(pos-tree[ls].cnt,rs);pushup(rt);
}
pair<int,int> query(int l,int r,int rt) {if(l==1&&r==tree[rt].cnt) {return make_pair(tree[rt].mn,tree[rt].mx);}if(r<=tree[ls].cnt) return query(l,r,ls);else if(l>tree[ls].cnt) return query(l-tree[ls].cnt,r-tree[ls].cnt,rs);else {pair<int,int> ans1=query(l,tree[ls].cnt,ls);pair<int,int> ans2=query(1,r-tree[ls].cnt,rs);return make_pair(min(ans1.first,ans2.first),max(ans1.second,ans2.second));}
}
signed main() {n=read();m=read();for(int i=1;i<=n;i++) {a[i]=read();}build(root);for(int i=1;i<=m;i++) {int opt=read();if(opt==1) {int pos=read();update(pos,1);}else {int l=read(),r=read();pair<int,int>ans;ans=query(l,r,1);printf("%lld %lld\n",ans.first,ans.second);}}return 0;
}