这就是一道数据结构裸题啊,最大极差就是区间最大值减最小值,最小极差就是相邻两个数差的最小值。然后平衡树splay/treap或者块状链表维护就行了。
第一次自己写块状链表,蛮好写,就是长。。然后就BZOJ rank1了(2019.5.11求不打脸 )
CODE
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
char cb[1<<15],*cs=cb,*ct=cb;
#define getc() (cs==ct&&(ct=(cs=cb)+fread(cb,1,1<<15,stdin),cs==ct)?0:*cs++)
template<class T>inline void read(T &res) {
char ch; for(;!isdigit(ch=getc()););
for(res=ch-'0';isdigit(ch=getc());res=res*10+ch-'0');
}
const int Bsz = 500;
const int Cnt = 500;
const int inf = 0x3f3f3f3f;
stack<int>bin;
int n, q, num[MAXN], m;
struct Block{
int a[Bsz+5], use, nxt;
int mx, mn, d;
Block() {
memset(a, 0, sizeof a);
use = nxt = 0;
mx = 0, mn = d = inf;
}
inline void Clear() {
memset(a, 0, sizeof a);
use = nxt = 0;
mx = 0, mn = d = inf;
}
inline void getmax() {
mx = 0, mn = d = inf;
for(int i = 1; i <= use; ++i) {
mx = max(mx, a[i]),
mn = min(mn, a[i]);
if(i > 1) d = min(d, abs(a[i]-a[i-1]));
}
}
}b[Cnt+5];
inline int Query1(int x, int y) {
int l = 1;
while(x > b[l].use) x -= b[l].use, y -= b[l].use, l = b[l].nxt;
int r = l;
while(y > b[r].use) y -= b[r].use, r = b[r].nxt;
int Mx = 0, Mn = inf;
if(l == r) {
for(int i = x; i <= y; ++i)
Mx = max(Mx, b[l].a[i]),
Mn = min(Mn, b[l].a[i]);
return Mx-Mn;
}
for(int i = x; i <= b[l].use; ++i)
Mx = max(Mx, b[l].a[i]),
Mn = min(Mn, b[l].a[i]);
for(int i = 1; i <= y; ++i)
Mx = max(Mx, b[r].a[i]),
Mn = min(Mn, b[r].a[i]);
for(int i = b[l].nxt; i != r; i = b[i].nxt)
Mx = max(Mx, b[i].mx),
Mn = min(Mn, b[i].mn);
return Mx-Mn;
}
inline int Query2(int x, int y) {
int l = 1;
while(x > b[l].use) x -= b[l].use, y -= b[l].use, l = b[l].nxt;
int r = l;
while(y > b[r].use) y -= b[r].use, r = b[r].nxt;
int re = inf;
if(l == r) {
for(int i = x; i < y; ++i)
re = min(re, abs(b[l].a[i]-b[l].a[i+1]));
return re;
}
for(int i = x; i < b[l].use; ++i)
re = min(re, abs(b[l].a[i]-b[l].a[i+1]));
for(int i = 1; i < y; ++i)
re = min(re, abs(b[r].a[i]-b[r].a[i+1]));
for(int i = b[l].nxt; i != r; i = b[i].nxt)
re = min(re, b[i].d);
for(int i = l; i != r; i = b[i].nxt)
re = min(re, abs(b[i].a[b[i].use]-b[b[i].nxt].a[1]));
return re;
}
inline int Newnode() {
int re;
if(!bin.empty()) re = bin.top(), bin.pop();
else re = ++m;
b[re].Clear();
return re;
}
inline void Merge(int x, int val) {
int l = 1, pre = 0;
while(x > b[l].use) x -= b[l].use, pre = l, l = b[l].nxt;
if(x == b[l].use) {
int tmp = b[l].nxt;
b[tmp].a[1] = val;
b[tmp].getmax();
if(--b[l].use) b[l].getmax();
else b[pre].nxt = b[l].nxt, bin.push(l);
}
else {
b[l].a[x+1] = val;
--b[l].use;
for(int i = x; i <= b[l].use; ++i)
b[l].a[i] = b[l].a[i+1];
b[l].getmax();
}
}
inline void Insert(int x, int val) {
int l = 1, pre = 0;
while(x > b[l].use) x -= b[l].use, pre = l, l = b[l].nxt;
++b[l].use;
for(int i = b[l].use; i > x+1; --i) b[l].a[i] = b[l].a[i-1];
b[l].a[x+1] = val;
if(b[l].use > Bsz) {
int tmp = Newnode();
b[tmp].nxt = b[l].nxt; b[l].nxt = tmp;
b[tmp].use = b[l].use/2;
b[l].use -= b[tmp].use;
for(int i = 1; i <= b[tmp].use; ++i)
b[tmp].a[i] = b[l].a[b[l].use+i];
b[l].getmax(), b[tmp].getmax();
}
else b[l].getmax();
}
int main () {
read(n), read(q);
for(int i = 1; i <= n; ++i)
read(num[i]);
for(int i = 1; i*Bsz <= n; ++i) {
b[++m].use = Bsz; b[m-1].nxt = m;
for(int j = 1; j <= b[m].use; ++j)
b[m].a[j] = num[(m-1)*Bsz + j];
b[m].getmax();
}
if(n%Bsz) {
b[++m].use = n%Bsz; b[m-1].nxt = m;
for(int j = 1; j <= b[m].use; ++j)
b[m].a[j] = num[(m-1)*Bsz + j];
b[m].getmax();
}
char ch;
int x, y;
while(q--) {
while(!isalpha(ch=getc()));
ch=getc();
read(x), read(y);
switch(ch) {
case 'a':
printf("%d\n", Query1(x, y));
break;
case 'i':
printf("%d\n", Query2(x, y));
break;
case 'n':
Insert(x, y);
break;
case 'e':
Merge(x, y);
break;
}
}
}
BZOJ 4864: [BeiJing 2017 Wc]神秘物质 (块状链表/平衡树 )的更多相关文章
-
BZOJ 4864: [BeiJing 2017 Wc]神秘物质 解题报告
4864: [BeiJing 2017 Wc]神秘物质 Description 21ZZ 年,冬. 小诚退休以后, 不知为何重新燃起了对物理学的兴趣. 他从研究所借了些实验仪器,整天研究各种微观粒子. ...
-
#4864. [BeiJing 2017 Wc]神秘物质 [FHQ Treap]
这题其实挺简单的,有个东西可能稍微难维护了一点点.. \(merge\ x\ e\) 当前第 \(x\) 个原子和第 \(x+1\) 个原子合并,得到能量为 \(e\) 的新原子: \(insert\ ...
-
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]神秘物质
来自FallDream的博客,未经允许,请勿转载,谢谢. 21ZZ 年,冬. 小诚退休以后, 不知为何重新燃起了对物理学的兴趣. 他从研究所借了些实验仪器,整天研究各种微观粒子.这 一天, 小诚刚从研 ...
-
BZOJ4864[BeiJing 2017 Wc]神秘物质——非旋转treap
题目描述 21ZZ 年,冬. 小诚退休以后, 不知为何重新燃起了对物理学的兴趣. 他从研究所借了些实验仪器,整天研究各种微观粒子.这 一天, 小诚刚从研究所得到了一块奇异的陨石样本, 便迫不及待地开始 ...
-
BZOJ4864 BeiJing 2017 Wc神秘物质(splay)
splay维护区间最大值.最小值.相邻两数差的绝对值的最小值即可. #include<iostream> #include<cstdio> #include<cmath& ...
-
BZOJ4864: [BeiJing 2017 Wc]神秘物质(Splay)
Description 21ZZ 年,冬. 小诚退休以后, 不知为何重新燃起了对物理学的兴趣. 他从研究所借了些实验仪器,整天研究各种微观粒子.这 一天, 小诚刚从研究所得到了一块奇异的陨石样本, 便 ...
-
【BZOJ 1507】【NOI 2003】&;【Tyvj P2388】Editor 块状链表模板题
2016-06-18 当时关于块状链表的想法是错误的,之前维护的是一个动态的$\sqrt{n}$,所以常数巨大,今天才知道原因TwT,请不要参照这个程序为模板!!! 模板题水啊水~~~ 第一次写块状链 ...
随机推荐
-
LINQ To DataSet 示例
如果在项目遇到这样的问题如:DataTable1和DataTable2需要根据一定的规则进行合并成一个DataTable3. 问题1:DataTable1不是读数据库表的结果,而是合成的数据集,因此无 ...
-
httpclient4.3 工具类
httpclient4.3 java工具类. .. .因项目须要开发了一个工具类.正经常常使用的httpclient 请求操作应该都够用了 工具类下载地址:http://download.csdn. ...
-
源码安装zabbix遇到的报错集锦
报错1:checking for mysql_config... configure: error: MySQL library not found 解决办法:查找mysql_config #find ...
-
Docker 系列三(容器管理).
一.运行容器 1.基于镜像新建一个容器并启动 : tomcat:8.0 -i:交互式操作 -t:终端 -rm:容器退出后随之将其删除,可以避免浪费空间 -p :端口映射 -d :容器在后台运行 指明了 ...
-
C++ 11 创建和使用 unique_ptr
unique_ptr 不共享它的指针.它无法复制到其他 unique_ptr,无法通过值传递到函数,也无法用于需要副本的任何标准模板库 (STL) 算法.只能移动unique_ptr.这意味着,内存资 ...
-
pandas学习(常用数学统计方法总结、读取或保存数据、缺省值和异常值处理)
pandas学习(常用数学统计方法总结.读取或保存数据.缺省值和异常值处理) 目录 常用数学统计方法总结 读取或保存数据 缺省值和异常值处理 常用数学统计方法总结 count 计算非NA值的数量 de ...
-
org.apache.flink.runtime.entrypoint.StandaloneSessionClusterEntrypoint
org.apache.flink.runtime.entrypoint.StandaloneSessionClusterEntrypoint-Xms2024m -Xmx2024m -Dlog.file ...
-
jQuery实现的层级轮播图
<!DOCTYPE html> <html> <head lang="en"> <meta charset="UTF-8&quo ...
-
mysql的MyISAM 和 InnoDB 的区别?优化MYSQL数据库的方法?
MyISAM 和 InnoDB 的基本区别 1.InnoDB不支持FULLTEXT类型的索引. 2.InnoDB 中不保存表的具体行数,也就是说,执行select count(*) from tabl ...
-
CF1025C Plasticine zebra【环状字符串/思维】
给你一个长度为 \(\left|s\right|\) 的01串 \(s\) ,每次操作你可以任选一个 \(k\) ,使01串的 \([1,k]\) 和 \((k,\left|s\right|]\) 分 ...