首页 > 代码库 > 【bzoj1251】序列终结者
【bzoj1251】序列终结者
用魔法平衡树的实现!
反正没人会看的。
#include<bits/stdc++.h> #define rat 5 #define newnode(s,v,a,b) (&(*st[cnt++]=Node(s,v,a,b))) #define up(cur) pushdown(cur),pushup(cur),pushup(rt->lc),pushup(rt) #define N 400005 using namespace std; struct Node{ int size,val,rev,addv; Node *lc,*rc; Node(int s,int v,Node *a,Node *b):size(s),val(v),lc(a),rc(b),rev(0),addv(0){} Node(){} }*nul,*rt,*st[N],t[N]; int n,m,cnt; inline void pushdown(Node *o){ register Node *l=o->lc,*r=o->rc; if(o->addv){ if(!l->size)o->val+=o->addv; else l->addv+=o->addv,r->addv+=o->addv; o->addv=0; } if(o->rev){ if(l->size){ l->rev^=1;r->rev^=1; swap(o->lc,o->rc); }o->rev=0; } } inline void pushup(Node *o){ register Node *l=o->lc,*r=o->rc; if(l->size)o->size=l->size+r->size,o->val=max(l->val+l->addv,r->val+r->addv); } inline Node* merge(Node *a,Node *b){ pushdown(a);pushdown(b);pushup(a);pushup(b); return newnode(a->size+b->size,max(a->val,b->val),a,b); } void split(int x,Node *o){ pushdown(o); if(x>o->lc->size){ split(x-o->lc->size,o->rc);o->lc=merge(o->lc,o->rc->lc); st[--cnt]=o->rc;o->rc=o->rc->rc; } else if(x<o->lc->size){ split(x,o->lc);o->rc=merge(o->lc->rc,o->rc); st[--cnt]=o->lc;o->lc=o->lc->lc; } pushup(o); } Node* build(int l,int r){ if(l==r)return newnode(1,0,nul,nul); int mid=(l+r)>>1; return merge(build(l,mid),build(mid+1,r)); } inline Node* cut(int l,int r){ split(r,rt);split(l-1,rt->lc);return rt->lc->rc; } inline int read(){ int f=1,x=0;char ch; do{ch=getchar();if(ch==‘-‘)f=-1;}while(ch<‘0‘||ch>‘9‘); do{x=x*10+ch-‘0‘;ch=getchar();}while(ch>=‘0‘&&ch<=‘9‘); return f*x; } int main(){ n=read();m=read(); for(int i=0;i<=N;i++)st[i]=&t[i]; nul=new Node(0,0,0,0); rt=build(0,n+1); while(m--){ int opt=read(),l=read()+1,r=read()+1; Node* o=cut(l,r); if(opt==1){o->addv+=read();up(o);} if(opt==2){o->rev^=1;up(o);} if(opt==3){pushdown(o);pushup(o);printf("%d\n",o->val);} } }
【bzoj1251】序列终结者
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。