2018.08.06bzoj1251: 序列终结者（非旋treap）

传送门
平衡树板子题。
直接fhqtreap打区间标记就行了。
代码：

#include
#define N 50005
using namespace std;
typedef pair<int,int> res;
inline int read(){int ans=0,w=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();return ans*w;
}
int n,m,cnt=0,rt=0,val[N],son[N][2],siz[N],rev[N],rd[N],mx[N],add[N];
inline void pushup(int p){siz[p]=siz[son[p][0]]+siz[son[p][1]]+1;mx[p]=val[p];if(son[p][0])mx[p]=max(mx[p],mx[son[p][0]]);if(son[p][1])mx[p]=max(mx[p],mx[son[p][1]]);
}
inline int newnode(){siz[++cnt]=1,son[cnt][0]=son[cnt][1]=0;val[cnt]=rev[cnt]=add[N]=mx[cnt]=0,rd[cnt]=rand();return cnt;
}
inline void pushadd(int p,int v){add[p]+=v,mx[p]+=v,val[p]+=v;}
inline void pushrev(int p){swap(son[p][0],son[p][1]),rev[p]^=1;}
inline void pushdown(int p){if(rev[p]){if(son[p][0])pushrev(son[p][0]);if(son[p][1])pushrev(son[p][1]);rev[p]=0;}if(add[p]){if(son[p][0])pushadd(son[p][0],add[p]);if(son[p][1])pushadd(son[p][1],add[p]);add[p]=0;}
}
inline int merge(int a,int b){if(!a||!b)return a+b;pushdown(a),pushdown(b);if(rd[a]>=rd[b]){son[a][1]=merge(son[a][1],b),pushup(a);return a;}son[b][0]=merge(a,son[b][0]),pushup(b);return b;
}
inline res split(int p,int k){if(!p)return res(0,0);res tmp,ans;pushdown(p);if(siz[son[p][0]]>=k){tmp=split(son[p][0],k);ans.first=tmp.first,son[p][0]=tmp.second,pushup(ans.second=p);return ans;}tmp=split(son[p][1],k-siz[son[p][0]]-1);ans.second=tmp.second,son[p][1]=tmp.first,pushup(ans.first=p);return ans;
}
inline int rank(int p,int v){if(!p)return 0;pushdown(p); if(val[p]>v)return rank(son[p][0],v);return rank(son[p][1],v)+siz[son[p][0]]+1; 
}
inline void update(){int l=read(),r=read(),v=read();res x=split(rt,r),y=split(x.first,l-1);pushadd(y.second,v);rt=merge(merge(y.first,y.second),x.second);
}
inline void reverse(){int l=read(),r=read();res x=split(rt,r),y=split(x.first,l-1);pushrev(y.second);rt=merge(merge(y.first,y.second),x.second);
}
inline void query(){int l=read(),r=read();res x=split(rt,r),y=split(x.first,l-1);printf("%d\n",mx[y.second]);rt=merge(merge(y.first,y.second),x.second);
}
inline void ins(){int p=newnode();rt=merge(rt,p);
}
int main(){n=read(),m=read();for(int i=1;i<=n;++i)ins();while(m--){int op=read();if(op==1)update();if(op==2)reverse();if(op==3)query();}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！