中英网站建设,重庆建设厂历史,做游戏排行榜的网站模板,整站优化加盟传送门:牛客
题目描述:
牛牛为了减#xff08;吃#xff09;肥#xff08;好#xff09;#xff0c;希望对他的零食序列有更深刻的了解#xff0c;所以他把他的零食排成一列#xff0c;然后对每一
个零食的美味程度都打了分#xff0c;现在他有可能执行两种操作…传送门:牛客
题目描述:
牛牛为了减吃肥好希望对他的零食序列有更深刻的了解所以他把他的零食排成一列然后对每一
个零食的美味程度都打了分现在他有可能执行两种操作
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一道线段树维护区间和的题目.
对于本题,最难解决显然是如何解决消除第kkk个位置的物品,显然我们是不能暴力维护的.我们的解决方案是记录每一个区间的实际的物品的数量.
那么对于我们的updateupdateupdate来说,我们此时的参数pospospos的含义就不在是原本的大区间的第pospospos个数了.此时就变成了本区间第pospospos个数了
对于我们的queryqueryquery来说,此时我们的参数l,rl,rl,r的含义变成了本区间第lll个数字开始到第rrr个数字之间的区间和.那么当我们的rrrtree[ls].cnttree[ls].cnttree[ls].cnt时,此时显然是在左区间,并且此时我们的l,rl,rl,r应不变;当我们的ltree[ls].cntltree[ls].cntltree[ls].cnt时,显然我们此时的区间是在右区间,并且注意,此时我们的l.rl.rl.r应该是变化的,因为是在rtrtrt区间的l,rl,rl,r,这就意味着是在rsrsrs区间的l−lcnt,r−lcntl-lcnt,r-lcntl−lcnt,r−lcnt的位置.当然如果是横跨两个区间,我们按照上述的方式进行一个分类即可
下面是具体的代码部分:
#include bits/stdc.h
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt1
#define rs rt1|1
#define lson l,mid,rt1
#define rson mid1,r,rt1|1
inline ll read() {ll x0,w1;char chgetchar();for(;ch9||ch0;chgetchar()) if(ch-) w-1;for(;ch0ch9;chgetchar()) xx*10ch-0;return x*w;
}
#define int long long
#define maxn 1000100
const double eps1e-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].mxmax(tree[ls].mx,tree[rs].mx);tree[rt].mnmin(tree[ls].mn,tree[rs].mn);tree[rt].cnttree[ls].cnttree[rs].cnt;
}
void build(int l,int r,int rt) {tree[rt].ll;tree[rt].rr;tree[rt].mx-ll_INF;tree[rt].mnll_INF;if(lr) {tree[rt].mxtree[rt].mna[l];tree[rt].cnt1;return ;}int mid(lr)1;build(lson);build(rson);pushup(rt);
}
void update(int pos,int rt) {if(tree[rt].ltree[rt].r) {tree[rt].mx-ll_INF;tree[rt].mnll_INF;tree[rt].cnt0;return ;}if(postree[ls].cnt) update(pos,ls);else update(pos-tree[ls].cnt,rs);pushup(rt);
}
pairint,int query(int l,int r,int rt) {if(l1rtree[rt].cnt) {return make_pair(tree[rt].mn,tree[rt].mx);}if(rtree[ls].cnt) return query(l,r,ls);else if(ltree[ls].cnt) return query(l-tree[ls].cnt,r-tree[ls].cnt,rs);else {pairint,int ans1query(l,tree[ls].cnt,ls);pairint,int ans2query(1,r-tree[ls].cnt,rs);return make_pair(min(ans1.first,ans2.first),max(ans1.second,ans2.second));}
}
signed main() {nread();mread();for(int i1;in;i) {a[i]read();}build(root);for(int i1;im;i) {int optread();if(opt1) {int posread();update(pos,1);}else {int lread(),rread();pairint,intans;ansquery(l,r,1);printf(%lld %lld\n,ans.first,ans.second);}}return 0;
}
