1 /************************************************************** 2     Problem: 1058 3     User: rausen 4     Language: C++ 5     Result: Accepted 6     Time:15272 ms 7     Memory:68408 kb 8 ****************************************************************/ 9  10 #include <cstdio>11 #include <vector>12 #include <queue>13 #include <algorithm>14 #include <map>15 #include <set>16  17 using namespace std;18 const int N = 500005;19 const int inf = (int) 1e9;20 int n, m;21 int Start[N], End[N];22 multiset <int> a, b;23 map <int, int> mp;24 priority_queue <int, vector<int>, greater<int> > h;25  26 inline int read(){27     int x = 0, sgn = 1;28     char ch = getchar();29     while (ch < ‘0‘ || ch > ‘9‘){30         if (ch == ‘-‘) sgn = -1;31         ch = getchar();32     }33     while (ch >= ‘0‘ && ch <= ‘9‘){34         x = x * 10 + ch - ‘0‘;35         ch = getchar();36     }37     return sgn * x;38 }39  40 int pr[15], NUM = 0;41 inline void print(int x){42     if (!x){43         puts("0");44         return;45     }46     while (x)47         pr[++NUM] = x % 10, x /= 10;48     while (NUM)49         putchar(pr[NUM--] + ‘0‘);50     putchar(‘\n‘);51 }52  53 inline void insert(int x){54     if ((++mp[x]) == 1) a.insert(x);55 }56  57 int l, r;58 inline void push(int x){59     l = *--b.lower_bound(x), r = *b.lower_bound(x);60     h.push(min(x - l, r - x));61     b.insert(x);62 }63  64 int main(){65     int i, p, X, t;66     n = read(), m = read();67     b.insert(inf), b.insert(-inf);68     for (i = 1; i <= n; ++i){69         X = read();70         End[i] = Start[i] = X;71         push(X);72     }73     for (i = 2; i <= n; ++i)74         insert(abs(Start[i] - Start[i - 1]));75     char st[12];76     for (i = 1; i <= m; ++i){77         scanf("%s", st);78         if (st[0] == ‘I‘){79             p = read(), X = read();80             if (p != n){81                 t = abs(End[p] - Start[p + 1]);82                 --mp[t];83                 if (!mp[t]) a.erase(t);84             }85             insert(abs(End[p] - X));86             insert(abs(X - Start[p + 1]));87             End[p] = X;88             push(X);89         }else if (st[4] == ‘S‘) print(h.top());90         else print(*a.begin());91     }92     return 0;93 }