Luogu P1110 [ZJOI2007]报表统计 题解

Describe

题目链接

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

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

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

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

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

Solution

开两个multiset即可。

一个存放所有元素的最小差值,一个存放相邻元素的最小差值。

每次插入一个数字可以处理下前驱和后继即可。

细节详见代码。

P.S.千万不要作死用vector.

Code

#include<bits/stdc++.h>
#define It multiset<int>::iterator
#define inf 2000000010//inf不要太小哦
using namespace std;
inline int read(){
	int res=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar();
	return res*f;
}
inline void write(int x){
	if(x<0) x=-x,putchar('-');
	if(x<10) putchar(x+'0');
	else write(x/10),putchar(x%10+'0');
}
int n,m,Min=inf,las,nxt,tmp,a[500010],b[500010];//a,b分别表示每一段的开头与结尾
multiset<int> v,d;//v表示全部,d表示相邻
char c;
int main(){
	n=read();m=read();
	for(int i=1;i<=n;i++) a[i]=b[i]=read(),v.insert(a[i]);
	v.insert(inf);v.insert(-inf);//防止奇怪错误
	for(int i:v) Min=min(Min,abs(i-las)),las=i;//预处理开始的情况
	for(int i=2;i<=n;i++) d.insert(abs(a[i]-a[i-1]));//预处理插入相邻之差
	for(int x,y,i=1;i<=m;i++){
		c=getchar();while(c!='M'&&c!='I'&&c!='N'&&c!='_'&&c!='S'&&c!='O'&&c!='T'&&c!='G'&&c!='A'&&c!='P'&&c!='E'&&c!='R') c=getchar();
		if(c=='I'){
			while(c=='M'||c=='I'||c=='N'||c=='_'||c=='S'||c=='O'||c=='T'||c=='G'||c=='A'||c=='P'||c=='E'||c=='R') c=getchar();
			x=read();y=read();
			las=b[x];
			if(x!=n){
				nxt=a[x+1];
				tmp=abs(las-nxt);//如果插入一个数必定把前一个数与后一个数隔开,所以要删去
				d.erase(d.find(tmp));
				d.insert(abs(y-nxt));//插入新的后继
			}
			d.insert(abs(y-las));//插入新的前驱
			b[x]=y;
			It pos=v.lower_bound(y);//寻找后继
			Min=min(Min,abs(y-*pos));
			--pos;//后继-1就是前驱
			Min=min(Min,abs(y-*pos));
			v.insert(y);//插入总
		}else{
			c=getchar();c=getchar();c=getchar();c=getchar();
			if(c=='G'){
				while(c=='M'||c=='I'||c=='N'||c=='_'||c=='S'||c=='O'||c=='T'||c=='G'||c=='A'||c=='P'||c=='E'||c=='R') c=getchar();
				write(*d.begin());putchar('\n');//输出最小值
			}else{
				while(c=='M'||c=='I'||c=='N'||c=='_'||c=='S'||c=='O'||c=='T'||c=='G'||c=='A'||c=='P'||c=='E'||c=='R') c=getchar();
				write(Min);putchar('\n');//输出最小值
			}
		}
	}
} 
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇