# BZOJ1058: [ZJOI2007]报表统计(set)

Time Limit: 15 Sec  Memory Limit: 162 MB
Submit: 4190  Solved: 1420
[Submit][Status][Discuss]

## Description

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

## Input

第一行包含两个整数N，M，分别表示原数列的长度以及操作的次数。第二行为N个整数，为初始序列。接下来

## Output

对于每一个“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

## HINT

N , M ≤500000 对于所有的数据，序列内的整数不超过5*10^8。

## Source

#include<cstdio>
#include<set>
#include<algorithm>
#define msit multiset<int>::iterator
#define sit set<int>::iterator
using namespace std;
const int MAXN=1e6+10;
multiset<int>sp;//相邻元素的差值
set<int>sv;//相近元素的差值
set<int>s;//维护已经加入的元素的值
struct node
{
int up,down;
}a[MAXN];
int date[MAXN];
char opt;
int main()
{
#ifdef WIN32
freopen("a.in","r",stdin);
#endif
int N,M;
scanf("%d%d",&N,&M);
for(int i=1;i<=N;i++)
scanf("%d",&a[i].up),
date[i]=a[i].down=a[i].up,
s.insert(a[i].up);
for(int i=1;i<=N-1;i++) sp.insert(abs(a[i].up-a[i+1].up));
sort(date+1,date+N+1);
for(int i=1;i<=N-1;i++) sv.insert(abs(date[i]-date[i+1]));
while(M--)
{
scanf("%s",opt);
if(opt=='R')//insert
{
int pos,val;
scanf("%d%d",&pos,&val);
msit it=sp.find(abs(a[pos].down-a[pos+1].up));
if(it!=sp.end()) sp.erase(it);
sp.insert(abs(val-a[pos].down));
sp.insert(abs(val-a[pos+1].up));
a[pos].down=val;
sit st=s.lower_bound(val);
if(st!=s.end())
sv.insert(abs(val-*st));
if(st!=s.begin())
--st,
sv.insert(abs(val-*st));
s.insert(val);
}
else if(opt=='S')//val min
printf("%d\n",*sv.begin());
else if(opt=='G')//neighbor min
printf("%d\n",*sp.begin());
}
return 0;
}

posted @ 2018-04-02 08:55  自为风月马前卒  阅读(152)  评论(0编辑  收藏

……
{"ft_lang_label":"__label__zh","ft_lang_prob":0.75331587,"math_prob":0.97648036,"size":2293,"snap":"2020-34-2020-40","text_gpt3_token_len":1274,"char_repetition_ratio":0.11882918,"word_repetition_ratio":0.086021505,"special_character_ratio":0.3340602,"punctuation_ratio":0.19214876,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9838531,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2020-08-08T00:06:27Z\",\"WARC-Record-ID\":\"<urn:uuid:eaee8624-bb92-4779-9ba7-4989ecb6131a>\",\"Content-Length\":\"29621\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:6ebd63a7-d76b-46e1-b726-ba324d2ed92d>\",\"WARC-Concurrent-To\":\"<urn:uuid:8a1ef8b1-d5dc-4c60-952e-14e29872578e>\",\"WARC-IP-Address\":\"118.31.180.41\",\"WARC-Target-URI\":\"https://www.cnblogs.com/zwfymqz/p/8689993.html\",\"WARC-Payload-Digest\":\"sha1:7LEASSPOSNKADABMGY56GBRTS7DBAOGD\",\"WARC-Block-Digest\":\"sha1:N5C2WVTCIYDTRWL6B4OTY2CUDCXWXKOL\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2020/CC-MAIN-2020-34/CC-MAIN-2020-34_segments_1596439737233.51_warc_CC-MAIN-20200807231820-20200808021820-00026.warc.gz\"}"}