非旋treap模板
2024-10-19 02:17:12
bzoj3580
非旋转treap
在大神教导下发现split一段区间时先split右边再split左边比较好写
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cctype>
using namespace std;
typedef long long LL;
const int M=200007;
inline int rd(){
int x=0;bool f=1;char c=getchar();
for(;!isdigit(c);c=getchar())if(c=='-')f=0;
for(;isdigit(c);c=getchar())x=x*10-48+c;
return f?x:-x;
}
struct D{
int c[2];
D(){c[0]=c[1]=0;}
};
struct treap{
int sz,val,fix,mn,rev,tag,c[2];
void input(){
val=mn=rd();
fix=rand();
sz=1;
rev=tag=c[0]=c[1]=0;
}
}a[M];
int n,m,rt;
inline int min(int x,int y){
return x<y?x:y;
}
void update(int x){
a[x].mn=a[x].val,a[x].sz=1;
if(a[x].c[0]) a[x].mn=min(a[x].mn,a[a[x].c[0]].mn),a[x].sz+=a[a[x].c[0]].sz;
if(a[x].c[1]) a[x].mn=min(a[x].mn,a[a[x].c[1]].mn),a[x].sz+=a[a[x].c[1]].sz;
}
void totag(int x,int z){
a[x].tag+=z;
a[x].mn+=z;
a[x].val+=z;
}
void pushdown(int x){
if(a[x].rev){
if(a[x].c[0])a[a[x].c[0]].rev^=1;
if(a[x].c[1])a[a[x].c[1]].rev^=1;
a[x].rev^=1;
swap(a[x].c[0],a[x].c[1]);
}
if(a[x].tag){
if(a[x].c[0]) totag(a[x].c[0],a[x].tag);
if(a[x].c[1]) totag(a[x].c[1],a[x].tag);
a[x].tag=0;
}
}
int build(int l,int r){
if(l>r) return 0;
int mid=l+r>>1;
a[mid].c[0]=build(l,mid-1);
a[mid].c[1]=build(mid+1,r);
update(mid);
return mid;
}
D split(int x,int k){
D nw;
if(x==0)return nw;
pushdown(x);
if(a[a[x].c[0]].sz+1==k){
nw.c[1]=a[x].c[1];
a[x].c[1]=0;
nw.c[0]=x;
}
else if(k<=a[a[x].c[0]].sz){
nw=split(a[x].c[0],k);
a[x].c[0]=nw.c[1];
nw.c[1]=x;
}
else{
nw=split(a[x].c[1],k-a[a[x].c[0]].sz-1);
a[x].c[1]=nw.c[0];
nw.c[0]=x;
}
update(x);
return nw;
}
int merge(int x,int y){
if(!x) return y;
if(!y) return x;
if(a[x].fix<a[y].fix){
pushdown(x);
a[x].c[1]=merge(a[x].c[1],y);
update(x);
return x;
}
else{
pushdown(y);
a[y].c[0]=merge(x,a[y].c[0]);
update(y);
return y;
}
}
void add(int x,int y,int z){
D t2=split(rt,y);
D t1=split(t2.c[0],x-1);
totag(t1.c[1],z);
rt=merge(merge(t1.c[0],t1.c[1]),t2.c[1]);
}
void ins(int x,int z){
D tt=split(rt,x);
rt=merge(merge(tt.c[0],z),tt.c[1]);
}
void del(int x){
D t2=split(rt,x);
D t1=split(t2.c[0],x-1);
rt=merge(t1.c[0],t2.c[1]);
}
void get(int x,int y){
D t2=split(rt,y);
D t1=split(t2.c[0],x-1);
printf("%d\n",a[t1.c[1]].mn);
rt=merge(merge(t1.c[0],t1.c[1]),t2.c[1]);
}
void reverse(int x,int y){
D t2=split(rt,y);
D t1=split(t2.c[0],x-1);
a[t1.c[1]].rev^=1;
rt=merge(merge(t1.c[0],t1.c[1]),t2.c[1]);
}
void revolve(int x,int y,int z){
D t2=split(rt,y);
D t1=split(t2.c[0],x-1);
D tt=split(t1.c[1],z);
rt=merge(merge(merge(t1.c[0],tt.c[1]),tt.c[0]),t2.c[1]);
}
int main(){
int i,x,y,z;
char s[9];
n=rd();
for(i=1;i<=n;i++) a[i].input();
rt=build(1,n);
m=rd();
for(i=1;i<=m;i++){
scanf("%s",s);
if(s[0]=='A'){
x=rd(),y=rd(),z=rd();
add(x,y,z);
}
else if(s[0]=='I'){
x=rd();
a[++n].input();
ins(x,n);
}
else if(s[0]=='D'){
x=rd();
del(x);
}
else if(s[0]=='M'){
x=rd(),y=rd();
get(x,y);
}
else if(s[3]=='E'){
x=rd(),y=rd();
reverse(x,y);
}
else{
x=rd(),y=rd(),z=rd();
z=(z%(y-x+1)+(y-x+1))%(y-x+1);
z=(y-x+1)-z;
revolve(x,y,z);
}
}
return 0;
}
最新文章
- Gson---简单入门
- jekyll安装的斗智斗勇
- 载入条LoadingBar
- Centos下查看占用端口并关闭进程方法
- border-collapse实现表格细线边框
- noip知识点总结之--贪心
- git 如何恢复只是提交到本地的文件(或者commit)
- EMVTag系列7《静态签名数据》
- delphi 注册表操作(读取、添加、删除、修改)完全手册
- js/jquery获取浏览器窗口可视区域高度和宽度以及滚动条高度实现代码
- HDU 5050 Divided Land(进制转换)
- (转)addEventListener()与removeEventListener()详解
- js如何获取客户端IP
- vue有关小知识
- 单机千万级MQTT连接服务器测试报告
- 通用网页调用本地应用程序方案(windows平台)
- redis-python
- Oracle分析函数-keep(dense_rank first/last)
- Oracle表空间状态查询、意义及修改方式
- MVC实现删除数据库记录