这就是一道数据结构裸题啊，最大极差就是区间最大值减最小值，最小极差就是相邻两个数差的最小值。然后平衡树splay/treap或者块状链表维护就行了。
第一次自己写块状链表，蛮好写，就是长。。然后就BZOJ rank1了（2019.5.11求不打脸 ）
CODE
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
char cb[1<<15],*cs=cb,*ct=cb;
#define getc() (cs==ct&&(ct=(cs=cb)+fread(cb,1,1<<15,stdin),cs==ct)?0:*cs++)
template<class T>inline void read(T &res) {
char ch; for(;!isdigit(ch=getc()););
for(res=ch-'0';isdigit(ch=getc());res=res*10+ch-'0');
}
const int Bsz = 500;
const int Cnt = 500;
const int inf = 0x3f3f3f3f;
stack<int>bin;
int n, q, num[MAXN], m;
struct Block{
int a[Bsz+5], use, nxt;
int mx, mn, d;
Block() {
memset(a, 0, sizeof a);
use = nxt = 0;
mx = 0, mn = d = inf;
}
inline void Clear() {
memset(a, 0, sizeof a);
use = nxt = 0;
mx = 0, mn = d = inf;
}
inline void getmax() {
mx = 0, mn = d = inf;
for(int i = 1; i <= use; ++i) {
mx = max(mx, a[i]),
mn = min(mn, a[i]);
if(i > 1) d = min(d, abs(a[i]-a[i-1]));
}
}
}b[Cnt+5];
inline int Query1(int x, int y) {
int l = 1;
while(x > b[l].use) x -= b[l].use, y -= b[l].use, l = b[l].nxt;
int r = l;
while(y > b[r].use) y -= b[r].use, r = b[r].nxt;
int Mx = 0, Mn = inf;
if(l == r) {
for(int i = x; i <= y; ++i)
Mx = max(Mx, b[l].a[i]),
Mn = min(Mn, b[l].a[i]);
return Mx-Mn;
}
for(int i = x; i <= b[l].use; ++i)
Mx = max(Mx, b[l].a[i]),
Mn = min(Mn, b[l].a[i]);
for(int i = 1; i <= y; ++i)
Mx = max(Mx, b[r].a[i]),
Mn = min(Mn, b[r].a[i]);
for(int i = b[l].nxt; i != r; i = b[i].nxt)
Mx = max(Mx, b[i].mx),
Mn = min(Mn, b[i].mn);
return Mx-Mn;
}
inline int Query2(int x, int y) {
int l = 1;
while(x > b[l].use) x -= b[l].use, y -= b[l].use, l = b[l].nxt;
int r = l;
while(y > b[r].use) y -= b[r].use, r = b[r].nxt;
int re = inf;
if(l == r) {
for(int i = x; i < y; ++i)
re = min(re, abs(b[l].a[i]-b[l].a[i+1]));
return re;
}
for(int i = x; i < b[l].use; ++i)
re = min(re, abs(b[l].a[i]-b[l].a[i+1]));
for(int i = 1; i < y; ++i)
re = min(re, abs(b[r].a[i]-b[r].a[i+1]));
for(int i = b[l].nxt; i != r; i = b[i].nxt)
re = min(re, b[i].d);
for(int i = l; i != r; i = b[i].nxt)
re = min(re, abs(b[i].a[b[i].use]-b[b[i].nxt].a[1]));
return re;
}
inline int Newnode() {
int re;
if(!bin.empty()) re = bin.top(), bin.pop();
else re = ++m;
b[re].Clear();
return re;
}
inline void Merge(int x, int val) {
int l = 1, pre = 0;
while(x > b[l].use) x -= b[l].use, pre = l, l = b[l].nxt;
if(x == b[l].use) {
int tmp = b[l].nxt;
b[tmp].a[1] = val;
b[tmp].getmax();
if(--b[l].use) b[l].getmax();
else b[pre].nxt = b[l].nxt, bin.push(l);
}
else {
b[l].a[x+1] = val;
--b[l].use;
for(int i = x; i <= b[l].use; ++i)
b[l].a[i] = b[l].a[i+1];
b[l].getmax();
}
}
inline void Insert(int x, int val) {
int l = 1, pre = 0;
while(x > b[l].use) x -= b[l].use, pre = l, l = b[l].nxt;
++b[l].use;
for(int i = b[l].use; i > x+1; --i) b[l].a[i] = b[l].a[i-1];
b[l].a[x+1] = val;
if(b[l].use > Bsz) {
int tmp = Newnode();
b[tmp].nxt = b[l].nxt; b[l].nxt = tmp;
b[tmp].use = b[l].use/2;
b[l].use -= b[tmp].use;
for(int i = 1; i <= b[tmp].use; ++i)
b[tmp].a[i] = b[l].a[b[l].use+i];
b[l].getmax(), b[tmp].getmax();
}
else b[l].getmax();
}
int main () {
read(n), read(q);
for(int i = 1; i <= n; ++i)
read(num[i]);
for(int i = 1; i*Bsz <= n; ++i) {
b[++m].use = Bsz; b[m-1].nxt = m;
for(int j = 1; j <= b[m].use; ++j)
b[m].a[j] = num[(m-1)*Bsz + j];
b[m].getmax();
}
if(n%Bsz) {
b[++m].use = n%Bsz; b[m-1].nxt = m;
for(int j = 1; j <= b[m].use; ++j)
b[m].a[j] = num[(m-1)*Bsz + j];
b[m].getmax();
}
char ch;
int x, y;
while(q--) {
while(!isalpha(ch=getc()));
ch=getc();
read(x), read(y);
switch(ch) {
case 'a':
printf("%d\n", Query1(x, y));
break;
case 'i':
printf("%d\n", Query2(x, y));
break;
case 'n':
Insert(x, y);
break;
case 'e':
Merge(x, y);
break;
}
}
}