bzoj 1058: [ZJOI2007]报表统计

时间:2022-08-27 18:54:33

Description

  小Q的妈妈是一个出纳,经常需要做一些统计报表的工作。今天是妈妈的生日,小Q希望可以帮妈妈分担一些工
作,作为她的生日礼物之一。经过仔细观察,小Q发现统计一张报表实际上是维护一个可能为负数的整数数列,并
且进行一些查询操作。在最开始的时候,有一个长度为N的整数序列,并且有以下三种操作: INSERT i k 在原数
列的第i个元素后面添加一个新元素k; 如果原数列的第i个元素已经添加了若干元素,则添加在这些元素的最后(
见下面的例子) MIN_GAP 查询相邻两个元素的之间差值(绝对值)的最小值 MIN_SORT_GAP 查询所有元素中最接
近的两个元素的差值(绝对值) 例如一开始的序列为 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。于是小Q写了一个程序,使
得程序可以自动完成这些操作,但是他发现对于一些大的报表他的程序运行得很慢,你能帮助他改进程序么?

Input

  第一行包含两个整数N,M,分别表示原数列的长度以及操作的次数。第二行为N个整数,为初始序列。接下来
的M行每行一个操作,即“INSERT i k”,“MIN_GAP”,“MIN_SORT_GAP”中的一种(无多余空格或者空行)。

Output

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

Sample Input

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

Sample Output

2
2
1

HINT

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

 
 

思路

stl水题,不需要思路。
不过由于数据范围是500000,
调用stl中的函数会非常非常慢,只能在bzoj上A掉,codevs上会tle。
所以还可以用splay解决MIN_GAP,离散化+舞蹈链解决MIN_SORT_GAP。
当然,懒惰的我选择了stl
 
 

代码

 #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]报表统计的更多相关文章

  1. BZOJ 1058&colon; &lbrack;ZJOI2007&rsqb;报表统计&lpar; 链表 &plus; set &rpar;

    这种题用数据结构怎么写都能AC吧...按1~N弄个链表然后每次插入时就更新答案, 用set维护就可以了... --------------------------------------------- ...

  2. bzoj 1058&colon; &lbrack;ZJOI2007&rsqb;报表统计 &lpar;Treap)

    链接:https://www.lydsy.com/JudgeOnline/problem.php?id=1058 题面; 1058: [ZJOI2007]报表统计 Time Limit: 15 Sec ...

  3. &lbrack;BZOJ 1058&rsqb; &lbrack;ZJOI2007&rsqb; 报表统计 【平衡树】

    题目链接:BZOJ - 1058 题目分析 这道题看似是需要在序列中插入一些数字,但其实询问的内容只与相邻的元素有关. 那么我们只要对每个位置维护两个数 Ai, Bi, Ai 就是初始序列中 i 这个 ...

  4. BZOJ 1058&colon; &lbrack;ZJOI2007&rsqb;报表统计 multiset &plus; 卡常

    Code: #include<bits/stdc++.h> #define maxn 600000 #define inf 1000000000 using namespace std; ...

  5. bzoj 1058 &lbrack;ZJOI2007&rsqb;报表统计(set)

    [题目链接] http://www.lydsy.com/JudgeOnline/problem.php?id=1058 [题意] 一个序列,提供插入,查询相邻最小差值,查询任意最小差值的操作. [思路 ...

  6. bzoj 1058&colon; &lbrack;ZJOI2007&rsqb;报表统计【set】

    我想写FHQtreap的!是set自己跑进代码的!因为太好写了 是有点慢--洛谷上不吸氧会T一个点 就是,用一个set p维护所有点值,ans维护MIN_SORT_GAP的答案,每次insert一个点 ...

  7. bzoj P1058 &lbrack;ZJOI2007&rsqb;报表统计——solution

    1058: [ZJOI2007]报表统计 Time Limit: 15 Sec  Memory Limit: 162 MB Submit: 4099  Solved: 1390 [Submit][St ...

  8. 【BZOJ】1058&colon; &lbrack;ZJOI2007&rsqb;报表统计(splay&plus;set)

    http://www.lydsy.com/JudgeOnline/problem.php?id=1058 当复习一下splay.... 做法很简单..... 观察得知每一次插入一个点只需要维护前后的绝 ...

  9. 1058&colon; &lbrack;ZJOI2007&rsqb;报表统计 - BZOJ

    Description 小Q的妈妈是一个出纳,经常需要做一些统计报表的工作.今天是妈妈的生日,小Q希望可以帮妈妈分担一些工作,作为她的生日礼物之一.经过仔细观察,小Q发现统计一张报表实际上是维护一个非 ...

随机推荐

  1. iOS 设置 文字和 图片的位置

    1.我最开始实现这个采用的方法:重新自定义一个view,然后有两个属性label和imageView,然后设置位置布局,再添加单击手势,用代理回传点击方法. 2.第二种方法:自定义一个Button继承 ...

  2. Object&period;defineProperty

    属性类型ECMA-262第5版在定义只有内部才用的特性(attribute)时,描述了属性(property)的各种特征.ECMA-262定义这些特性是为了实现JavaScript引擎用的,因此在Ja ...

  3. aps&period;net 用ajax 读取服务端值

      1.Default.aspx 页面内容 实例一: <%@ Page Language="C#" AutoEventWireup="true" Code ...

  4. Your data vis &OpenCurlyDoubleQuote;Spidey-sense” &amp&semi; the need for a robust &OpenCurlyDoubleQuote;utility belt”

    @theboysmithy did a great piece on coming up with an alternate view for a timeline for an FT piece. ...

  5. 关于回文串的DP问题

    问题1:插入/删除字符使得原字符串变成一个回文串且代价最小 poj 3280 Cheapest Palindrome 题意:给出一个由m中字母组成的长度为n的串,给出m种字母添加和删除花费的代价,求让 ...

  6. 利用python实现简单邮件功能

    #!/usr/bin/env python # -*- coding:utf-8 -*- import smtplib from email.utils import formataddr from ...

  7. 如何更简单方便地执行SQL操作&quest;

    现在公司使用mybatis作为DAL层的框架. 使用起来比较简单,使用xml进行SQL的书写,java代码使用接口执行. 但在写一些简单SQL的时候会显得非常繁琐: xml和java分离(设计上为了解 ...

  8. python的基本数据类型&lpar;一&rpar;

    一.运算符逻辑运算and:两边都真则真or:有真则真not:非假是真 顺序:()>==>not==>and>=or 二.while.. elsewhile 条件: 代码块els ...

  9. linux驱动编写之阻塞与非阻塞

    一.概念 应用程序使用API接口,如open.read等来最终操作驱动,有两种结果--成功和失败.成功,很好处理,直接返回想要的结果:但是,失败,是继续等待,还是返回失败类型呢?  如果继续等待,将进 ...

  10. codeforces701C

    They Are Everywhere CodeForces - 701C 大B,年轻的口袋妖怪训练师,找到了一个由 n 间从左向右的房间组成的大房子.你可以从街道里走入任何一间房子,也可以从任何一间 ...