首页 > 代码库 > BZOJ 1251 序列终结者 Splay
BZOJ 1251 序列终结者 Splay
题目大意:维护一种数据结构,支持下列操作:
1.将一个区间加上一个数
2.将一个区间翻转
3.询问一段区间的最大值
Splay裸题 OTZ题干……
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 50500 using namespace std; struct abcd{ abcd *ls,*rs,*fa; int num,max_num; int size; int add_mark; bool rev_mark; void Push_Up(); void Push_Down(); void Add(int x); void Reverse(); abcd(int x); }*null=new abcd(0xefefefef),*root; int n,m; abcd :: abcd(int x) { ls=rs=fa=null; num=max_num=x; size=null?1:0; add_mark=0; rev_mark=0; } void abcd :: Push_Up() { size=ls->size+rs->size+1; max_num=max( max(ls->max_num,rs->max_num),num ); } void abcd :: Push_Down() { if(rev_mark) { ls->Reverse(); rs->Reverse(); rev_mark=0; } if(add_mark) { ls->Add(add_mark); rs->Add(add_mark); add_mark=0; } } void abcd :: Add(int x) { if(this==null) return ; num+=x; max_num+=x; add_mark+=x; } void abcd :: Reverse() { swap(ls,rs); rev_mark^=1; } void Zig(abcd *x) { abcd *y=x->fa; y->ls=x->rs; x->rs->fa=y; x->rs=y; x->fa=y->fa; if(y==y->fa->ls) y->fa->ls=x; else if(y==y->fa->rs) y->fa->rs=x; y->fa=x; y->Push_Up(); if(y==root) root=x; } void Zag(abcd *x) { abcd *y=x->fa; y->rs=x->ls; x->ls->fa=y; x->ls=y; x->fa=y->fa; if(y==y->fa->ls) y->fa->ls=x; else if(y==y->fa->rs) y->fa->rs=x; y->fa=x; y->Push_Up(); if(y==root) root=x; } void Splay(abcd *x,abcd *tar) { while(1) { abcd *y=x->fa,*z=y->fa; if(y==tar) break; if(z==tar) { if(x==y->ls) Zig(x); else Zag(x); break; } if(x==y->ls) { if(y==z->ls) Zig(y); Zig(x); } else { if(y==z->rs) Zag(y); Zag(x); } } x->Push_Up(); } void Find(abcd *x,int y,abcd *z) { while(1) { int temp=x->ls->size; x->Push_Down(); if(y<=temp) x=x->ls; else { y-=temp; if(y==1) break; --y; x=x->rs; } } Splay(x,z); } abcd* Build_Tree(int x,int y) { int mid=x+y>>1; if(x>y) return null; abcd *re=new abcd(0); re->ls=Build_Tree(x,mid-1); re->rs=Build_Tree(mid+1,y); re->ls->fa=re->rs->fa=re; return re->Push_Up(),re; } void Initialize() { root=new abcd(19980402); root->rs=new abcd(19980402); root->rs->ls=Build_Tree(1,n); root->rs->ls->fa=root->rs; root->rs->fa=root; root->rs->Push_Up(); root->Push_Up(); } void Add() { int x,y,z; scanf("%d%d%d",&x,&y,&z); Find(root,x,null); Find(root,y+2,root); root->rs->ls->Add(z); } void Reverse() { int x,y; scanf("%d%d",&x,&y); Find(root,x,null); Find(root,y+2,root); root->rs->ls->Reverse(); } void Query() { int x,y; scanf("%d%d",&x,&y); Find(root,x,null); Find(root,y+2,root); printf("%d\n",root->rs->ls->max_num); } int main() { int i,p; cin>>n>>m; Initialize(); for(i=1;i<=m;i++) { scanf("%d",&p); switch(p) { case 1:Add();break; case 2:Reverse();break; case 3:Query();break; } } }
BZOJ 1251 序列终结者 Splay
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。