题解 | #牛牛的最美味和最不美味的零食#

牛牛的最美味和最不美味的零食

#include <iostream>

using namespace std;

const int N = 1e6 + 10, INF = 0x3f3f3f3f;

int n, m, a[N];
struct Node
{
	int l, r;
	int cnt, ma, mi;
}tr[N << 2];

template <class T>
inline void read(T &res)
{
	char ch; bool flag = false;
	while((ch = getchar()) < '0' || ch > '9')
		if(ch == '-') flag = true;
	res = (ch ^ 48);
	while((ch = getchar()) >= '0' && ch <= '9')
		res = (res << 1) + (res << 3) + (ch ^ 48);
	if(flag) res = ~res + 1;
}

//要更新的东西有点多的时候就写俩pushup
void pushup(Node &u, Node &l, Node &r)
{
	u.cnt = l.cnt + r.cnt;
	u.ma = max(l.ma, r.ma), u.mi = min(l.mi, r.mi);
}
void pushup(int u) {pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);}

void build(int u, int l, int r)
{
	tr[u].l = l, tr[u].r = r;
	if(l == r)
	{
		tr[u].cnt = 1;
		tr[u].mi = tr[u].ma = a[l];
		return ;
	}
	int mid = l + r >> 1;
	build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
	pushup(u);
}

void del(int u, int x)
{
	if(tr[u].l == tr[u].r)
	{
		tr[u].cnt = 0;//将当前区间的零食数量置零
		tr[u].mi = INF, tr[u].ma = -INF;//同时修改mi和ma的值
		return ;
	}
	int lcnt = tr[u << 1].cnt;//左区间零食个数
	if(x <= lcnt) del(u << 1, x);//在左区间，就去左区间删左区间的第x个零食
	else del(u << 1 | 1, x - lcnt);//在右区间，就去右区间删右区间的第x - lcnt个零食
	pushup(u);
}

Node query(int u, int l, int r)
{
    //必须要完全保证覆盖当前区间，否则一定在下面三种情况之中
	if(l == 1 && r == tr[u].cnt) return tr[u];
	int lcnt = tr[u << 1].cnt;
	if(r <= lcnt) return query(u << 1, l, r);//如果完全在左区间
	else if(l > lcnt) return query(u << 1 | 1, l - lcnt, r - lcnt);//完全在右区间
	else//横跨左右两个区间
	{
	    //这里一定要注意传参，如果lcnt写成r，会一直造成query的第三种情况，引发无穷递归
		Node left = query(u << 1, l, lcnt);
		Node right = query(u << 1 | 1, 1, r - lcnt);
		Node res;
		pushup(res, left, right);
		return res;
	}
}

int main()
{
	read(n), read(m);
	for(int i = 1; i <= n; i ++) read(a[i]);
	build(1, 1, n);
	for(int i = 1; i <= m; i ++)
	{
		int op, k, l, r;
		read(op);
		if(op == 1)
		{
			read(k);
			del(1, k);
		}
		else
		{
			read(l), read(r);
			Node res = query(1, l, r);
			printf("%d %d\n", res.mi, res.ma);
		}
	}
	
	return 0;
}