Description
Input
Output
Sample Input
5 8 10 2
max 1 3
min 1 3
max 2 4
Sample Output
解题思路:
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)的更多相关文章
-
【BZOJ4864】[BeiJing 2017 Wc]神秘物质 Splay
[BZOJ4864][BeiJing 2017 Wc]神秘物质 Description 21ZZ 年,冬. 小诚退休以后, 不知为何重新燃起了对物理学的兴趣. 他从研究所借了些实验仪器,整天研究各种微 ...
-
BZOJ4864 BeiJing 2017 Wc神秘物质(splay)
splay维护区间最大值.最小值.相邻两数差的绝对值的最小值即可. #include<iostream> #include<cstdio> #include<cmath& ...
-
[bzoj4864][BeiJing 2017 Wc]神秘物质
来自FallDream的博客,未经允许,请勿转载,谢谢. 21ZZ 年,冬. 小诚退休以后, 不知为何重新燃起了对物理学的兴趣. 他从研究所借了些实验仪器,整天研究各种微观粒子.这 一天, 小诚刚从研 ...
-
BZOJ4864[BeiJing 2017 Wc]神秘物质——非旋转treap
题目描述 21ZZ 年,冬. 小诚退休以后, 不知为何重新燃起了对物理学的兴趣. 他从研究所借了些实验仪器,整天研究各种微观粒子.这 一天, 小诚刚从研究所得到了一块奇异的陨石样本, 便迫不及待地开始 ...
-
BZOJ_4864_[BeiJing 2017 Wc]神秘物质_Splay
BZOJ4864_[BeiJing 2017 Wc]神秘物质_Splay Description 21ZZ 年,冬. 小诚退休以后, 不知为何重新燃起了对物理学的兴趣. 他从研究所借了些实验仪器,整天 ...
-
BZOJ 4864: [BeiJing 2017 Wc]神秘物质 解题报告
4864: [BeiJing 2017 Wc]神秘物质 Description 21ZZ 年,冬. 小诚退休以后, 不知为何重新燃起了对物理学的兴趣. 他从研究所借了些实验仪器,整天研究各种微观粒子. ...
-
BZOJ 4864: [BeiJing 2017 Wc]神秘物质 (块状链表/平衡树 )
这就是一道数据结构裸题啊,最大极差就是区间最大值减最小值,最小极差就是相邻两个数差的最小值.然后平衡树splay/treap或者块状链表维护就行了. 第一次自己写块状链表,蛮好写,就是长..然后就BZ ...
-
#4864. [BeiJing 2017 Wc]神秘物质 [FHQ Treap]
这题其实挺简单的,有个东西可能稍微难维护了一点点.. \(merge\ x\ e\) 当前第 \(x\) 个原子和第 \(x+1\) 个原子合并,得到能量为 \(e\) 的新原子: \(insert\ ...
-
【BZOJ4864】神秘物质 [Splay]
神秘物质 Time Limit: 10 Sec Memory Limit: 256 MB Description Input Output Sample Input Sample Output 1 ...
随机推荐
-
linux常用命令-用户管理命令
useradd 用户名 passwd 用户名:修改该用户的密码 groupadd 组名 who: 查看现在登录了几个用户,得到的信息含义如下 登录用户名 登录终端 登录时间 登录终端的IP地址(如果没 ...
-
使用JAVA客户端对HDFS进行代码编写(五)
在linux中,在JAVA中编程,耗时的不是代码的编写而是环境的搭建,版本的选择...日了苍天,昨天eclipse突然抽风在linux运行不起来,耗了几个小时,试了各种办法...现在windows环境 ...
-
iis配置PHP
今天在服务器上配置PHP出现在下面的问题:“HTTP 错误 500.0 - Internal Server Error,C:\php\php-cgi.exe - FastCGI 进程意外退出”,下面说 ...
-
Scriplet的三种代码
Jsp中注释分为显示注释和隐式注释, 显示注释 -- 可以通过查看源代码看到 <!-- 第一种注释 --> 隐式注释 -- 源代码中看不到 <%--jsp注释---%> & ...
-
Maven构建Struts2项目
1.添加Struts2依赖 这里主需要在pom.xml中添加一个struts-core的依赖即可: <project xmlns="http://maven.apache.org/PO ...
-
[Swift]LeetCode895. 最大频率栈 | Maximum Frequency Stack
Implement FreqStack, a class which simulates the operation of a stack-like data structure. FreqStack ...
-
JNI和NDK基础
引言 JNI是Java Native Interface(Java本地接口),是为了方便Java调用C和C++等本地代码所封装的一层接口. NDK是Android提供的一个工具集合,通过NDK可以在A ...
-
Pytorch Visdom可视化工具
2018-12-04 14:05:49 Visdom是Facebook专门为PyTorch开发的一款可视化工具,其开源于2017年3月.Visdom十分轻量级,但却支持非常丰富的功能,能胜任大多数的科 ...
-
2017-6-6&;6-8/大型网站架构总结
一.WikiPedia(*) WikiPedia是非盈利网站,因此尽可能地使用免费的软件和廉价的服务器.截止到2012年,这个只有区区数百台服务器和十余个技术人员开发.维护的网站,成为流量全球排 ...
-
[py][mx]django自定义认证类-实现邮箱作为用户名登录
创建自定义验证用户名密码类CustomBackend users/views.py from django.contrib.auth import authenticate, login from d ...