题解 P1110 【[ZJOI2007]报表统计】
Treeloveswater
2017-05-06 19:30:16
超级大水题。竟然是省选难度的？
一棵无比简单的连update都不用写的splay+一个带删除的堆，完美搞定。
操作一：没必要搞一棵splay。我们只用开一个lq[500001][2]的数组记录这个点的前面和后面就行。
操作二：带修改的小根堆
操作三：把所有数扔到splay里，按大小为关键字，再插入的时候取个max的差值就好了。
完美解决，特别好写~
完结，撒花~
```cpp
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int tot,n,m,a,k,minans=1e7;
struct node
{
int data;
node *son[2],*pre;
bool judge();
void setson(node *child,int lr);
}pool[1000001],*null,*root;
int heap1[1500001],delheap[1000001],lq[500001][3];
char s[25];
bool node::judge(){return pre->son[1]==this;}
void node::setson(node *child,int lr){son[lr]=child;if(child!=null)child->pre=this;}
node *getnew(int value)
{
node *now=pool+ ++tot;
now->data=value;
now->pre=now->son[1]=now->son[0]=null;
return now;
}
int ab(int x)
{
return x<0?-x:x;
}
void rotate(node *&now)
{
node *dad=now->pre,*grandfa=now->pre->pre;
int lr=now->judge();
dad->setson(now->son[lr^1],lr);
now->setson(dad,lr^1);
now->pre=grandfa;
if(grandfa!=null) grandfa->son[grandfa->son[1]==dad?1:0]=now;
}
void splay(node *now,node *tar)
{
for(;now->pre!=null;rotate(now))
if(now->pre->pre!=tar)
now->judge()==now->pre->judge()?rotate(now->pre):rotate(now);
if(tar==null)root=now;
}
void in(int *heap,int value)
{
heap[++heap[0]]=value;
int now=heap[0],nxt;
while(now>1)
{
nxt=now>>1;
if(heap[nxt]<heap[now])break;
swap(heap[nxt],heap[now]);
now=nxt;
}
}
void del(int *heap)
{
heap[1]=heap[heap[0]--];
int now=1,nxt;
while(now*2<=heap[0])
{
nxt=now<<1;
if(heap[nxt]>heap[nxt+1]&&nxt<heap[0])nxt++;
if(heap[now]<heap[nxt])break;
swap(heap[now],heap[nxt]);
now=nxt;
}
}
void insert(int value)
{
node *newone=getnew(value);
node *now=root,*last=null;
while(now!=null)
{
last=now;
if(ab(newone->data-now->data)<minans)minans=ab(newone->data-now->data);
if(now->data>=newone->data) now=now->son[0];
else now=now->son[1];
}
if(last==null) root=newone;
else
{
if(ab(newone->data-last->data)<minans)minans=ab(newone->data-last->data);
if(last->data>=newone->data) last->setson(newone,0);
else last->setson(newone,1);
}
}
int main()
{
null=pool;
null->data=0;
null->pre=null->son[1]=null->son[0]=null;
root=null;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&lq[i][1]);
lq[i][2]=lq[i][1];
if(i>1)in(heap1,ab(lq[i][1]-lq[i-1][2]));
insert(lq[i][1]);
}
for(int i=1;i<=m;i++)
{
scanf("%s",s);
if(s[0]=='I')
{
scanf("%d%d",&a,&k);
if(a<n)
{
in(delheap,ab(lq[a][2]-lq[a+1][1]));
in(heap1,ab(k-lq[a+1][1]));
}
in(heap1,ab(k-lq[a][2]));
lq[a][2]=k;
insert(k);
}
else
{
int length=strlen(s);
if(length<10)
{
while(heap1[1]==delheap[1])
{
del(heap1);
del(delheap);
}
printf("%d\n",heap1[1]);
}
else
printf("%d\n",minans);
}
}
}
```