[bzoj4864][BeiJing 2017 Wc]神秘物质

时间:2022-05-22 09:21:42

来自FallDream的博客,未经允许,请勿转载,谢谢。


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 的子区间。
小诚坚信这项研究可以获得诺贝尔物理学奖。为了让小诚早日了结心愿,你能否帮助他实现上述的观测和测量呢?
n,m<=10^5
 
话说省夏监考的时候写题真刺激..
这道题其实是一道平衡树裸题,max操作显然是问区间最大值和最小值,min操作只要稍微脑补一下都能发现答案只可能是相邻两个相差的绝对值的最小值
所以只要开两个splay,一个维护原数组,另一个维护差分数组即可
#include<iostream>
#include<cstdio>
#define MN 200000
using namespace std;
inline int read()
{
int x=;char ch=getchar();
while(ch<''||ch>'')ch=getchar();
while(ch>=''&&ch<='')x=x*+ch-'',ch=getchar();
return x;
}
int n,m,a[MN+],b[MN+];
inline int abs(int x){return x<?-x:x;}
struct Splay
{
int cnt,c[MN+][],fa[MN+],size[MN+],mx[MN+],mn[MN+],rt,s[MN+];
void update(int x)
{
int l=c[x][],r=c[x][];
mx[x]=mn[x]=s[x];size[x]=size[l]+size[r]+;
if(l) mx[x]=max(mx[x],mx[l]),mn[x]=min(mn[x],mn[l]);
if(r) mx[x]=max(mx[x],mx[r]),mn[x]=min(mn[x],mn[r]);
}
int build(int*a,int l,int r)
{
if(l>r)return ;
int mid=l+r>>;s[mid]=a[mid];
c[mid][]=build(a,l,mid-);fa[c[mid][]]=mid;
c[mid][]=build(a,mid+,r);fa[c[mid][]]=mid;
update(mid);
return mid;
}
void rotate(int x,int&k)
{
int y=fa[x],z=fa[y],l=c[y][]==x,r=l^;
if(y==k) k=x; else c[z][c[z][]==y]=x;
fa[x]=z;fa[y]=x;fa[c[x][r]]=y;
c[y][l]=c[x][r];c[x][r]=y;
update(y);update(x);
}
void splay(int x,int&k)
{
for(;x!=k;rotate(x,k))
if(fa[x]!=k) rotate(c[fa[fa[x]]][]==fa[x]^c[fa[x]][]==x?x:fa[x],k);
}
int Find(int x,int rk)
{
int Sz=size[c[x][]]+;
if(Sz==rk) return x;
if(Sz>rk) return Find(c[x][],rk);
else return Find(c[x][],rk-Sz);
}
int Split(int l,int r)
{
splay(Find(rt,l),rt);
splay(Find(rt,r),c[rt][]);
return c[c[rt][]][];
}
void Modify(int x,int rk,int v)
{
int Sz=size[c[x][]]+;
if(Sz==rk){s[x]=v;update(x);return;}
else if(Sz<rk) Modify(c[x][],rk-Sz,v);
else Modify(c[x][],rk,v);
update(x);
}
void ins(int&x,int rk,int v,int last)
{
if(!x){x=++cnt;s[x]=mx[x]=mn[x]=v;size[x]=v;fa[x]=last;return;}
int Sz=size[c[x][]]+;
if(Sz<=rk) ins(c[x][],rk-Sz,v,x);
else ins(c[x][],rk,v,x);
update(x);
}
}s,S;
char op[];
int main()
{
n=read();m=read();
for(int i=;i<=n;++i) a[i+]=read(),b[i]=abs(a[i+]-a[i]);
s.rt=s.build(a,,n+);S.rt=S.build(b,,n+);
s.cnt=n+;S.cnt=n+;
for(int i=;i<=m;++i)
{
scanf("%s",op+);int x=read(),y=read();
if(op[]=='e')
{
int z=s.Split(x,x+);S.Split(x,x+);
S.c[S.c[S.rt][]][]=s.c[z][]=s.c[z][]=;
S.s[S.rt]=abs(y-s.s[s.rt]);S.s[S.c[S.rt][]]=abs(s.s[s.c[s.rt][]]-y);
S.update(S.c[S.rt][]);S.update(S.rt);
s.s[z]=y;s.update(z);s.update(s.c[s.rt][]);s.update(s.rt);
}
if(op[]=='n')
{
int b=s.Find(s.rt,x+),a=s.Find(s.rt,x+);
s.ins(s.rt,x+,y,);s.splay(s.cnt,s.rt);
S.Modify(S.rt,x+,abs(y-s.s[b]));
S.ins(S.rt,x+,abs(s.s[a]-y),);S.splay(S.cnt,S.rt);
}
if(op[]=='a')
{
int X=s.Split(x,y+);
printf("%d\n",s.mx[X]-s.mn[X]);
}
if(op[]=='i')
{
int X=S.Split(x,y+);
printf("%d\n",S.mn[X]);
}
}
return ;
}

[bzoj4864][BeiJing 2017 Wc]神秘物质的更多相关文章

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

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

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

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

  3. BZOJ4864&colon; &lbrack;BeiJing 2017 Wc&rsqb;神秘物质&lpar;Splay&rpar;

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

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

    [BZOJ4864][BeiJing 2017 Wc]神秘物质 Description 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. &lbrack;bzoj4864&rsqb;&lbrack;BeiJing2017Wc&rsqb;神秘物质&lowbar;非旋转Treap

    神秘物质 bzoj-4864 BeiJing-2017-Wc 题目大意:给定一个长度为n的序列,支持插入,将相邻两个元素合并并在该位置生成一个指定权值的元素:查询:区间内的任意一段子区间的最大值减最小 ...

随机推荐

  1. thinkjs中自定义sql语句

    一直以为在使用thinkjs时,只能是它自带的sql语句查询,当遇到类似于这样的sql语句时,却不知道这该怎样来写程序,殊不知原来thinkjs可以执行自定义sql语句 SELECT * from a ...

  2. Map&sol;Reduce个人实战--生成数据测试集

    背景: 在大数据领域, 由于各方面的原因. 有时需要自己来生成测试数据集, 由于测试数据集较大, 因此采用Map/Reduce的方式去生成. 在这小编(mumuxinfei)结合自身的一些实战经历, ...

  3. java开发--JavaScript

    http://www.cnblogs.com/hongten/archive/2011/03/21/1990121.html JavaScript表单验证电话号码,判断一个输入量是否为电话号码,通过正 ...

  4. 学习Slim Framework for PHP v3 &lpar;三&rpar;

    继续上一篇的问题,如何动态的添加不同的Module.添加Module是给Middleware用的,用于调用Module的写日志方法.上篇中的写法是在app->add(mv),这时的middlew ...

  5. Java字节码(&period;class文件)格式详解(一)

    原文链接:http://www.blogjava.net/DLevin/archive/2011/09/05/358033.html 小介:去年在读<深入解析JVM>的时候写的,记得当时还 ...

  6. input效果:当鼠标在input中输入文字是改变内部文字效果

    主要用到属性:onpropertychange事件(属性改变时触发的事件),oninput属性(当input有输入时发生的事件) onpropertychange事件是IE专属事件 oninput属性 ...

  7. Anisotropic gauss filter

    最近一直在做版面分析,其中文本行检测方面,许多文章涉及到了Anigauss也就是各向异性高斯滤波. 顾名思义,简单的理解就是参数不同的二维高斯滤波. 在文章Fast Anisotropic Gauss ...

  8. C&num; byte&lbrack;&rsqb;与char&lbrack;&rsqb;、string与char&lbrack;&rsqb;、byte&lbrack;&rsqb; 与 string 互转

    1. byte array -> char array Byte[] b=new byte[5]{0x01,0x02,0x03,0x04,0x05};  Char[] c=Encoding.AS ...

  9. Unity5权威讲解

    Photon Cloud 299c7416-a08d-4a23-95a1-e4be108259aa Shooter 视频:https://pan.baidu.com/s/1kVFJ1x9 项目:htt ...

  10. Linux 小知识翻译 - 「虚拟化技术 续」

    这次,继续聊聊「虚拟化技术」. 根据上回的介绍,虚拟化技术可以使「计算机的台数和运行的OS的个数的比例不再是1:1」.这回介绍一下如何使用这个技术. 使用方法之一,「一台计算机上运行多个OS」.从个人 ...