题目描述
小绝恋love 枫是一个出纳，经常需要做一些统计报表的工作。今天是绝恋love 枫的生日，小绝恋love 枫希望可以帮爸爸分担一些工作，作为他的生日礼物之一。经过仔细观察，小绝恋love 枫发现统计一张报表实际上是维护一个非负整数数列，并且进行一些查询操作。在最开始的时候，有一个长度为N 的整数序列，并且有以下三种操作：INSERT i k 在原数列的第i 个元素后面添加一个新元素k；如果原数列的第i 个元素已经添加了若干元素，则添加在这些元素的最后（见下面的例子）
MIN_GAP 查询相邻两个元素的之间差值（绝对值）的最小值
MIN_SORT_GAP 查询所有元素中最接近的两个元素的差值（绝对值）
例如一开始的序列为
5 3 1
执行操作INSERT 2 9 将得到：
5 3 9 1
此时MIN_GAP 为2，MIN_SORT_GAP 为2。
再执行操作INSERT 2 6 将得到：
5 3 9 6 1
注意这个时候原序列的第2 个元素后面已经添加了一个9，此时添加的6 应加在9 的后面。这个时候MIN_GAP 为2，MIN_SORT_GAP 为1。于是小绝恋love 枫写了一个程序，使得程序可以自动完成这些操作，但是他发现对于一些大的报表他的程序运行得很慢，你能帮助他改进程序么？
输入
第一行包含两个整数N,M，分别表示原数列的长度以及操作的次数。
第二行为N 个整数，为初始序列。
接下来的M 行每行一个操作，即“INSERT i k”，“MIN_GAP”，“MIN_SORT_GAP”中的一种（无多余空格或者空行）。
输出
对于每一个“MIN_GAP”和“MIN_SORT_GAP”命令，输出一行答案即可。
样例输入
3 5
5 3 1
INSERT 2 9
MIN_SORT_GAP
INSERT 2 6
MIN_GAP
MIN_SORT_GAP
样例输出
2
2
1
提示
对于30% 的数据，N≤1000,M≤5000
对于100% 的数据，N,M≤50000
对于所有的数据，序列内的整数不超过5*10^8。
题解
一道显而易见的数据结构题，在数据结构题里几乎算不用动脑子的那种。前后最小的一下子想到钢哥讲过的垃圾堆，维护两个堆就可以实现有效答案的添加和删除。原数列也可以用一个副本数组，只维护目前最靠前和最靠后的值(考试时忘了下一个位置的开头元素还需要记录，炸了不少分)。但是整个序列中最相近的两个元素，就有些犯难。明明知道就应该建个平衡树找前驱后继，尴尬的情况是平衡树只打过Treap，Treap只打过两道题，还是一两周之前的事了，考场上打挂可能性极大。权衡了一下，还是拿了个数组暴力排序，唯一的优化是如果最小值已经为0就不再改动。算上这道题平衡树也只打过三道，简直不能算做过题。书到用时方恨少，事非经过不知难，从第一次见到这句话到现在已经有些年了，理解倒是越来越深了= =。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<cstdlib>
#include<cmath>
using namespace std;
const int sj=;
int n,m,a[sj],a1,a2,mi,g,q,h,jq,hj,size,d[sj];
priority_queue<int,vector<int>,greater<int> > qi;
priority_queue<int,vector<int>,greater<int> > du;
char c[];
struct tree
{
int l,r,v,rnd;
}t[sj];
int bj(int x,int y)
{
return x<y?x:y;
}
void lturn(int &x)
{
int tt=t[x].r;
t[x].r=t[tt].l;
t[tt].l=x;
x=tt;
}
void rturn(int &x)
{
int tt=t[x].l;
t[x].l=t[tt].r;
t[tt].r=x;
x=tt;
}
void query_pre(int k,int x)
{
if(k==) return;
if(t[k].v<x)
{
q=k;
query_pre(t[k].r,x);
}
else query_pre(t[k].l,x);
}
void query_beh(int k,int x)
{
if(k==) return;
if(t[k].v>x)
{
h=k;
query_beh(t[k].l,x);
}
else query_beh(t[k].r,x);
}
void cr(int &x,int y)
{
if(x==)
{
size++;
x=size;
t[x].rnd=rand();
t[x].v=y;
return;
}
if(t[x].v==y)
{
jq=hj=y;
q=h=;
return;
}
if(y>t[x].v)
{
cr(t[x].r,y);
if(t[x].rnd>t[t[x].r].rnd) lturn(x);
}
if(y<t[x].v)
{
cr(t[x].l,y);
if(t[x].rnd>t[t[x].l].rnd) rturn(x);
}
}
void init()
{
scanf("%d%d",&n,&m);
mi=0x7fffffff;
for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);
if(i!=) qi.push(abs(a[i]-a[i-]));
if(mi)
{
q=h=-;
jq=hj=;
cr(g,a[i]);
if(q==-)
{
query_beh(g,a[i]);
query_pre(g,a[i]);
if(q!=-||h!=-)
{
jq=(q==-)?0x7fffffff:t[q].v;
hj=(h==-)?0x7fffffff:t[h].v;
mi=bj(mi,abs(a[i]-jq));
mi=bj(mi,abs(a[i]-hj));
}
}
else mi=;
}
memcpy(d,a,sizeof(a));
}
}
void cl()
{
for(int i=;i<=m;i++)
{
scanf("%s",c);
if(c[]=='R')
{
scanf("%d%d",&a1,&a2);
if(a1!=n)
{
qi.push(abs(a2-a[a1+]));
du.push(abs(a[a1+]-d[a1]));
}
qi.push(abs(a2-d[a1]));
d[a1]=a2;
if(mi)
{
q=h=-;
jq=hj=;
cr(g,a2);
if(q==-)
{
query_beh(g,a2);
query_pre(g,a2);
if(q!=-||h!=-)
{
jq=(q==-)?0x7fffffff:t[q].v;
hj=(h==-)?0x7fffffff:t[h].v;
mi=bj(mi,abs(a2-jq));
mi=bj(mi,abs(a2-hj));
}
}
else mi=;
}
}
if(c[]=='G')
{
while(!qi.empty()&&!du.empty()&&qi.top()==du.top())
{
qi.pop();
du.pop();
}
printf("%d\n",qi.top());
}
if(c[]=='S') printf("%d\n",mi);
}
}
int main()
{
init();
cl();
return ;
}
love
在cogs上看到了这题，交了一下RE，发现数据范围是十倍……调了数组大小再交一遍，居然TLE了！据说堆可能会炸掉，不得已又改成了线段树。跑得确实快了，可是比堆难写得多啊。差点上两百行【抵制恶意缩行不良风气，从我做起！
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
using namespace std;
const int sj=;
int n,m,a[sj],a1,a2,mi,g,q,h,jq,hj,size,d[sj],last;
struct xs
{
int v,l,r;
}xds[sj*];
char c[];
struct tree
{
int l,r,v,rnd;
}t[sj];
int bj(int x,int y)
{
return x<y?x:y;
}
void lturn(int &x)
{
int tt=t[x].r;
t[x].r=t[tt].l;
t[tt].l=x;
x=tt;
}
void rturn(int &x)
{
int tt=t[x].l;
t[x].l=t[tt].r;
t[tt].r=x;
x=tt;
}
void query_pre(int k,int x)
{
if(k==) return;
if(t[k].v<x)
{
q=k;
query_pre(t[k].r,x);
}
else query_pre(t[k].l,x);
}
void query_beh(int k,int x)
{
if(k==) return;
if(t[k].v>x)
{
h=k;
query_beh(t[k].l,x);
}
else query_beh(t[k].r,x);
}
void cr(int &x,int y)
{
if(x==)
{
size++;
x=size;
t[x].rnd=rand();
t[x].v=y;
return;
}
if(t[x].v==y)
{
jq=hj=y;
q=h=;
return;
}
if(y>t[x].v)
{
cr(t[x].r,y);
if(t[x].rnd>t[t[x].r].rnd) lturn(x);
}
if(y<t[x].v)
{
cr(t[x].l,y);
if(t[x].rnd>t[t[x].l].rnd) rturn(x);
}
}
void build(int x,int z,int y)
{
xds[x].l=z;
xds[x].r=y;
xds[x].v=0x7fffffff;
if(z==y) return;
int mid=(z+y)>>;
build(x<<,z,mid);
build((x<<)|,mid+,y);
}
void update(int x,int z,int y)
{
if(xds[x].l==xds[x].r&&xds[x].l==z)
{
xds[x].v=y;
return;
}
int mid=(xds[x].l+xds[x].r)>>;
if(z<=mid)
{
update(x<<,z,y);
xds[x].v=bj(xds[(x<<)|].v,xds[x<<].v);
}
else
{
update((x<<)|,z,y);
xds[x].v=bj(xds[(x<<)|].v,xds[x<<].v);
}
}
void init()
{
scanf("%d%d",&n,&m);
mi=0x7fffffff;
build(,,sj*-);
for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);
if(i!=) update(,i-,abs(a[i]-a[i-]));
if(mi)
{
q=h=-;
jq=hj=;
cr(g,a[i]);
if(q==-)
{
query_beh(g,a[i]);
query_pre(g,a[i]);
if(q!=-||h!=-)
{
jq=(q==-)?0x7fffffff:t[q].v;
hj=(h==-)?0x7fffffff:t[h].v;
mi=bj(mi,abs(a[i]-jq));
mi=bj(mi,abs(a[i]-hj));
}
}
else mi=;
}
}
memcpy(d,a,sizeof(a));
last=n-;
}
void cl()
{
for(int i=;i<=m;i++)
{
scanf("%s",c);
if(c[]=='R')
{
scanf("%d%d",&a1,&a2);
last++;
update(,last,abs(a2-d[a1]));
update(,a1,abs(a2-a[a1+]));
d[a1]=a2;
if(mi)
{
q=h=-;
jq=hj=;
cr(g,a2);
if(q==-)
{
query_beh(g,a2);
query_pre(g,a2);
if(q!=-||h!=-)
{
jq=(q==-)?0x7fffffff:t[q].v;
hj=(h==-)?0x7fffffff:t[h].v;
mi=bj(mi,abs(a2-jq));
mi=bj(mi,abs(a2-hj));
}
}
else mi=;
}
}
if(c[]=='G') printf("%d\n",xds[].v);
if(c[]=='S') printf("%d\n",mi);
}
}
int main()
{
init();
cl();
return ;
}
form