P1110 [ZJOI2007] 报表统计

题目描述

小 Q 的妈妈是一个出纳，经常需要做一些统计报表的工作。今天是妈妈的生日，小 Q 希望可以帮妈妈分担一些工作，作为她的生日礼物之一。

经过仔细观察，小 Q 发现统计一张报表实际上是维护一个非负整数数列，并且进行一些查询操作。

在最开始的时候，有一个长度为 n 的整数序列 a，并且有以下三种操作：

INSERT i k：在原数列的第 i 个元素后面添加一个新元素 k；如果原数列的第 i 个元素已经添加了若干元素，则添加在这些元素的最后（见样例说明）。
MIN_GAP：查询相邻两个元素的之间差值（绝对值）的最小值。
MIN_SORT_GAP：查询所有元素中最接近的两个元素的差值（绝对值）。

于是小 Q 写了一个程序，使得程序可以自动完成这些操作，但是他发现对于一些大的报表他的程序运行得很慢，你能帮助他改进程序么？

输入格式

第一行包含两个整数，分别表示原数列的长度 n 以及操作的次数 m。

第二行为 n 个整数，为初始序列，第 i 个整数表示 ai。

接下来的 m 行，每行一个操作，即INSERT i k，MIN_GAP，MIN_SORT_GAP 中的一种（无多余空格或者空行）。

输出格式

对于每一个 MIN_GAP 和 MIN_SORT_GAP 命令，输出一行答案即可。

输入输出样例

输入 #1复制

3 5
5 3 1
INSERT 2 9
MIN_SORT_GAP
INSERT 2 6
MIN_GAP
MIN_SORT_GAP

输出 #1复制

2
2
1

说明/提示

样例输入输出 1 解释

一开始的序列为 {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。

数据规模与约定

对于全部的测试点，保证 2≤n,m≤5×105，1≤i≤n，0≤ai,k≤5×108。

看了半天怎么就没有Splay+堆的题解呢。。
题意是很简单的。。
就是一开始有n个元素，每个元素相当于一个队列，总的序列是所有队列按顺序拼接起来的序列，有下面三种操作。
操作一：在原序列第k个队列插入一个x
操作二：查询总序列里面相邻元素的差值的绝对值的最小值。
操作三：查询总序列里面所有元素差值的绝对值的最小值。

第一个操作应该是建立在二，三操作的基础上进行的。。
我们先对二，三操作进行讨论。

第三个操作比较简单，我们只要建立一个平衡树，每次插入元素之后，查询这个元素和排名相邻的元素的差值，然后统计出最小值就可以了。

重点是第二个操作。
发现如果我们插入一个元素，这个元素会打破一对元素的相邻关系，并且建立两队相邻关系，每次的答案就是所有的相邻关系中差值最小的一对。
差值最小的一对很容易用堆来维护，我们的问题就变成了维护一个可以删除的堆。

这个堆也很容易实现。。
我们开两个堆，第一个堆储存已经插入的数，第二个堆储存已经删除的数，每次弹出时我们只需要判断两堆的堆顶是不是一样，如果一样就同时弹掉，直到堆顶不一样。

那么第一个操作就是这两个操作的结合了吧。。不讲了。。
注意平衡树判断前驱，后继的时候要注意判断当前元素是否有多个，如果有多个的话说明最小值是零。

同时有一个卡常小技巧。。
最小值是一直向着0贴近的，不会变成负数也不会变大，所以当我们发现最小值变成0的时候，我们就不需要再进行平衡树操作了（卡了这个之后我代码快了700ms）。
当然最开始的时候我们要对所有的数据进行初始化，确定每个数据在最终的数组中的位置。(不然用vector好像也是可以的，没试过，你们可以去试试）

下面就直接贴代码（常熟巨大不开氧气2336ms,开了氧气也是830ms）

#include <bits/stdc++.h>
#define fa(x) tree[x].fa
#define son(x,k) tree[x].ch[k]
#define cnt(x) tree[x].cnt
#define val(x) tree[x].val
#define siz(x) tree[x].siz
using namespace std;
const int N=5e6+1009;
const int inf=(1<<31)-1;
struct Hp{
	priority_queue<int>q1,q2;
	Hp(){
		while(!q1.empty())q1.pop();
		while(!q2.empty())q2.pop();
	}
	void Insert(int x){
		q1.push(-x);
	}
	void Delete(int x){
		q2.push(-x);
	}
	int Top(){
		while(!q2.empty()&&!q1.empty()){
			if(q1.top()!=q2.top())return -q1.top();
			q1.pop();q2.pop();
		}
	}
}Heap;
int read(){
	char c;int num,f=1;
	while(c=getchar(),!isdigit(c))if(c=='-')f=-1;num=c-'0';
	while(c=getchar(), isdigit(c))num=num*10+c-'0';
	return f*num;
}
int abs(int x){return x<0?-x:x;}
int rt,tot;
int n,m,pos[N],minn=(1<<31)-1;
int ord[N][10],a[N],b[N];

struct Node{
    int fa,ch[2],siz,cnt,val;
}tree[N];
bool chk(int x){return son(fa(x),1)==x;}
void update(int x){siz(x)=siz(son(x,0))+siz(son(x,1))+cnt(x);}
int New(int x,int pre){
    tot++;
    if(pre)son(pre,x>val(pre))=tot;
    son(tot,0)=son(tot,1)=0;
    cnt(tot)=siz(tot)=1;
    val(tot)=x;fa(tot)=pre;
    return tot;
}
void rotate(int x){
    int y=fa(x),z=fa(y),k=chk(x);
    son(z,chk(y))=x;fa(x)=z;
    son(y,k)=son(x,k^1);fa(son(x,k^1))=y;
    son(x,k^1)=y;fa(y)=x;
    update(y);update(x);
}
void splay(int x,int goal=0){
    while(fa(x)!=goal){
        int y=fa(x),z=fa(y);
        if(z!=goal){
            if(chk(y)==chk(x))rotate(y);
            else rotate(x);
        }
        rotate(x);
    }
    if(!goal)rt=x;
}
void Insert(int x){
    int cur=rt,p=0;
    while(cur&&val(cur)!=x)
        p=cur,cur=son(cur,x>val(cur));
    if(cur)cnt(cur)++;
    else cur=New(x,p);
    splay(cur);
}
void Find(int x){
    if(!rt)return ;
    int cur=rt;
    while(son(cur,x>val(cur))&&val(cur)!=x)
        cur=son(cur,x>val(cur));
    splay(cur);
}
int Pre(int x){
    Find(x);
    if(val(rt)<x||(val(rt)==x&&cnt(rt)>1))return rt;
    int cur=son(rt,0);
    while(son(cur,1))cur=son(cur,1);
    return cur;
}
int Succ(int x){
    Find(x);
    if(val(rt)>x||(val(rt)==x&&cnt(rt)>1))return rt;
    int cur=son(rt,1);
    while(son(cur,0))cur=son(cur,0);
    return cur;
}
int main()
{
	n=read();m=read();
	Insert(inf);Insert(-inf);
	for(int i=1;i<=n;i++){
		int x=read();
		pos[i]=x;
		b[i]++;
	}
	for(int i=1;i<=m;i++){
		char c[19];
		scanf("%s",c);
		int len=strlen(c);
		if(len==6){
			ord[i][0]=1;
			ord[i][1]=read();
			ord[i][2]=read();
			b[ord[i][1]]++;
			ord[i][3]=b[ord[i][1]];
		}else if(len==7)ord[i][0]=2;
		else ord[i][0]=3;
	}
	for(int i=1;i<=n;i++){
		if(i!=1)Heap.Insert(abs(pos[i]-pos[i-1]));
		if(minn!=0){
			Insert(pos[i]);
			int xx=val(Succ(pos[i])),yy=val(Pre(pos[i]));
			if(xx!=inf&&xx!=-inf)minn=min(minn,xx-pos[i]);
			if(yy!=inf&&yy!=-inf)minn=min(minn,pos[i]-yy);
		}
		a[b[i-1]+1]=pos[i];
		b[i]+=b[i-1];
	}
	for(int i=1;i<=m;i++){
		if(ord[i][0]==1){
			if(minn!=0) Insert(ord[i][2]);
			a[b[ord[i][1]-1]+ord[i][3]]=ord[i][2];
			
			Heap.Insert(abs(a[b[ord[i][1]-1]+ord[i][3]]-a[b[ord[i][1]-1]+ord[i][3]-1]));
			Heap.Insert(abs(a[b[ord[i][1]-1]+ord[i][3]]-a[b[ord[i][1]]+1]));
			Heap.Delete(abs(a[b[ord[i][1]]+1]-a[b[ord[i][1]-1]+ord[i][3]-1]));
			if(minn!=0){
				int xx=val(Succ(ord[i][2])),yy=val(Pre(ord[i][2]));
				if(xx!=inf&&xx!=-inf)minn=min(minn,xx-ord[i][2]);
				if(yy!=inf&&yy!=-inf)minn=min(minn,ord[i][2]-yy);
			}
		}else if(ord[i][0]==2)
			printf("%d
",Heap.Top());
		else printf("%d
",minn);
	}
	return 0;
}

文章版权归作者所有，未经允许请勿转载。如内容涉嫌侵权，请在本页底部进入<联系我们>进行举报投诉!

THE END