Description
Input
Output
对于每一个“MIN_GAP”和“MIN_SORT_GAP”命令,输出一行答案即可。
Sample Input
5 3 1
INSERT 2 9
MIN_SORT_GAP
INSERT 2 6
MIN_GAP
MIN_SORT_GAP
Sample Output
2
1
HINT
N , M ≤500000 对于所有的数据,序列内的整数不超过5*10^8。
思路
代码
#include <map>
#include <set>
#include <queue>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
#define ref(i,x,y)for(int i=x;i<=y;++i)
int read()
{
char c=getchar();int d=,f=;
for(;c<''||c>'';c=getchar())if(c=='-')f=-;
for(;c>=''&&c<='';d=d*+c-,c=getchar());
return d*f;
}
const int N=;
int n,m,ANS,a[N],b[N];
set<int> s;
map<int,int> mp;
priority_queue<int,vector<int>,greater<int> > q;
void Insert(int y)
{
int lower=*--s.lower_bound(y);
int upper=*s.lower_bound(y);
ANS=min(ANS,y-lower),ANS=min(ANS,upper-y);
s.insert(y);
}
int main()
{
n=read(),m=read();
s.insert(-1e9); s.insert(1e9);
ANS=2e9;
ref(i,,n)a[i]=b[i]=read(),Insert(a[i]);
ref(i,,n)
{
int s=abs(a[i]-a[i-]),tmp=++mp[s];
if(tmp==)q.push(s);
}
ref(i,,m)
{
char st[];scanf("%s",&st);
if(st[]=='I')
{
int x=read(),y=read();
Insert(y);
int s=abs(a[x+]-b[x]),tmp;--mp[s];
s=abs(b[x]-y);tmp=++mp[s];
if(tmp==)q.push(s);
s=abs(a[x+]-y);tmp=++mp[s];
if(tmp==)q.push(s);
b[x]=y;
}
else
{
if(st[]=='G')
{
while(!mp[q.top()])q.pop();
printf("%d\n",q.top());
}
else printf("%d\n",ANS);
}
}
}
bzoj 1058: [ZJOI2007]报表统计的更多相关文章
-
BZOJ 1058: [ZJOI2007]报表统计( 链表 + set )
这种题用数据结构怎么写都能AC吧...按1~N弄个链表然后每次插入时就更新答案, 用set维护就可以了... --------------------------------------------- ...
-
bzoj 1058: [ZJOI2007]报表统计 (Treap)
链接:https://www.lydsy.com/JudgeOnline/problem.php?id=1058 题面; 1058: [ZJOI2007]报表统计 Time Limit: 15 Sec ...
-
[BZOJ 1058] [ZJOI2007] 报表统计 【平衡树】
题目链接:BZOJ - 1058 题目分析 这道题看似是需要在序列中插入一些数字,但其实询问的内容只与相邻的元素有关. 那么我们只要对每个位置维护两个数 Ai, Bi, Ai 就是初始序列中 i 这个 ...
-
BZOJ 1058: [ZJOI2007]报表统计 multiset + 卡常
Code: #include<bits/stdc++.h> #define maxn 600000 #define inf 1000000000 using namespace std; ...
-
bzoj 1058 [ZJOI2007]报表统计(set)
[题目链接] http://www.lydsy.com/JudgeOnline/problem.php?id=1058 [题意] 一个序列,提供插入,查询相邻最小差值,查询任意最小差值的操作. [思路 ...
-
bzoj 1058: [ZJOI2007]报表统计【set】
我想写FHQtreap的!是set自己跑进代码的!因为太好写了 是有点慢--洛谷上不吸氧会T一个点 就是,用一个set p维护所有点值,ans维护MIN_SORT_GAP的答案,每次insert一个点 ...
-
bzoj P1058 [ZJOI2007]报表统计——solution
1058: [ZJOI2007]报表统计 Time Limit: 15 Sec Memory Limit: 162 MB Submit: 4099 Solved: 1390 [Submit][St ...
-
【BZOJ】1058: [ZJOI2007]报表统计(splay+set)
http://www.lydsy.com/JudgeOnline/problem.php?id=1058 当复习一下splay.... 做法很简单..... 观察得知每一次插入一个点只需要维护前后的绝 ...
-
1058: [ZJOI2007]报表统计 - BZOJ
Description 小Q的妈妈是一个出纳,经常需要做一些统计报表的工作.今天是妈妈的生日,小Q希望可以帮妈妈分担一些工作,作为她的生日礼物之一.经过仔细观察,小Q发现统计一张报表实际上是维护一个非 ...
随机推荐
-
iOS 设置 文字和 图片的位置
1.我最开始实现这个采用的方法:重新自定义一个view,然后有两个属性label和imageView,然后设置位置布局,再添加单击手势,用代理回传点击方法. 2.第二种方法:自定义一个Button继承 ...
-
Object.defineProperty
属性类型ECMA-262第5版在定义只有内部才用的特性(attribute)时,描述了属性(property)的各种特征.ECMA-262定义这些特性是为了实现JavaScript引擎用的,因此在Ja ...
-
aps.net 用ajax 读取服务端值
1.Default.aspx 页面内容 实例一: <%@ Page Language="C#" AutoEventWireup="true" Code ...
-
Your data vis “Spidey-sense” &; the need for a robust “utility belt”
@theboysmithy did a great piece on coming up with an alternate view for a timeline for an FT piece. ...
-
关于回文串的DP问题
问题1:插入/删除字符使得原字符串变成一个回文串且代价最小 poj 3280 Cheapest Palindrome 题意:给出一个由m中字母组成的长度为n的串,给出m种字母添加和删除花费的代价,求让 ...
-
利用python实现简单邮件功能
#!/usr/bin/env python # -*- coding:utf-8 -*- import smtplib from email.utils import formataddr from ...
-
如何更简单方便地执行SQL操作?
现在公司使用mybatis作为DAL层的框架. 使用起来比较简单,使用xml进行SQL的书写,java代码使用接口执行. 但在写一些简单SQL的时候会显得非常繁琐: xml和java分离(设计上为了解 ...
-
python的基本数据类型(一)
一.运算符逻辑运算and:两边都真则真or:有真则真not:非假是真 顺序:()>==>not==>and>=or 二.while.. elsewhile 条件: 代码块els ...
-
linux驱动编写之阻塞与非阻塞
一.概念 应用程序使用API接口,如open.read等来最终操作驱动,有两种结果--成功和失败.成功,很好处理,直接返回想要的结果:但是,失败,是继续等待,还是返回失败类型呢? 如果继续等待,将进 ...
-
codeforces701C
They Are Everywhere CodeForces - 701C 大B,年轻的口袋妖怪训练师,找到了一个由 n 间从左向右的房间组成的大房子.你可以从街道里走入任何一间房子,也可以从任何一间 ...