洛谷P1110\BZOJ1058 [ZJOI2007]报表统计

题目传送门：洛谷P1110\BZOJ1058 [ZJOI2007]报表统计

想法

引入

第一次看见这个题：想了一会，woc，三颗平衡树，好麻烦呀，先放一放。

第二次看见这个题：想了一会，woc，平衡树加线段树，好麻烦呀，先放一放。

第三次看见这个题：想了一会，woc，一棵权值平衡树加一棵位置平衡树，好麻烦呀，先放一放。

第四次看见这个题：想了一会，woc，一棵平衡树加堆，好麻烦呀……诶等等，好像可以就开两个差不多的平衡树就行了……

---

写的时候脑袋有点懵，不过还是肝好了呢。

解法

当他插入的时候，显然可以发现，就是在堆里面删除元素：$abs(head[id+1]-tail[id])$；然后插入两个新元素：$abs(head[id+1]-new)$，$abs(new-tail[id])$。然后新的 $tail[id]$ 再附上 $new$。每次询问 $MIN\_GAP$ 就是询问堆里面的最小值了。

支持删除，插入，查询权值最小，显然可以用平衡树去搞。

对于第二种询问，单独插入一个元素，我们需要在集合里面查找他的前驱和后继，便可以计算最小的差值，显然这个询问的答案是单调的，所以我们开全局变量去记录。

支持插入，查前驱，查后继，显然可以又用平衡树去搞。

这里我用了我喜欢的$Fhq\_Treap$，然后前驱后继是直接查的，其实可以通过$pushup$上传最大最小值，但是不知道为什么会慢一点，然后卡了会儿常，代码有点丑：

代码

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cstdio>
#include<vector>
#include<string>
#include<queue>
#include<stack>
#include<cmath>
#include<ctime>
#include<map>
#include<set>
using namespace std;
const int inf=0x7fffffff;
const double eps=1e-10;
const double pi=acos(-1.0);
//char buf[1<<15],*S=buf,*T=buf;
//char getch(){return S==T&&(T=(S=buf)+fread(buf,1,1<<15,stdin),S==T)?0:*S++;}
inline int read(){
  int x=0,f=1;char ch;ch=getchar();
  while(ch<'0'||ch>'9'){if(ch=='-') f=0;ch=getchar();}
  while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch&15);ch=getchar();}
  if(f)return x;else return -x;
}
const int N=1000010;
int ans=inf;
inline int Abs(const int &a){if(a<0)return -a;return a;}
inline int min(const int &a,const int &b){if(a<b)return a;return b;}
inline int max(const int &a,const int &b){if(a>b)return a;return b;}
struct fhq_treap_val{
  #define lson ls[rt]
  #define rson rs[rt]
  int val[N],size[N],key[N];
  int ls[N],rs[N];
  int root,cnt;
  void pushup(int rt){size[rt]=size[lson]+size[rson]+1;}
  int merge(int a,int b){
    if(!a||!b)return a|b;
    if(key[a]<key[b]){rs[a]=merge(rs[a],b);pushup(a);return a;}
    else {ls[b]=merge(a,ls[b]);pushup(b);return b;}
  }
  void split(int rt,int x,int &a,int &b){
    if(!rt){a=b=0;return;}
    if(val[rt]<=x){a=rt;split(rson,x,rson,b);}
    else{b=rt;split(lson,x,a,lson);}
    pushup(rt);
  }
  int Max(int rt){while(rson)rt=rson;return val[rt];}
  int Min(int rt){while(lson)rt=lson;return val[rt];}
  int newnode(int x){
    int rt=++cnt;
    val[rt]=x;
    size[rt]=1;key[rt]=rand();
    lson=rson=0;
    return rt;
  }
  void Insert(int x){
    int a,b;
    split(root,x,a,b);
    int rt=newnode(x);
    root=merge(merge(a,rt),b);
  }
  void Insert_2(int x){
    int a,b;
    split(root,x,a,b);
    if(size[a])ans=min(ans,abs(x-Max(a)));
    if(size[b])ans=min(ans,abs(Min(b)-x));
    int rt=newnode(x);
    root=merge(merge(a,rt),b);
  }
  void Delete(int x){
    int a,b,c;
    split(root,x,a,c);
    split(a,x-1,a,b);
    b=merge(ls[b],rs[b]);
    root=merge(merge(a,b),c);
  }
}T1,T2;
int n,m,a[N],b[N],id,g;
char op[20];
int main()
{
  srand(time(NULL));
  n=read();m=read();
  for(int i=1;i<=n;i++)a[i]=b[i]=read();
  for(int i=1;i<n;i++)T1.Insert(Abs(a[i+1]-a[i]));
  for(int i=1;i<=n;i++)T2.Insert_2(a[i]);
  while(m--){
    scanf("%s",op);
    if(op[0]=='I'){
      id=read();g=read();
      T2.Insert_2(g);
      if(id!=n){
        T1.Delete(Abs(a[id+1]-b[id]));
        T1.Insert(Abs(a[id+1]-g));
      }
      T1.Insert(Abs(b[id]-g));
      b[id]=g;
    }
    else if(op[4]=='G')printf("%d\n",T1.Min(T1.root));
    else printf("%d\n",ans);
  }
  return 0;
}