神秘物质

Time Limit: 10 Sec Memory Limit: 256 MB

Description

21ZZ 年，冬。

小诚退休以后， 不知为何重新燃起了对物理学的兴趣。 他从研究所借了些实验仪器，整天研究各种微观粒子。这

一天， 小诚刚从研究所得到了一块奇异的陨石样本， 便迫不及待地开始观测。 在精密仪器的视野下，构成陨石

的每个原子都无比清晰。 小诚发现， 这些原子排成若干列， 每一列的结构具有高度相似性。于是，他决定对单

独一列原子进行测量和测试。被选中的这列共有 N 个顺序排列的原子。 最初， 第 i 个原子具有能量 Ei。 随着

时间推移和人为测试， 这列原子在观测上会产生两种变化：

merge x e 当前第 x 个原子和第 x+1 个原子合并，得到能量为 e 的新原子；

insert x e 在当前第 x 个原子和第 x+1 个原子之间插入一个能量为 e 的新原子。

对于一列原子，小诚关心的是相邻一段中能量最大和能量最小的两个原子的能量差值，

称为区间极差。 因此， 除了观测变化外，小诚还要经常统计这列原子的两类数据：

max x y 当前第 x 到第 y 个原子之间的任意子区间中区间极差的最大值；

min x y 当前第 x 到第 y 个原子之间的任意子区间中区间极差的最小值。

其中， 子区间指的是长度至少是 2 的子区间。

小诚坚信这项研究可以获得诺贝尔物理学奖。为了让小诚早日了结心愿，你能否帮助他实现上述的观测和测量呢？

Input

第一行， 两个整数 N， M， 分别表示最初的原子数目和事件总数。

第二行， N 个整数 E1, E2, …, EN， 由空格隔开。依次表示每个原子的能量。

接下来 M 行， 每行为一个字符串和两个整数， 描述一次事件，格式见题目描述。

Output

输出若干行， 按顺序依次表示每次 max 和 min 类事件的测量结果。

Sample Input

img

Sample Output

1
　　2
　　1
　　5

HINT

img

Main idea

每个点有一个权值，维护一个结构，支持合并相邻两点，删除单点，加入单点，查询区间子集极差的最大值和最小值。

Solution

首先我们可以发现，区间子集极差的最大值显然就是整个区间的最大值-区间最小值，然后区间子集极差最小值只有相邻点的才会产生贡献。

那么我们用Splay来维护这个结构即可，维护一下子树最大值、子树最小值、子树邻差最小值即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
#include<bits/stdc++.h>
using namespace std;
typedef long long s64;

const int ONE = 300005;
const int INF = 2147483640;

int n,m;
int x,y,a[ONE];
int root,cnt;
int lc[ONE],rc[ONE],fa[ONE];
int size[ONE],val[ONE];
int maxx[ONE],minn[ONE],del[ONE];
int Ls[ONE],Rs[ONE];
char ch[10];

inline int get()
{
    int res=1,Q=1;  char c;
    while( (c=getchar())<48 || c>57)
        if(c=='-')Q=-1;
    if(Q) res=c-48;
    while((c=getchar())>=48 && c<=57)
        res=res*10+c-48;
    return res*Q;
}

void Up(int i)
{
    size[i] = size[lc[i]] + size[rc[i]] + 1;
    maxx[i] = minn[i] = val[i];
    del[i] = INF;
    Ls[i] = Rs[i] = i;
    if(lc[i])
    {
        Ls[i] = Ls[lc[i]];
        maxx[i] = max(maxx[i], maxx[lc[i]]);
        minn[i] = min(minn[i], minn[lc[i]]);
        del[i] = min(del[i], del[lc[i]]);
        del[i] = min(del[i], abs( val[i]-val[Rs[lc[i]]] ) );
    }
    if(rc[i])
    {
        Rs[i] = Rs[rc[i]];
        maxx[i] = max(maxx[i], maxx[rc[i]]);
        minn[i] = min(minn[i], minn[rc[i]]);
        del[i] = min(del[i], del[rc[i]]);
        del[i] = min(del[i], abs( val[i]-val[Ls[rc[i]]] ) );
    }
}

void Turn(int x)
{
    int y = fa[x], z = fa[y];
    int b = x==lc[y] ? rc[x]:lc[x];

    fa[y] = x;    fa[x] = z;
    if(b) fa[b] = y;

    if(z)
    {
        if(y == lc[z]) lc[z] = x;
        else rc[z] = x;
    }

    if(x==lc[y]) rc[x] = y,lc[y] = b;
    else lc[x] = y, rc[y] = b;

    Up(y);    Up(x);
}

void Splay(int x,int pos)
{
    while(fa[x] != pos)
    {
        if(fa[fa[x]] != pos)
        {
            if( (lc[fa[x]]==x) == (lc[fa[fa[x]]]==fa[x]) ) Turn(fa[x]);
            else Turn(x);
        }
        Turn(x);
    }
    if(pos == 0) root = x;
}

int Build(int i,int l,int r)
{
    int mid = l+r >> 1;
    fa[mid] = i;
    if(l <= mid-1) lc[mid] = Build(mid, l,mid-1);
    if(mid+1 <= r) rc[mid] = Build(mid, mid+1,r);
    Up(mid);
    return mid;
}

int Getid(int num)
{
    int i = root;
    while(size[lc[i]] + 1 != num)
    {
        if(size[lc[i]] + 1 < num)
            num -= size[lc[i]] + 1,    i = rc[i];
        else i = lc[i];
    }
    return i;
}

void Delete(int i)
{
    int x = Getid(i);
    Splay(x, 0);
    int L = Rs[lc[x]];    Splay(L,0);
    int R = Ls[rc[x]];    Splay(R,L);
    lc[R] = 0;
    Splay(R,0);
}

void Insert(int i,int Val)
{
    int x = Getid(i);
    Splay(x,0);
    int R = Ls[rc[x]];    Splay(R,x);
    val[++cnt] = Val; fa[cnt] = R; lc[R] = cnt;
    Splay(cnt,0);
}

int main()
{
    n=get();    m=get();
    for(int i=1;i<=n;i++)
        val[i+1] = get();
    val[1] = val[n+2] = INF;

    cnt = n+2;
    root = n+3 >> 1;
    Build(0,1,n+2);

    while(m--)
    {
        scanf("%s",ch+1);    x=get();    y=get();
        x++;

        if(ch[3] == 'r')
        {
            Insert(x+1,y);
            Delete(x);    Delete(x);
        }
        if(ch[3] == 's')
            Insert(x,y);
        if(ch[3] == 'x')
        {
            y++;
            x = Getid(x-1);    y = Getid(y+1);
            Splay(x,0);    Splay(y,x);
            printf("%d\n", maxx[lc[y]] - minn[lc[y]]);
        }
        if(ch[3] == 'n')
        {
            y++;
            x = Getid(x-1);    y = Getid(y+1);
            Splay(x,0);    Splay(y,x);
            printf("%d\n", del[lc[y]]);
        }

    }
}