1058: [ZJOI2007]报表统计 - BZOJ

时间:2022-08-27 19:08:27

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

对于30%的数据,N ≤ 1000 , M ≤ 5000 对于100%的数据,N , M ≤500000 对于所有的数据,序列内的整数不超过5*108。

囧,又是splay,又被卡常数了,每次基本上都是对着数据调才调过的

我用两颗splay树,一个存所有的数(每次查前驱和后继更新答案),一个存所有的差值

当minsortgap为0时就不用再更新它了,还有,因为相邻的差值有一部分是不会被删除的,所以用min记录这些值中最小的值,大于等于min的差值就不用管它了(既不用删除,也不用插入)

搞了这么久终于过了(不过很慢,1300ms+)

 const
maxn=;
type
node=record
son:array[..]of longint;
x,count,fa:longint;
end;
var
tree:array[..maxn*]of node;
a,b:array[..maxn]of longint;
n,m,mingap,minsortgap,min,tot,root1,root2:longint;
flag:boolean; procedure down(var x:longint;y:longint);
begin
if x>y then x:=y;
end; procedure rotate(x,w:longint;var root:longint);
var
y:longint;
begin
y:=tree[x].fa;
tree[y].son[w]:=tree[x].son[w xor ];
if tree[x].son[w xor ]<> then tree[tree[x].son[w xor ]].fa:=y;
tree[x].son[w xor ]:=y;
if root=y then root:=x
else
if tree[tree[y].fa].son[]=y then tree[tree[y].fa].son[]:=x
else tree[tree[y].fa].son[]:=x;
tree[x].fa:=tree[y].fa;
tree[y].fa:=x;
end; procedure splay(x,z:longint;var root:longint);
var
y:longint;
begin
while tree[x].fa<>z do
begin
y:=tree[x].fa;
if tree[y].fa=z then
if tree[y].son[]=x then rotate(x,,root)
else rotate(x,,root)
else
if tree[tree[y].fa].son[]=y then
if tree[y].son[]=x then
begin
rotate(y,,root);
rotate(x,,root);
end
else
begin
rotate(x,,root);
rotate(x,,root);
end
else
if tree[y].son[]=x then
begin
rotate(x,,root);
rotate(x,,root);
end
else
begin
rotate(y,,root);
rotate(x,,root);
end;
end;
end; function pre(now:longint):longint;
begin
now:=tree[now].son[];
while tree[now].son[]<> do
now:=tree[now].son[];
exit(now);
end; function succ(now:longint):longint;
begin
now:=tree[now].son[];
while tree[now].son[]<> do
now:=tree[now].son[];
exit(now);
end; procedure delete(x:longint);
var
now,l,r:longint;
begin
now:=root2;
while true do
begin
if now= then exit;
if tree[now].x=x then break;
if tree[now].x>x then now:=tree[now].son[]
else now:=tree[now].son[];
end;
splay(now,,root2);
if tree[root2].count> then dec(tree[root2].count)
else
begin
if (tree[root2].son[]=) or (tree[root2].son[]=) then
begin
if tree[root2].son[]<> then mingap:=tree[succ(root2)].x;
root2:=tree[root2].son[]+tree[root2].son[];
tree[root2].fa:=;
exit;
end;
l:=pre(root2);
r:=succ(root2);
splay(l,,root2);
splay(r,l,root2);
tree[r].son[]:=;
end;
end; procedure insert(x:longint;var root:longint);
var
now:longint;
begin
now:=root;
if root= then
begin
inc(tot);
root:=tot;
tree[tot].x:=x;
tree[tot].count:=;
if root=root2 then down(mingap,x);
exit;
end;
while true do
begin
if tree[now].x=x then
if root=root1 then
begin
minsortgap:=;
flag:=true;
exit;
end
else
begin
inc(tree[now].count);
exit;
end;
if tree[now].x>x then
if tree[now].son[]= then break
else now:=tree[now].son[]
else
if tree[now].son[]= then break
else now:=tree[now].son[];
end;
inc(tot);
tree[tot].x:=x;
tree[tot].count:=;
if x<tree[now].x then tree[now].son[]:=tot
else tree[now].son[]:=tot;
tree[tot].fa:=now;
splay(tot,,root);
if root=root1 then
begin
if tree[root].son[]<> then down(minsortgap,tree[root].x-tree[pre(root)].x);
if tree[root].son[]<> then down(minsortgap,tree[succ(root)].x-tree[root].x);
end
else down(mingap,x);
end; procedure init;
var
i:longint;
begin
read(n,m);
minsortgap:=maxlongint;
mingap:=maxlongint;
min:=maxlongint;
for i:= to n do
begin
read(a[i]);
b[i]:=a[i];
if flag=false then insert(a[i],root1);
if i> then insert(abs(a[i]-a[i-]),root2);
end;
readln;
end; procedure work;
var
i,x,y:longint;
c:char;
s:string;
begin
for i:= to m do
begin
read(c);
case c of
'I':begin
readln(c,c,c,c,c,x,y);
if x<n then
begin
if min>abs(b[x+]-y) then insert(abs(b[x+]-y),root2);
if min>abs(a[x]-b[x+]) then delete(abs(a[x]-b[x+]));
end;
down(min,abs(a[x]-y));
if flag=false then insert(y,root1);
a[x]:=y;
end;
'M':begin
readln(s);
if length(s)> then writeln(minsortgap)
else
begin
down(mingap,min);
writeln(mingap);
end;
end;
end;
end;
end; begin
init;
work;
end.

1058: [ZJOI2007]报表统计 - BZOJ的更多相关文章

  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. bzoj 1058&colon; &lbrack;ZJOI2007&rsqb;报表统计

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

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

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

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

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

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

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

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

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

  8. AC日记——&lbrack;ZJOI2007&rsqb;报表统计 bzoj 1058

    1058 思路: 平衡树的题: 然而我的平衡树写一次炸一次QwQ: 而且各种tle: 所以stl水过: 代码: #include <set> #include <cstdio> ...

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

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

随机推荐

  1. Nike Zoom Winflo 2 Kvinder Sko N&&num;229&semi;r jeg set elementet

    De fleste af os elskede denne Nike Pegasus 34 foruden var ved at blive begejstret for at få dine ben ...

  2. CSS3的学习--实现瀑布流

    基于CSS3实现瀑布流,使用CSS3的CSS 多栏(Multi-column). 可以到github上下载源码 : https://github.com/CraryPrimitiveMan/water ...

  3. 正则转nfa:bug出现。

    本人写的一个正则到nfa的bug 刚写完前面的那篇,自己用脑子过了一下,发现了一个bug.具体情况如下. 这个bug的产生条件是多次调用假名的时候,每次调用都会修改假名的nfa图.直接这么说不好理解, ...

  4. &lbrack;UWP 自定义控件&rsqb;了解模板化控件&lpar;5&period;1&rpar;:TemplatePart vs&period; VisualState

    1. TemplatePart vs. VisualState 在前面两篇文章中分别使用了TemplatePart及VisualState的方式实现了相同的功能,其中明显VisualState的方式更 ...

  5. linux常用命令以及快捷键

    find命令查找某些文件并将其拷贝到指定目录 [root@host lib]# find -name "*hbase*.jar" |xargs -i cp {}  /root/aa ...

  6. Java基础笔记&lpar;3&rpar; 进制与进制转换

    ---恢复内容开始--- 进制 在一般生活中,我们一直在应用的十进制,就是逢十进一,而今天我们要接触的是,计算机编程常用的进制!首先我们要知道,计算机内部运算采用的是二进制,也就是逢二进制! 1.什么 ...

  7. 用srvctl命令配置service

    .用srvctl命令配置service 除了用DBCA图形方式,还能够使用命令方式配置service,这样的方法对于维护远程尤事实上用.不管是创建还是维护都是用一个命令srvctl,先看一下srvct ...

  8. e551&period; 精简的Applet

    Every applet must subclass Applet. import java.applet.*; import java.awt.*; public class BasicApplet ...

  9. rem和em学习笔记及CSS预处理

    1.当元素A的字体单位是n rem时,它将根据根元素(html)的font-size的大小作为基准,比如   parent-div中的em-div的font-size为2rem,他的基准就是html的 ...

  10. N个数求和

    题目: 本题的要求很简单,就是求N个数字的和.麻烦的是,这些数字是以有理数分子/分母的形式给出的,你输出的和也必须是有理数的形式. 输入格式: 输入第一行给出一个正整数N(≤100).随后一行按格式a ...