自动搬运

查看原文

来自洛谷，原作者为

	LJC00118 Alice foo foo！

搬运于2025-08-24 22:07:06，当前版本为作者最后更新于2018-12-12 08:46:28，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

看到 Venus 的题解写道：首先排除Treap Splay这种根本不可能用于这题的东西

所以我们来用 $Splay$ 来做这题

$Splay$ 可以简单的提取出一个区间，如果要提取出 $[l, r]$ 这个区间，我们先 $splay (root, r + 1)$，此时 $root$ 的左孩子是区间 $[1, r]$，然后我们 $splay (root -> leftson, l - 1)$，此时 $root$ 的左孩子的右孩子是区间 $[l, r]$，我们在节点上维护区间最小值即可

当然如果直接 $splay (root, r + 1)$ 可能会出锅，如果 $l = 1 \ \&\&\ r = n$，$splay (root, r + 1 )$ 可能会导致 $RE$，所以我们在最左边和最右边放一个节点，改成 $splay (root, r + 2)$ 后 $splay (root -> leftson, l)$ 即可

#include <bits/stdc++.h>
#define CIOS ios::sync_with_stdio(false);
#define rep(i, a, b) for(register int i = a; i <= b; i++)
#define per(i, a, b) for(register int i = a; i >= b; i--)
#define DEBUG(x) cerr << "DEBUG" << x << " >>> ";
using namespace std;

typedef unsigned long long ull;
typedef long long ll;

template <typename T>
inline void read(T &f) {
	f = 0; T fu = 1; char c = getchar();
	while (c < '0' || c > '9') { if (c == '-') fu = -1; c = getchar(); }
	while (c >= '0' && c <= '9') { f = (f << 3) + (f << 1) + (c & 15); c = getchar(); }
	f *= fu;
}

template <typename T>
void print(T x) {
	if (x < 0) putchar('-'), x = -x;
	if (x < 10) putchar(x + 48);
	else print(x / 10), putchar(x % 10 + 48);
}

template <typename T>
void print(T x, char t) {
	print(x); putchar(t);
}

struct Node {
	Node *ch[2];
	int size, val, minn;
	
	Node (int a, int b, int c, Node *d, Node *e) : size(a), val(b), minn(c) { ch[0] = d; ch[1] = e; }
}*root, *null;

void update(Node *u) {
	u -> size = 1; u -> minn = u -> val;
	u -> size += u -> ch[0] -> size, u -> minn = min(u -> minn, u -> ch[0] -> minn);
	u -> size += u -> ch[1] -> size, u -> minn = min(u -> minn, u -> ch[1] -> minn);
}

void rotate(Node *&u, int d) {
	Node *tmp = u -> ch[d];
	u -> ch[d] = tmp -> ch[d ^ 1];
	tmp -> ch[d ^ 1] = u;
	update(u); update(tmp);
	u = tmp;
}

void splay(Node *&u, int k) {
	int ltree = u -> ch[0] -> size;
	if(ltree + 1 == k) return;
	int d = k > ltree, k2 = d ? k - ltree - 1 : k;
	int ltree2 = u -> ch[d] -> ch[0] -> size;
	if(ltree2 + 1 != k2) {
		int d2 = k2 > ltree2;
		splay(u -> ch[d] -> ch[d2], d2 ? k2 - ltree2 - 1 : k2);
		if(d == d2) rotate(u, d); else rotate(u -> ch[d], d2);
	}
	rotate(u, d);
}

int a[25005], n, m;
Node *build(int l, int r) {
	if(l > r) return null;
	if(l == r) return new Node(1, a[l], a[r], null, null);
	int mid = (l + r) >> 1; Node *t = new Node(1, a[mid], a[mid], build(l, mid - 1), build(mid + 1, r));
	return update(t), t;
}

int main() {
	null = new Node(0, 1e9, 1e9, 0, 0);
	read(n); read(m);
	for(register int i = 1; i <= n; i++) read(a[i]);
	root = build(0, n + 1); 
	while(m--) {
		int l, r; read(l); read(r);
		splay(root, r + 2);
		splay(root -> ch[0], l);
		print(root -> ch[0] -> ch[1] -> minn, '\n');
	} 
	return 0;
}