题目链接

思路

set+map+优先队列就可以水过去。可以发现，每插入一个元素，都会使得操作2中原来相邻的那个差值消失，然后多了两个新的差值。对于新的差值，只要直接扔到优先队列里就好了。那么删除呢。可以用map记录一下当前元素被删除了多少次。然后查询的时候将被删除的跳过即可。对于操作3，只要将插入的数都扔到set里，然后每次插入都找出当前点的前驱后继，并用ans记录下最优的。查询的时候直接输出ans即可。

为了证明自己真的有在练习平衡树，写了个splay代替set，然后跑的比set还慢2333。还可以再写一棵平衡树，来代替map+优先队列的操作。

STL代码

/*

* @Author: wxyww

* @Date:   2018-12-09 19:19:23

* @Last Modified time: 2018-12-09 19:56:45

*/

#include<cstdio>

#include<iostream>

#include<cstdlib>

#include<set>

#include<cstring>

#include<cmath>

#include<map>

#include<ctime>

#include<queue>

#include<bitset>

using namespace std;

typedef long long ll;

const int N = 1000000 + 100,INF = 1e9;

map<int,int>ma;

priority_queue<int,vector<int>,greater<int> >q;

set<int>s;

ll read() {

   ll x=0,f=1;char c=getchar();

   while(c<'0'||c>'9') {

      if(c=='-') f=-1;

      c=getchar();

   }

   while(c>='0'&&c<='9') {

      x=x*10+c-'0';

      c=getchar();

   }

   return x*f;

}

int a[N],lianbiao[N],now[N];

char c[20];

set<int>::iterator k1,k2;

int ans1 = INF,ans2 = INF;

int main() {

   int n = read(),m = read();

   memset(a,-0x3f,sizeof(a));

   s.insert(-INF);s.insert(INF);

   for(int i = 1;i <= n;++i) {

      a[i] = read();

      lianbiao[i - 1] = i;

      k1 = --s.lower_bound(a[i]);k2 = s.lower_bound(a[i]);

      ans2 = min(ans2,min(abs(*k1 - a[i]),abs(*k2 - a[i])));

      q.push(abs(a[i] - a[i - 1]));

      s.insert(a[i]);

      now[i] = i;

   }

   while(m--) {

      scanf("%s",c + 1);

      if(c[1] == 'I') {

         int pos = read();

         a[++n] = read();

         int k = now[pos];

         ma[abs(a[k] - a[lianbiao[k]])]++;

         q.push(abs(a[n] - a[k]));q.push(abs(a[n] - a[lianbiao[k]]));

         k1 = --s.lower_bound(a[n]);k2 = s.lower_bound(a[n]);

         ans2 = min(ans2,min(abs(*k1 - a[n]),abs(*k2 - a[n])));

         s.insert(a[n]);

         now[pos] = n;

         lianbiao[n] = lianbiao[k];

         lianbiao[k] = n;

      }

      else if(c[6] == 'A') {

         int z = q.top();

         while(ma[z]) {

            q.pop();

            ma[z]--;

            z = q.top();

         }

         printf("%d\n",z);

      }

      else printf("%d\n",ans2);

   }

   return 0;

}

splay代码

/*

* @Author: wxyww

* @Date:   2018-12-09 16:29:51

* @Last Modified time: 2018-12-09 20:32:00

*/

#include<cstdio>

#include<iostream>

#include<cstdlib>

#include<cmath>

#include<cstring>

#include<map>

#include<queue>

#include<ctime>

#include<bitset>

using namespace std;

#define ls TR[cur].ch[0]

#define rs TR[cur].ch[1]

typedef long long ll;

const int N = 1000000 + 100,INF = 1e9;

ll read() {

   ll x=0,f=1;char c=getchar();

   while(c<'0'||c>'9') {

      if(c=='-') f=-1;

      c=getchar();

   }

   while(c>='0'&&c<='9') {

      x=x*10+c-'0';

      c=getchar();

   }

   return x*f;

}

struct node {

   int ch[2],val,siz,pre,cnt;

}TR[N];

inline void up(int cur) {

   TR[cur].siz = TR[ls].siz + TR[rs].siz + TR[cur].cnt;

}

int tot,rt;

inline int getwh(int cur) {

   return TR[TR[cur].pre].ch[1] == cur;

}

inline void rotate(int cur) {

   int f = getwh(cur),fa = TR[cur].pre,gr = TR[fa].pre;

   TR[cur].pre = gr;

   TR[gr].ch[getwh(fa)] = cur;

   TR[TR[cur].ch[f ^ 1]].pre = fa;

   TR[fa].ch[f] = TR[cur].ch[f ^ 1];

   TR[fa].pre = cur;

   TR[cur].ch[f ^ 1] = fa;

   up(fa);up(cur);

}

void splay(int cur,int to) {

   while(TR[cur].pre != to) {

      if(TR[TR[cur].pre].pre != to) {

         if(getwh(cur) == getwh(TR[cur].pre)) rotate(TR[cur].pre);

         else rotate(cur);

      }

      rotate(cur);

   }

   if(!to) rt = cur;

}

void insert(int cur,int val,int father) {

   if(!cur) {

      cur = ++tot;

      TR[cur].pre = father;

      TR[cur].val = val;

      TR[cur].siz = TR[cur].cnt = 1;

      TR[father].ch[val > TR[father].val] = cur;

      splay(cur,0);

      return;

   }

   TR[cur].siz++;

   if(val == TR[cur].val) {TR[cur].cnt++;return;}

   insert(TR[cur].ch[val > TR[cur].val],val,cur);

}

inline int getpos(int val) {

   int cur = rt,lst;

   while(cur) {

      lst = cur;

      if(TR[cur].val == val) return cur;

      if(val > TR[cur].val) cur = rs;

      if(val < TR[cur].val) cur = ls;

   }

   return lst;

}

inline int pred(int val) {

   int cur = getpos(val);

   if(TR[cur].val <= val) return TR[cur].val;

   splay(cur,0);

   cur = ls;

   while(rs) cur = rs;

   return TR[cur].val;

}

inline int nex(int val) {

   int cur = getpos(val);

   if(TR[cur].val >= val) return TR[cur].val;

   splay(cur,0);

   cur = rs;

   while(ls) cur = ls;

   return TR[cur].val;

}

int a[N],lianbiao[N],now[N];

char c[20];

int ans1 = INF,ans2 = INF;

map<int,int>ma;

priority_queue<int,vector<int>,greater<int> >q;

int main() {

   int n = read(),m = read();

   memset(a,-0x3f,sizeof(a));

   insert(rt,-INF,0);insert(rt,INF,0);

   for(int i = 1;i <= n;++i) {

      a[i] = read();

      lianbiao[i - 1] = i;

      // puts("!!");

      int k1 = pred(a[i]),k2 = nex(a[i]);

      ans2 = min(ans2,min(abs(k1 - a[i]),abs(k2 - a[i])));

      q.push(abs(a[i] - a[i - 1]));

      insert(rt,a[i],0);

      now[i] = i;

   }

   while(m--) {

      scanf("%s",c + 1);

      if(c[1] == 'I') {

         int pos = read();

         a[++n] = read();

         int k = now[pos];

         ma[abs(a[k] - a[lianbiao[k]])]++;

         q.push(abs(a[n] - a[k]));q.push(abs(a[n] - a[lianbiao[k]]));

         int k1 = pred(a[n]),k2 = nex(a[n]);

         ans2 = min(ans2,min(abs(k1 - a[n]),abs(k2 - a[n])));

         insert(rt,a[n],0);

         now[pos] = n;

         lianbiao[n] = lianbiao[k];

         lianbiao[k] = n;

      }

      else if(c[6] == 'A') {

         int z = q.top();

         while(ma[z]) {

            q.pop();

            ma[z]--;

            z = q.top();

         }

         printf("%d\n",z);

      }

      else printf("%d\n",ans2);

   }

   return 0;

}

一言

积极者相信只有推动自己才能推动世界，只要推动自己就能推动世界。