题解 P5097 【[USACO2004OPEN]Cave Cows 2 洞穴里的牛之二】
LJC00118
·
·
题解
看到 Venus 的题解写道：首先排除Treap Splay这种根本不可能用于这题的东西
所以我们来用 Splay 来做这题
当然如果直接 $ splay (root, r + 1) $ 可能会出锅，如果 $ l = 1 \ \&\&\ r = n$，$ splay (root, r + 1 ) $ 可能会导致 $ RE $，所以我们在最左边和最右边放一个节点，改成 $ splay (root, r + 2) $ 后 $ splay (root -> leftson, l) $ 即可
```cpp
#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;
}
```