自动搬运

查看原文

来自洛谷，原作者为

	EternalEpic 一个人的命运啊,当然要靠自我奋斗,但是也要考虑到历史的行程。

搬运于2025-08-24 22:16:30，当前版本为作者最后更新于2020-05-21 16:55:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这道题，有删除操作，于是我想到了两种做法。

法1：序列平衡树，对于做过文艺平衡树的人很简单，只要维护一个类似线段树标记，就可以了。这里不着重描述。

法2：有一个很简单暴力的方法——用线段树。一个棘手的问题就是线段树是静态的，怎么支持删除？我们根本不要在结构中删去节点，我们只要将该节点的min设置成INT_MAX，max设置成INT_MIN，就可以消除掉该节点的贡献，从而在形式上“删去”了次节点。

那么，有一个深邃的问题，删的过程中数组下标在变化，所以要用树状数组维护pos之前删去了几个数，从而得到真正的idx。

但是，题目是给你真正的下标idx，你要倒着求pos，这就需要二分了，注意，二分时可能有多个满足值，要取最大的那一个，因为前面的都是已删去的数。

Last but not the least，code is here:

const int Maxn = 1e6 + 5; int n, m, a[Maxn];
struct SegmentTree {
	int tmin[Maxn << 2 | 1], tmax[Maxn << 2 | 1];
	SegmentTree(void) {}
	inline void pushup(int pos) {
		tmin[pos] = min(tmin[pos << 1], tmin[pos << 1 | 1]);
		tmax[pos] = max(tmax[pos << 1], tmax[pos << 1 | 1]);
	}

	inline void build(int pos, int l, int r) {
		if (l == r) { tmin[pos] = tmax[pos] = a[l]; return; }
		int mid = l + r >> 1;
		build(pos << 1, l, mid),
		build(pos << 1 | 1, mid + 1, r);
		pushup(pos);
	}

	inline void remove(int pos, int l, int r, int idx) {
		if (l == r) { tmin[pos] = INT_MAX, tmax[pos] = INT_MIN; return; }
		int mid = l + r >> 1;
		if (idx <= mid) remove(pos << 1, l, mid, idx);
		else remove(pos << 1 | 1, mid + 1, r, idx);
		pushup(pos);
	}
	
	inline int querymin(int pos, int l, int r, int L, int R) {
		if (L <= l && R >= r) return tmin[pos];
		int mid = l + r >> 1, ret = INT_MAX;
		if (L <= mid) ret = querymin(pos << 1, l, mid, L, R);
		if (R > mid) chkmin(ret, querymin(pos << 1 | 1, mid + 1, r, L, R));
		return ret;
	}

	inline int querymax(int pos, int l, int r, int L, int R) {
		if (L <= l && R >= r) return tmax[pos];
		int mid = l + r >> 1, ret = INT_MIN;
		if (L <= mid) ret = querymax(pos << 1, l, mid, L, R);
		if (R > mid) chkmax(ret, querymax(pos << 1 | 1, mid + 1, r, L, R));
		return ret;
	}
} sgt;

struct BinaryIndexTree {
	int c[Maxn];
	BinaryIndexTree(void) { Ms(c, 0); return; }
	inline void update(int pos) { for (; pos <= n; pos += lowbit(pos)) ++c[pos]; }
	inline int query(int pos) { int ret = 0; for (; pos; pos -= lowbit(pos)) ret += c[pos]; return ret; }
} bit;

inline int Index(int pos) {
	int l = 1, r = n, ans;
	while (l <= r) {
		int mid = l + r >> 1;
		if (mid - bit.query(mid) == pos) ans = mid;
		if (mid - bit.query(mid) > pos) r = mid - 1;
		else l = mid + 1;
	} return ans;
}

signed main(void) {
//	file("");
	read(n), read(m);
	for (int i = 1; i <= n; i++) read(a[i]);
	sgt.build(1, 1, n);
	for (int opt, l, r; m; m--) {
		read(opt), read(l);
		if (opt == 1) { l = Index(l);
			sgt.remove(1, 1, n, l);
			bit.update(l + 1);
		} else {
			read(r); l = Index(l), r = Index(r);
			writeln(sgt.querymin(1, 1, n, l, r), ' ');
			writeln(sgt.querymax(1, 1, n, l, r));
		}
	}
//	fwrite(pf, 1, o1 - pf, stdout);
	return 0;
}