嘟嘟嘟
这几天复习一下数据结构，要不就忘了。
这题据说能拿STL水过，但是我仍是写了一发splay。
对于第一个询问，我确实是拿vector + multiset水过去的。但是第二问我还是写了个splay，支持插入和查找前驱和后继。
splay的数组别忘开二倍，因为最终可能有(n + m)个元素。
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
#include<set>
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define In inline
typedef long long ll;
typedef double db;
const int INF = 2147483647;
const db eps = 1e-8;
const int maxn = 5e5 + 5;
inline ll read()
{
ll ans = 0;
char ch = getchar(), last = ' ';
while(!isdigit(ch)) last = ch, ch = getchar();
while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
if(last == '-') ans = -ans;
return ans;
}
inline void write(ll x)
{
if(x < 0) x = -x, putchar('-');
if(x >= 10) write(x / 10);
putchar(x % 10 + '0');
}
char s0[20];
int n, m, Min = INF;
vector<int> v[maxn];
multiset<int> s;
#define snew multiset<int>::iterator
In void update(int pos, int x)
{
if(pos ^ n)
{
int tp = abs(v[pos + 1][0] - *(v[pos].end() - 1));
snew it = s.find(tp); s.erase(it);
}
int tp = *(v[pos].end() - 1);
v[pos].push_back(x);
s.insert(abs(tp - x));
if(pos ^ n) s.insert(abs(v[pos + 1][0] - x));
}
struct Tree
{
int ch[2], fa;
int val, cnt;
}t[maxn << 1];
int root, tcnt = 0;
In void rotate(int x)
{
int y = t[x].fa, z = t[y].fa, k = (t[y].ch[1] == x);
t[z].ch[t[z].ch[1] == y] = x, t[x].fa = z;
t[y].ch[k] = t[x].ch[k ^ 1], t[t[y].ch[k]].fa = y;
t[x].ch[k ^ 1] = y, t[y].fa = x;
}
In void splay(int x, int s)
{
while(t[x].fa != s)
{
int y = t[x].fa, z = t[y].fa;
if(z ^ s) rotate(((t[y].ch[0] == x) ^ (t[z].ch[0] == y)) ? x : y);
rotate(x);
}
if(!s) root = x;
}
In bool insert(int x)
{
bool flg = 0;
int now = root, f = 0;
while(now && x != t[now].val) f = now, now = t[now].ch[x > t[now].val];
if(now) ++t[now].cnt, flg = 1;
{
now = ++tcnt;
if(f) t[f].ch[x > t[f].val] = now;
t[now].fa = f;
t[now].ch[0] = t[now].ch[1] = 0;
t[now].val = x, t[now].cnt = 1;
}
splay(now, 0);
return flg;
}
In void find(int x)
{
int now = root;
while(t[now].ch[x > t[now].val] && t[now].val != x) now = t[now].ch[x > t[now].val];
splay(now, 0);
}
In int pre(int x)
{
find(x);
int now = t[root].ch[0];
while(t[now].ch[1]) now = t[now].ch[1];
return t[now].val;
}
In int nxt(int x)
{
find(x);
int now = t[root].ch[1];
while(t[now].ch[0]) now = t[now].ch[0];
return t[now].val;
}
In void _PrintAll()
{
for(int i = 1; i <= n; ++i)
for(int j = 0; j < (int)v[i].size(); ++j) printf("%d ", v[i][j]); enter;
}
int main()
{
//freopen("ha.in", "r", stdin);
//freopen("ha.out", "w", stdout);
n = read(), m = read(); insert(-INF), insert(INF);
for(int i = 1; i <= n; ++i)
{
int x = read();
v[i].push_back(x);
if(i > 1) s.insert(abs(v[i][0] - v[i - 1][0]));
if(Min == 0) continue;
if(insert(x)) Min = 0;
else
{
int a = pre(x), b = nxt(x);
Min = min(Min, min(abs(a - x), abs(b - x)));
}
}
for(int i = 1; i <= m; ++i)
{
scanf("%s", s0);
if(s0[0] == 'I')
{
int pos = read(), x = read();
update(pos, x);
if(Min == 0) continue;
if(insert(x)) Min = 0;
else
{
int a = pre(x), b = nxt(x);
Min = min(Min, min(abs(a - x), abs(b - x)));
}
}
else if(s0[4] == 'G') write(*s.begin()), enter;
else write(Min), enter;
//_PrintAll();
}
return 0;
}