1058: [ZJOI2007]报表统计
Time Limit: 15 Sec Memory Limit: 162 MB Submit: 4099 Solved: 1390 [Submit][Status][Discuss]
Description
Input
Output
对于每一个“MIN_GAP”和“MIN_SORT_GAP”命令,输出一行答案即可。
Sample Input
Sample Output
HINT
N , M ≤500000 对于所有的数据,序列内的整数不超过5*10^8。
http://www.lydsy.com/JudgeOnline/problem.php?id=1058
- by bzoj
首先明确每次插入的位置可以通过简单的记录来快速得知,
然后分开考虑两种询问
1询问排序后的相邻元素间的最小差值,
如果维护排序后相邻元素间差值的话,元素的加入影响差值,应该是一个有加入有删除的操作,
而事实上由于每一次删除差值的诱因一定是新加入的元素夹在原来的两个元素之间,破坏了这两个元素间的差值,
这意味着删除的差值一定不如新产生的差值小,
于是可以视作没有删除;
那就是一个单纯比较取最小的过程了;
为了找到新产生了哪些差值,笔者这里选用了set对报表中的元素进行动态排序加二分查找;
这个询问的答案只会越来越小,最后可能到零,记得到零后记录一下,省一点多余的操作
2询问当前没有排序的序列的相邻元素的最小值,
如果维护未排序时相邻元素间差值的话,元素的加入影响差值,这里真的是一个有加入有删除的操作了;
每次在i与i+1间插入一个元素x,在维护差值的数据结构中找到abs(a[i+1]-a[i])删掉,然后加入abs(x-a[i])和abs(x-a[i+1]);
这里可以用平衡树维护
笔者这里偷懒直接用动态加点线段树做了,本来内存巨大应该过不了,遂偷偷改小数组,没想到竟然bzoj和luogu的数据都水过来了,暗爽
——现在写题解时想想,好像只要写个set维护就完事了
——结果就是道STL题啊!!!!!!!!!!!!
代码:
#include<map>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
map <int ,int >MAP;
int id_now[500010];
struct ss{
int num,las,nex;
}ctn[1000010];
struct DT{
int size,ch[2];
}data[10000000];
int top,tot,n,m;
bool flag;
char s[20];
inline void in(int &ans)
{
ans=0;bool p=false;char ch=getchar();
while((ch>'9' || ch<'0')&&ch!='-') ch=getchar();
if(ch=='-') p=true,ch=getchar();
while(ch<='9'&&ch>='0') ans=ans*10+ch-'0',ch=getchar();
if(p) ans=-ans;
}
void insert(int ,int ,int ,int ,int );
int get_MIN(int ,int ,int );
int main()
{
int i,j,k,ans2=1000000000;
map <int ,int > :: iterator iter;
in(n),in(m);
tot=n,top=1,flag=false;
for(i=1;i<=n;i++){
ctn[i].las=i-1;
ctn[i].nex=(i+1)%(n+1);
in(ctn[i].num);
if(ctn[i].las)
insert(0,1000000000,1,abs(ctn[i].num-ctn[ctn[i].las].num),1);
if(MAP.count(ctn[i].num)||flag)
flag=true;
else{
iter=MAP.upper_bound(ctn[i].num);
if(iter!=MAP.end())
ans2=min(ans2,iter->first-ctn[i].num);
if(iter!=MAP.begin())
iter--,ans2=min(ans2,ctn[i].num-iter->first);
MAP[ctn[i].num]=i;
}
id_now[i]=i;
}
for(i=1;i<=m;i++){
scanf("%s",s);
if(s[0]=='I'){
in(j),in(k);
ctn[++tot].num=k;
ctn[tot].nex=ctn[id_now[j]].nex;
ctn[ctn[id_now[j]].nex].las=tot;
ctn[tot].las=id_now[j];
ctn[id_now[j]].nex=tot;
ctn[0].nex=ctn[0].las=ctn[0].num=0;
if(ctn[tot].las)insert(0,1000000000,1,abs(k-ctn[ctn[tot].las].num),1);
if(ctn[tot].nex)insert(0,1000000000,1,abs(k-ctn[ctn[tot].nex].num),1);
if(ctn[tot].las&&ctn[tot].nex)insert(0,1000000000,1,abs(ctn[ctn[tot].las].num-ctn[ctn[tot].nex].num),-1);
if(!flag){
if(MAP.count(ctn[tot].num)){
flag=true,id_now[j]=tot;continue;
}
iter=MAP.upper_bound(k);
if(iter!=MAP.end())ans2=min(ans2,iter->first-k);
if(iter!=MAP.begin())iter--,ans2=min(ans2,k-iter->first);
MAP[k]=tot;
}
id_now[j]=tot;
}
if(s[0]=='M'&&s[4]=='G')
printf("%d\n",get_MIN(0,1000000000,1));
if(s[0]=='M'&&s[4]=='S')
printf("%d\n",(flag^1)*ans2);
}
return 0;
}
void insert(int l,int r,int now,int lim,int x){
int mid=(l+r)>>1;
if(l==r){
data[now].size+=x;
return ;
}
if(lim<=mid){
if(!data[now].ch[0])data[now].ch[0]=++top;
insert(l,mid,data[now].ch[0],lim,x);
}
else{
if(!data[now].ch[1])data[now].ch[1]=++top;
insert(mid+1,r,data[now].ch[1],lim,x);
}
data[now].size=data[data[now].ch[0]].size+data[data[now].ch[1]].size;
}
int get_MIN(int l,int r,int now){
if(l==r)return l;
int mid=(l+r)>>1;
if(data[data[now].ch[0]].size)
return get_MIN(l,mid,data[now].ch[0]);
else
return get_MIN(mid+1,r,data[now].ch[1]);
}