题目描述：给定一个长度为 n 的初始为 0 的序列，m 个操作，包括区间维护、区间翻转、区间最大值查询。n ≤ 50000，m ≤ 100000。
伸展树模板题。每个节点加上两个标记，伸展时下传标记即可。
代码如下：
#include"stdio.h" #define Exchange(a,b) \ { \ typeof(a) __tmp_a=a; \ a=b,b=__tmp_a; \ } #define Max_Integer(a,b) \ ({ \ int __tmp_a=(a),__tmp_b=(b); \ __tmp_a>__tmp_b?__tmp_a:__tmp_b; \ }) struct SPLAY_TREE_NODE *NIL; struct SPLAY_TREE_NODE { int add,flag,key,mx,size; SPLAY_TREE_NODE *child[2]; SPLAY_TREE_NODE(int k,int s) { add=flag=mx=0; child[0]=child[1]=NIL; key=k; size=s; } void pushdown() { if(add!=0) { mx+=add; key+=add; if(child[0]!=NIL) child[0]->add+=add; if(child[1]!=NIL) child[1]->add+=add; add=0; } if(flag==1) { flag=0; Exchange(child[0],child[1]); if(child[0]!=NIL) child[0]->flag^=1; if(child[1]!=NIL) child[1]->flag^=1; } } }; void UpMax(SPLAY_TREE_NODE *now,SPLAY_TREE_NODE *end,int chi) { if(now==end) return; UpMax(now->child[chi],end,chi); now->mx=Max_Integer(now->key,Max_Integer(now->child[0]->add+now->child[0]->mx,now->child[1]->add+now->child[1]->mx)); } SPLAY_TREE_NODE* Splay(SPLAY_TREE_NODE *now,int rak) { SPLAY_TREE_NODE *Header=new SPLAY_TREE_NODE(0,now->size+1),*next,*SubTree[2]; SubTree[0]=Header; SubTree[1]=Header->child[1]=new SPLAY_TREE_NODE(0,rak); now->pushdown(); while(rak!=now->child[0]->size+1) { int chi=rak<now->child[0]->size+1?0:1; rak-=chi>0?now->child[0]->size+1:0; if((next=now->child[chi])==NIL) break; now->child[chi]=NIL; SubTree[chi]->child[chi]=now; now->size=SubTree[chi]->size-SubTree[chi]->child[1-chi]->size-1; SubTree[chi]=now; now=next; now->pushdown(); } SubTree[0]->child[0]=now->child[1]; SubTree[1]->child[1]=now->child[0]; UpMax(Header->child[1]->child[1],now->child[0],1); UpMax(Header->child[0],now->child[1],0); now->child[0]=Header->child[1]->child[1]; now->child[1]=Header->child[0]; now->mx=Max_Integer(now->child[0]->add+now->child[0]->mx,now->child[1]->add+now->child[1]->mx); now->size=now->child[0]->size+now->child[1]->size+1; return now; } SPLAY_TREE_NODE* Build(int left,int right) { if(left>=right) return NIL; int middle=(left+right)/2; SPLAY_TREE_NODE *now=new SPLAY_TREE_NODE(0,right-left); now->child[0]=Build(left,middle); now->child[1]=Build(middle+1,right); return now; } int main() { NIL=new SPLAY_TREE_NODE(0,0); NIL->child[0]=NIL->child[1]=NIL; NIL->mx=-0x80000000; SPLAY_TREE_NODE *now,*stroot; int k,l,m,n,r,v; scanf("%d %d",&n,&m); stroot=Build(1,n+1); while(m--) { scanf("%d %d %d",&k,&l,&r); if(l!=1) if(r!=n) stroot=Splay(stroot,l-1), stroot->child[1]=Splay(stroot->child[1],r-stroot->child[0]->size), now=stroot->child[1]->child[0]; else stroot=Splay(stroot,l-1), now=stroot->child[1]; else if(r!=n) stroot=Splay(stroot,r+1), now=stroot->child[0]; else now=stroot; switch(k) { case 1:scanf("%d",&v);now->add+=v;break; case 2:now->flag^=1;break; case 3:printf("%d\n",now->add+now->mx);break; } } return 0; }