BZOJ4864: [BeiJing 2017 Wc]神秘物质(Splay)

时间:2021-10-08 09:22:55

Description

21ZZ 年,冬。
小诚退休以后, 不知为何重新燃起了对物理学的兴趣。 他从研究所借了些实验仪器,整天研究各种微观粒子。这
一天, 小诚刚从研究所得到了一块奇异的陨石样本, 便迫不及待地开始观测。 在精密仪器的视野下,构成陨石
的每个原子都无比清晰。 小诚发现, 这些原子排成若干列, 每一列的结构具有高度相似性。于是,他决定对单
独一列原子进行测量和测试。被选中的这列共有 N 个顺序排列的原子。 最初, 第 i 个原子具有能量 Ei。 随着
时间推移和人为测试, 这列原子在观测上会产生两种变化:
merge x e 当前第 x 个原子和第 x+1 个原子合并,得到能量为 e 的新原子;
insert x e 在当前第 x 个原子和第 x+1 个原子之间插入一个能量为 e 的新原子。
对于一列原子,小诚关心的是相邻一段中能量最大和能量最小的两个原子的能量差值,
称为区间极差。 因此, 除了观测变化外,小诚还要经常统计这列原子的两类数据:
max x y 当前第 x 到第 y 个原子之间的任意子区间中区间极差的最大值;
min x y 当前第 x 到第 y 个原子之间的任意子区间中区间极差的最小值。
其中, 子区间指的是长度至少是 2 的子区间。
小诚坚信这项研究可以获得诺贝尔物理学奖。为了让小诚早日了结心愿,你能否帮助他实现上述的观测和测量呢?

Input

第一行, 两个整数 N, M, 分别表示最初的原子数目和事件总数。
第二行, N 个整数 E1, E2, …, EN, 由空格隔开。依次表示每个原子的能量。
接下来 M 行, 每行为一个字符串和两个整数, 描述一次事件,格式见题目描述。
N<=100,000,M<=100,000
1 ≤ e, Ei ≤ 109。 设 N’ 为当前时刻原子数目。
对于 merge 类事件, 1 ≤ x ≤ N’-1;
对于 insert 类事件, 1 ≤ x ≤ N’;
对于 max 和 min 类事件, 1 ≤ x < y ≤ N’。
任何时刻,保证 N’ ≥ 2。

Output

输出若干行, 按顺序依次表示每次 max 和 min 类事件的测量结果。

Sample Input

4 3
5 8 10 2
max 1 3
min 1 3
max 2 4

Sample Output

5 2 8

解题思路:

Splay维护插入,删除,区间统计答案。

极差最大值为区间最值差,最小值为相邻元素之差。

然后愉快地AC

代码:

 #include<cstdio>
#include<cstring>
#include<algorithm>
#define lll tr[spc].ch[0]
#define rrr tr[spc].ch[1]
#define ls ch[0]
#define rs ch[1]
const int N=;
struct trnt{
int ch[];
int fa;
int E;
int wgt;
int maxval;
int minval;
int abst;
int minab;
}tr[N];
int siz;
int root;
int n,m;
int energy[N];
char cmd[];
bool whc(int spc)
{
return tr[tr[spc].fa].rs==spc;
}
void pushup(int spc)
{
tr[spc].wgt=;
tr[spc].maxval=tr[spc].minval=tr[spc].E;
tr[spc].minab=tr[spc].abst;
if(lll)
{
tr[spc].wgt+=tr[lll].wgt;
tr[spc].maxval=std::max(tr[spc].maxval,tr[lll].maxval);
tr[spc].minval=std::min(tr[spc].minval,tr[lll].minval);
tr[spc].minab=std::min(tr[spc].minab,tr[lll].minab);
}
if(rrr)
{
tr[spc].wgt+=tr[rrr].wgt;
tr[spc].maxval=std::max(tr[spc].maxval,tr[rrr].maxval);
tr[spc].minval=std::min(tr[spc].minval,tr[rrr].minval);
tr[spc].minab=std::min(tr[spc].minab,tr[rrr].minab);
}
return ;
}
void rotate(int spc)
{
int f=tr[spc].fa;
bool k=whc(spc);
tr[f].ch[k]=tr[spc].ch[!k];
tr[spc].ch[!k]=f;
tr[tr[f].fa].ch[whc(f)]=spc;
tr[spc].fa=tr[f].fa;
tr[f].fa=spc;
tr[tr[f].ch[k]].fa=f;
pushup(f);
pushup(spc);
return ;
}
void splay(int spc,int f)
{
while(tr[spc].fa!=f)
{
int ft=tr[spc].fa;
if(tr[ft].fa==f)
{
rotate(spc);
break;
}
if(whc(spc)^whc(ft))
rotate(spc);
else
rotate(ft);
rotate(spc);
}
if(!f)
root=spc;
return ;
}
void Build(int l,int r,int &spc,int f)
{
if(l>r)
return ;
int mid=(l+r)>>;
spc=++siz;
tr[spc].fa=f;
tr[spc].E=energy[mid];
tr[spc].abst=std::abs(energy[mid]-energy[mid+]);
Build(l,mid-,lll,spc);
Build(mid+,r,rrr,spc);
pushup(spc);
return ;
}
int plc(int spc,int v)
{
if(tr[lll].wgt>=v)
return plc(lll,v);
if(tr[lll].wgt+==v)
return spc;
return plc(rrr,v-tr[lll].wgt-);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
scanf("%d",&energy[i]);
Build(,n+,root,);
while(m--)
{
int x,y;
scanf("%s",cmd+);
scanf("%d%d",&x,&y);
if(cmd[]=='i')
{
int spc1=plc(root,x+);
int spc2=plc(root,x+);
int spc=++siz;
splay(spc1,);
splay(spc2,root);
tr[spc1].abst=std::abs(tr[spc1].E-y);
tr[spc].abst=std::abs(tr[spc2].E-y);
tr[spc].fa=spc2;
tr[spc].E=y;
tr[spc2].ls=spc;
pushup(spc);
pushup(spc2);
pushup(root);
}else if(cmd[]=='e')
{
int spc1=plc(root,x),spc2=plc(root,x+);
splay(spc1,);
splay(spc2,root);
tr[spc1].abst=std::abs(y-tr[spc1].E);
int spc=++siz;
tr[spc].fa=tr[root].rs;
tr[spc].E=y;
tr[spc].abst=std::abs(y-tr[spc2].E);
tr[tr[root].rs].ls=spc;
pushup(spc);
pushup(spc2);
pushup(root);
}else if(cmd[]=='i')
{
int spc1=plc(root,x),spc2=plc(root,y+);
splay(spc1,);
splay(spc2,root);
int ans=tr[tr[tr[root].rs].ls].minab;
printf("%d\n",ans);
}else{
int spc1=plc(root,x),spc2=plc(root,y+);
splay(spc1,);
splay(spc2,root);
int ans=tr[tr[tr[root].rs].ls].maxval-tr[tr[tr[root].rs].ls].minval;
printf("%d\n",tr[tr[tr[root].rs].ls].maxval-tr[tr[tr[root].rs].ls].minval);
}
}
return ;
}

BZOJ4864: [BeiJing 2017 Wc]神秘物质(Splay)的更多相关文章

  1. 【BZOJ4864】&lbrack;BeiJing 2017 Wc&rsqb;神秘物质 Splay

    [BZOJ4864][BeiJing 2017 Wc]神秘物质 Description 21ZZ 年,冬. 小诚退休以后, 不知为何重新燃起了对物理学的兴趣. 他从研究所借了些实验仪器,整天研究各种微 ...

  2. BZOJ4864 BeiJing 2017 Wc神秘物质(splay)

    splay维护区间最大值.最小值.相邻两数差的绝对值的最小值即可. #include<iostream> #include<cstdio> #include<cmath& ...

  3. &lbrack;bzoj4864&rsqb;&lbrack;BeiJing 2017 Wc&rsqb;神秘物质

    来自FallDream的博客,未经允许,请勿转载,谢谢. 21ZZ 年,冬. 小诚退休以后, 不知为何重新燃起了对物理学的兴趣. 他从研究所借了些实验仪器,整天研究各种微观粒子.这 一天, 小诚刚从研 ...

  4. BZOJ4864&lbrack;BeiJing 2017 Wc&rsqb;神秘物质——非旋转treap

    题目描述 21ZZ 年,冬. 小诚退休以后, 不知为何重新燃起了对物理学的兴趣. 他从研究所借了些实验仪器,整天研究各种微观粒子.这 一天, 小诚刚从研究所得到了一块奇异的陨石样本, 便迫不及待地开始 ...

  5. BZOJ&lowbar;4864&lowbar;&lbrack;BeiJing 2017 Wc&rsqb;神秘物质&lowbar;Splay

    BZOJ4864_[BeiJing 2017 Wc]神秘物质_Splay Description 21ZZ 年,冬. 小诚退休以后, 不知为何重新燃起了对物理学的兴趣. 他从研究所借了些实验仪器,整天 ...

  6. BZOJ 4864&colon; &lbrack;BeiJing 2017 Wc&rsqb;神秘物质 解题报告

    4864: [BeiJing 2017 Wc]神秘物质 Description 21ZZ 年,冬. 小诚退休以后, 不知为何重新燃起了对物理学的兴趣. 他从研究所借了些实验仪器,整天研究各种微观粒子. ...

  7. BZOJ 4864&colon; &lbrack;BeiJing 2017 Wc&rsqb;神秘物质 &lpar;块状链表&sol;平衡树 &rpar;

    这就是一道数据结构裸题啊,最大极差就是区间最大值减最小值,最小极差就是相邻两个数差的最小值.然后平衡树splay/treap或者块状链表维护就行了. 第一次自己写块状链表,蛮好写,就是长..然后就BZ ...

  8. &num;4864&period; &lbrack;BeiJing 2017 Wc&rsqb;神秘物质 &lbrack;FHQ Treap&rsqb;

    这题其实挺简单的,有个东西可能稍微难维护了一点点.. \(merge\ x\ e\) 当前第 \(x\) 个原子和第 \(x+1\) 个原子合并,得到能量为 \(e\) 的新原子: \(insert\ ...

  9. 【BZOJ4864】神秘物质 &lbrack;Splay&rsqb;

    神秘物质 Time Limit: 10 Sec  Memory Limit: 256 MB Description Input Output Sample Input Sample Output 1 ...

随机推荐

  1. linux常用命令-用户管理命令

    useradd 用户名 passwd 用户名:修改该用户的密码 groupadd 组名 who: 查看现在登录了几个用户,得到的信息含义如下 登录用户名 登录终端 登录时间 登录终端的IP地址(如果没 ...

  2. 使用JAVA客户端对HDFS进行代码编写&lpar;五&rpar;

    在linux中,在JAVA中编程,耗时的不是代码的编写而是环境的搭建,版本的选择...日了苍天,昨天eclipse突然抽风在linux运行不起来,耗了几个小时,试了各种办法...现在windows环境 ...

  3. iis配置PHP

    今天在服务器上配置PHP出现在下面的问题:“HTTP 错误 500.0 - Internal Server Error,C:\php\php-cgi.exe - FastCGI 进程意外退出”,下面说 ...

  4. Scriplet的三种代码

    Jsp中注释分为显示注释和隐式注释, 显示注释 -- 可以通过查看源代码看到 <!-- 第一种注释 -->  隐式注释 --  源代码中看不到 <%--jsp注释---%> & ...

  5. Maven构建Struts2项目

    1.添加Struts2依赖 这里主需要在pom.xml中添加一个struts-core的依赖即可: <project xmlns="http://maven.apache.org/PO ...

  6. &lbrack;Swift&rsqb;LeetCode895&period; 最大频率栈 &vert; Maximum Frequency Stack

    Implement FreqStack, a class which simulates the operation of a stack-like data structure. FreqStack ...

  7. JNI和NDK基础

    引言 JNI是Java Native Interface(Java本地接口),是为了方便Java调用C和C++等本地代码所封装的一层接口. NDK是Android提供的一个工具集合,通过NDK可以在A ...

  8. Pytorch Visdom可视化工具

    2018-12-04 14:05:49 Visdom是Facebook专门为PyTorch开发的一款可视化工具,其开源于2017年3月.Visdom十分轻量级,但却支持非常丰富的功能,能胜任大多数的科 ...

  9. 2017-6-6&amp&semi;6-8&sol;大型网站架构总结

    一.WikiPedia(*) WikiPedia是非盈利网站,因此尽可能地使用免费的软件和廉价的服务器.截止到2012年,这个只有区区数百台服务器和十余个技术人员开发.维护的网站,成为流量全球排 ...

  10. &lbrack;py&rsqb;&lbrack;mx&rsqb;django自定义认证类-实现邮箱作为用户名登录

    创建自定义验证用户名密码类CustomBackend users/views.py from django.contrib.auth import authenticate, login from d ...