来自FallDream的博客,未经允许,请勿转载,谢谢。
#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]神秘物质的更多相关文章
-
BZOJ4864 BeiJing 2017 Wc神秘物质(splay)
splay维护区间最大值.最小值.相邻两数差的绝对值的最小值即可. #include<iostream> #include<cstdio> #include<cmath& ...
-
BZOJ4864[BeiJing 2017 Wc]神秘物质——非旋转treap
题目描述 21ZZ 年,冬. 小诚退休以后, 不知为何重新燃起了对物理学的兴趣. 他从研究所借了些实验仪器,整天研究各种微观粒子.这 一天, 小诚刚从研究所得到了一块奇异的陨石样本, 便迫不及待地开始 ...
-
BZOJ4864: [BeiJing 2017 Wc]神秘物质(Splay)
Description 21ZZ 年,冬. 小诚退休以后, 不知为何重新燃起了对物理学的兴趣. 他从研究所借了些实验仪器,整天研究各种微观粒子.这 一天, 小诚刚从研究所得到了一块奇异的陨石样本, 便 ...
-
【BZOJ4864】[BeiJing 2017 Wc]神秘物质 Splay
[BZOJ4864][BeiJing 2017 Wc]神秘物质 Description 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][BeiJing2017Wc]神秘物质_非旋转Treap
神秘物质 bzoj-4864 BeiJing-2017-Wc 题目大意:给定一个长度为n的序列,支持插入,将相邻两个元素合并并在该位置生成一个指定权值的元素:查询:区间内的任意一段子区间的最大值减最小 ...
随机推荐
-
thinkjs中自定义sql语句
一直以为在使用thinkjs时,只能是它自带的sql语句查询,当遇到类似于这样的sql语句时,却不知道这该怎样来写程序,殊不知原来thinkjs可以执行自定义sql语句 SELECT * from a ...
-
Map/Reduce个人实战--生成数据测试集
背景: 在大数据领域, 由于各方面的原因. 有时需要自己来生成测试数据集, 由于测试数据集较大, 因此采用Map/Reduce的方式去生成. 在这小编(mumuxinfei)结合自身的一些实战经历, ...
-
java开发--JavaScript
http://www.cnblogs.com/hongten/archive/2011/03/21/1990121.html JavaScript表单验证电话号码,判断一个输入量是否为电话号码,通过正 ...
-
学习Slim Framework for PHP v3 (三)
继续上一篇的问题,如何动态的添加不同的Module.添加Module是给Middleware用的,用于调用Module的写日志方法.上篇中的写法是在app->add(mv),这时的middlew ...
-
Java字节码(.class文件)格式详解(一)
原文链接:http://www.blogjava.net/DLevin/archive/2011/09/05/358033.html 小介:去年在读<深入解析JVM>的时候写的,记得当时还 ...
-
input效果:当鼠标在input中输入文字是改变内部文字效果
主要用到属性:onpropertychange事件(属性改变时触发的事件),oninput属性(当input有输入时发生的事件) onpropertychange事件是IE专属事件 oninput属性 ...
-
Anisotropic gauss filter
最近一直在做版面分析,其中文本行检测方面,许多文章涉及到了Anigauss也就是各向异性高斯滤波. 顾名思义,简单的理解就是参数不同的二维高斯滤波. 在文章Fast Anisotropic Gauss ...
-
C# byte[]与char[]、string与char[]、byte[] 与 string 互转
1. byte array -> char array Byte[] b=new byte[5]{0x01,0x02,0x03,0x04,0x05}; Char[] c=Encoding.AS ...
-
Unity5权威讲解
Photon Cloud 299c7416-a08d-4a23-95a1-e4be108259aa Shooter 视频:https://pan.baidu.com/s/1kVFJ1x9 项目:htt ...
-
Linux 小知识翻译 - 「虚拟化技术 续」
这次,继续聊聊「虚拟化技术」. 根据上回的介绍,虚拟化技术可以使「计算机的台数和运行的OS的个数的比例不再是1:1」.这回介绍一下如何使用这个技术. 使用方法之一,「一台计算机上运行多个OS」.从个人 ...