这题其实挺简单的,有个东西可能稍微难维护了一点点。。
\(merge\ x\ e\) 当前第 \(x\) 个原子和第 \(x+1\) 个原子合并,得到能量为 \(e\) 的新原子;
\(insert\ x\ e\) 在当前第 \(x\) 个原子和第 \(x+1\) 个原子之间插入一个能量为 \(e\) 的新原子。
\(max\ x\ y\) 当前第 \(x\) 到第 \(y\) 个原子之间的任意子区间中区间极差的最大值;
\(min\ x\ y\) 当前第 \(x\) 到第 \(y\) 个原子之间的任意子区间中区间极差的最小值。
极差最大值其实很显然是个区间 \(max - min\)
极差最小的区间呢,长度至少为 \(2\) 也必须为 \(2\)
至于证明的话
考虑 \(x,y,z\)
如果 \(x\) 和 \(z\) 的差的绝对值是解,那么 \(|x-y|\) 或者 \(|y-z|\) 一定更优
因为 \(x \leq y \leq z\) 才符合这种情况。
所以随便写写,把相邻两个的差变成后一个点的值,随便写写就可以了。
// by Isaunoya
#include <bits/stdc++.h>
using namespace std;
#define rep(i, x, y) for (register int i = (x); i <= (y); ++i)
#define Rep(i, x, y) for (register int i = (x); i >= (y); --i)
const int _ = 1 << 21;
struct I {
char fin[_], *p1 = fin, *p2 = fin;
inline char gc() {
return (p1 == p2) && (p2 = (p1 = fin) + fread(fin, 1, _, stdin), p1 == p2) ? EOF : *p1++;
}
inline I& operator>>(int& x) {
bool sign = 1;
char c = 0;
while (c < 48) ((c = gc()) == 45) && (sign = 0);
x = (c & 15);
while ((c = gc()) > 47) x = (x << 1) + (x << 3) + (c & 15);
x = sign ? x : -x;
return *this;
}
inline I& operator>>(double& x) {
bool sign = 1;
char c = 0;
while (c < 48) ((c = gc()) == 45) && (sign = 0);
x = (c - 48);
while ((c = gc()) > 47) x = x * 10 + (c - 48);
if (c == '.') {
double d = 1.0;
while ((c = gc()) > 47) d = d * 0.1, x = x + (d * (c - 48));
}
x = sign ? x : -x;
return *this;
}
inline I& operator>>(char& x) {
do
x = gc();
while (isspace(x));
return *this;
}
inline I& operator>>(string& s) {
s = "";
char c = gc();
while (isspace(c)) c = gc();
while (!isspace(c) && c != EOF) s += c, c = gc();
return *this;
}
} in;
struct O {
char st[100], fout[_];
signed stk = 0, top = 0;
inline void flush() {
fwrite(fout, 1, top, stdout), fflush(stdout), top = 0;
}
inline O& operator<<(int x) {
if (top > (1 << 20)) flush();
if (x < 0) fout[top++] = 45, x = -x;
do
st[++stk] = x % 10 ^ 48, x /= 10;
while (x);
while (stk) fout[top++] = st[stk--];
return *this;
}
inline O& operator<<(char x) {
fout[top++] = x;
return *this;
}
inline O& operator<<(string s) {
if (top > (1 << 20)) flush();
for (char x : s) fout[top++] = x;
return *this;
}
} out;
#define pb emplace_back
#define fir first
#define sec second
template < class T > inline void cmax(T & x , const T & y) {
(x < y) && (x = y) ;
}
template < class T > inline void cmin(T & x , const T & y) {
(x > y) && (x = y) ;
}
int n , m , rt = 0 ;
const int N = 2e5 + 10 ;
int a[N] ;
const int inf = 0x7fffffff ;
int rnd[N] , val[N] , mx[N] , mn[N] , ch[N][2] , sz[N] ;
int cnt = 0 ;
#define ls(x) ch[x][0]
#define rs(x) ch[x][1]
int newnode(int v) {
++ cnt ;
val[cnt] = mx[cnt] = mn[cnt] = v ;
rnd[cnt] = rand() ;
sz[cnt] = 1 ;
return cnt ;
}
int t[N] , s[N] ;
void pushup(int rt) {
mx[rt] = mn[rt] = val[rt] ;
if(ls(rt)) cmin(mn[rt] , mn[ls(rt)]) , cmax(mx[rt] , mx[ls(rt)]) ;
if(rs(rt)) cmin(mn[rt] , mn[rs(rt)]) , cmax(mx[rt] , mx[rs(rt)]) ;
sz[rt] = sz[ls(rt)] + sz[rs(rt)] + 1 ;
t[rt] = min(t[ls(rt)] , t[rs(rt)]) , cmin(t[rt] , s[rt]) ;
}
int merge(int u , int v) {
if(! u || ! v) return u | v ;
if(rnd[u] < rnd[v]) {
rs(u) = merge(rs(u) , v) ;
pushup(u) ;
return u ;
} else {
ls(v) = merge(u , ls(v)) ;
pushup(v) ;
return v ;
}
}
void split(int cur , int k , int & u , int & v) {
if(! cur) {
u = v = 0 ;
return ;
}
if(k <= sz[ls(cur)]) {
v = cur ;
split(ls(v) , k , u , ls(v)) ;
} else {
u = cur ;
split(rs(u) , k - sz[ls(u)] - 1 , rs(u) , v) ;
}
pushup(cur) ;
}
void ins(int k , int v) {
int x , y , z , xx ;
split(rt , k - 1 , x , y) ;
split(y , 1 , y , z) ;
split(z , 1 , z , xx) ;
int now = newnode(v) ;
t[now] = s[now] = abs(val[now] - val[y]) ;
if(! y) {
t[now] = s[now] = inf ;
}
t[z] = s[z] = abs(val[z] - val[now]) ;
if(! z) {
t[z] = s[z] = inf ;
}
rt = merge(merge(merge(merge(x , y) , now) , z) , xx) ;
}
void _merge(int k , int v) {
int x , y , z , xx ;
split(rt , k - 1 , x , y) ;
split(y , 1 , y , z) ;
split(z , 1 , z , xx) ;
rt = merge(x , xx) ;
ins(k - 1 , v) ;
}
int qrymax(int l , int r) {
int x , y , z ;
split(rt , r , x , z) ;
split(x , l - 1 , x , y) ;
int res = mx[y] - mn[y] ;
rt = merge(merge(x , y) , z) ;
return res ;
}
int qrymin(int l , int r) {
++ l ;
int x , y , z ;
split(rt , r , x , z) ;
split(x , l - 1 , x , y) ;
int res = t[y] ;
rt = merge(merge(x , y) , z) ;
return res ;
}
void dfs(int u) {
if(ls(u)) dfs(ls(u)) ;
out << val[u] << '\n' ;
if(rs(u)) dfs(rs(u)) ;
}
signed main() {
#ifdef _WIN64
freopen("testdata.in" , "r" , stdin) ;
#endif
in >> n >> m ;
rep(i , 1 , n) in >> a[i] ;
rt = newnode(a[1]) ;
t[rt] = s[rt] = inf ;
rep(i , 2 , n) ins(i - 1 , a[i]) ;
rep(i , 1 , m) {
string s ;
in >> s ;
int x , y ;
in >> x >> y ;
if(s == "max") out << qrymax(x , y) << '\n' ;
if(s == "min") out << qrymin(x , y) << '\n' ;
if(s == "merge") _merge(x , y) ;
if(s == "insert") ins(x , y) ;
}
return out.flush(), 0;
}
#4864. [BeiJing 2017 Wc]神秘物质 [FHQ Treap]的更多相关文章
-
BZOJ 4864: [BeiJing 2017 Wc]神秘物质 解题报告
4864: [BeiJing 2017 Wc]神秘物质 Description 21ZZ 年,冬. 小诚退休以后, 不知为何重新燃起了对物理学的兴趣. 他从研究所借了些实验仪器,整天研究各种微观粒子. ...
-
BZOJ 4864: [BeiJing 2017 Wc]神秘物质 (块状链表/平衡树 )
这就是一道数据结构裸题啊,最大极差就是区间最大值减最小值,最小极差就是相邻两个数差的最小值.然后平衡树splay/treap或者块状链表维护就行了. 第一次自己写块状链表,蛮好写,就是长..然后就BZ ...
-
BZOJ_4864_[BeiJing 2017 Wc]神秘物质_Splay
BZOJ4864_[BeiJing 2017 Wc]神秘物质_Splay Description 21ZZ 年,冬. 小诚退休以后, 不知为何重新燃起了对物理学的兴趣. 他从研究所借了些实验仪器,整天 ...
-
【BZOJ4864】[BeiJing 2017 Wc]神秘物质 Splay
[BZOJ4864][BeiJing 2017 Wc]神秘物质 Description 21ZZ 年,冬. 小诚退休以后, 不知为何重新燃起了对物理学的兴趣. 他从研究所借了些实验仪器,整天研究各种微 ...
-
BZOJ4864[BeiJing 2017 Wc]神秘物质——非旋转treap
题目描述 21ZZ 年,冬. 小诚退休以后, 不知为何重新燃起了对物理学的兴趣. 他从研究所借了些实验仪器,整天研究各种微观粒子.这 一天, 小诚刚从研究所得到了一块奇异的陨石样本, 便迫不及待地开始 ...
-
[bzoj4864][BeiJing 2017 Wc]神秘物质
来自FallDream的博客,未经允许,请勿转载,谢谢. 21ZZ 年,冬. 小诚退休以后, 不知为何重新燃起了对物理学的兴趣. 他从研究所借了些实验仪器,整天研究各种微观粒子.这 一天, 小诚刚从研 ...
-
BZOJ4864 BeiJing 2017 Wc神秘物质(splay)
splay维护区间最大值.最小值.相邻两数差的绝对值的最小值即可. #include<iostream> #include<cstdio> #include<cmath& ...
-
BZOJ4864: [BeiJing 2017 Wc]神秘物质(Splay)
Description 21ZZ 年,冬. 小诚退休以后, 不知为何重新燃起了对物理学的兴趣. 他从研究所借了些实验仪器,整天研究各种微观粒子.这 一天, 小诚刚从研究所得到了一块奇异的陨石样本, 便 ...
-
[bzoj4864][BeiJing2017Wc]神秘物质_非旋转Treap
神秘物质 bzoj-4864 BeiJing-2017-Wc 题目大意:给定一个长度为n的序列,支持插入,将相邻两个元素合并并在该位置生成一个指定权值的元素:查询:区间内的任意一段子区间的最大值减最小 ...
随机推荐
-
Android调用微信登陆、分享、支付
前言:用了微信sdk各种痛苦,感觉比qq sdk调用麻烦多了,回调过于麻烦,还必须要在指定包名下的actvity进行回调,所以我在这里写一篇博客,有这个需求的朋友可以借鉴一下,以后自己别的项目有用到也 ...
-
php广告图片循环播放 幻灯片效果
<!DOCTYPE> <html> <head> <meta http-equiv="content-type" content=&quo ...
-
jxl读数据库数据生成xls 并下载
1.所需jar jxl-2.6.10.jar jxls-core-1.0-RC-3.jar jxls-reader-1.0-RC-3.jar 2. excel修改行宽度封装 SheetColumn.j ...
-
C的文件操作
文件文件的基本概念 所谓“文件”是指一组相关数据的有序集合. 这个数据集有一个名称,叫做文件名. 实际上在前面的各章中我们已经多次使用了文件,例如源程序文件.目标文件.可执行文件.库文件 (头文件)等 ...
-
soapui中文操作手册(一)----创建一个新的项目
1) 创建一个新的项目 点击项目,选择新建项目SOAP.这将打开一个新的SOAP项目对话框. 注意:你也可以做CTRL + N(WIN)或CMD+ N(MAC)来创建一个新的SOAP项目. 在新的SO ...
-
Coursera, Machine Learning, Anomoly Detection &; Recommender system
Algorithm: When to select Anonaly detection or Supervised learning? 总的来说guideline是如果positive e ...
-
【Android】ContentValues的用法
ContentValues 和HashTable类似都是一种存储的机制 但是两者最大的区别就在于,contenvalues只能存储基本类型的数据,像string,int之类的,不能存储对象这种东西,而 ...
-
Ajax cross domain
xhrFields:{ withCredentials:true}, https://*.com/questions/2054316/sending-credentials-w ...
-
【Java初探02】——Java语言基础
本篇博文就Java语言的一些基本元素进行一些记录和阐述,主要讲解一下Java语言的一些基本构成元素和Java的主类结构. Java语言基础的大致组成 java主类结构 基本的数据类型 变量与常量 运算 ...
-
linux系统开机自启程序-需要-root用户 -启动 -
#!/bin/bashsh /home/hwjc/RSA/release2017-02-23/release2017-02-23/install.shsh /etc/init.d/mqtt.shifc ...