Description 给定一个长度为N的序列，每个序列的元素是一个整数。要支持以下三种操作： 1. 将[L,R]这个区间内的所有数加上V。 2. 将[L,R]这个区间翻转，比如1 2 3 4变成4 3 2 1。 3. 求[L,R]这个区间中的最大值。 最开始所有元素都是0。
Input 第一行两个整数N，M。M为操作个数。 以下M行，每行最多四个整数，依次为K，L，R，V。K表示是第几种操作，如果不是第1种操作则K后面只有两个数。
Output 对于每个第3种操作，给出正确的回答。
Sample Input 4 4 1 1 3 2 1 2 4 -1 2 1 3 3 2 4
Sample Output 2
数据范围 N<=50000，M<=100000。
题目解析 Splay裸题，模板借用KikiDMW的。
#include <cstdio> #include <iostream> #include <cstdlib> #include <algorithm> using namespace std ; const int N=50010; const int oo=1000000000; struct Node { int a,tag,siz,rev,mx,id; Node *ch[2],*fa; int d (){ return fa->ch[1] == this; } void sc (Node *x,int d){ (ch[d]=x)->fa=this; } void add (int x){ tag+=x; a+=x; mx+=x; } void pup (){ siz=ch[0]->siz+ch[1]->siz+1; mx=max (a,max (ch[1]->mx,ch[0]->mx)); } void pdw (); }nil[N],*root; void Node::pdw (){ if (tag){ if (ch[0]!=nil) ch[0]->add(tag); if (ch[1]!=nil) ch[1]->add(tag); tag=0; } if (rev){ ch[0]->rev^=1; ch[1]->rev^=1; swap (ch[0],ch[1]); rev=0; } } int n,m; void rotate (Node *x,Node *&k){ int d=x->d (); Node *p=x->fa; p->sc(x->ch[!d],d); if (p==k){ x->fa=k->fa; k=x; } else p->fa->sc (x,p->d()); x->sc (p,!d); p->pup (); x->pup (); } void splay (Node *x,Node *&k){ for (Node *y;x!=k;){ if ((y=x->fa)!=k) y->fa->pdw (); y->pdw (); x->pdw (); if (y!=k)(x->d ()^y->d ()) ? rotate (x,k) : rotate (y,k); rotate (x,k); } x->pup (); } Node * search (int k){ Node *p=root; while (1){ p->pdw (); int t=p->ch[0]->siz; if (t>=k) p=p->ch[0]; else { if (t+1<k) { k-=t+1; p=p->ch[1]; } else break; } } return p; } void build_tree (int l,int r,Node *tree,int d){ if (l>r){ tree->ch[d]=nil; return ; } Node *u; if (l==r){ u=nil+l; u->id=l; u->fa=tree; u->siz=1; u->ch[0]=u->ch[1]=nil; tree->ch[d]=u; return ; } int mid=(l+r)>>1; u=nil+mid; build_tree (l,mid-1,u,0); build_tree (mid+1,r,u,1); u->id=mid; u->fa=tree; u->pup(); tree->ch[d]=u; } void update (int l,int r,int val){ Node *u=search (l-1),*v=search (r+1); splay (u,root); splay (v,root->ch[1]); Node *w=v->ch[0]; w->add (val); } void rever (int l,int r){ Node *u=search (l-1),*v=search (r+1); splay (u,root); splay (v,root->ch[1]); Node *w=v->ch[0]; w->rev^=1; } void query (int l,int r){ Node *u=search (l-1),*v=search (r+1); splay (u,root); splay (v,root->ch[1]); Node *w=v->ch[0]; printf ("%d\n",w->mx); } void init (){ scanf ("%d %d",&n,&m); } int main (){ init (); int i,j,k,l,q; nil->ch[0]=nil->ch[1]=nil->fa=nil; nil->a=nil->mx=-oo; build_tree(1,n+2,nil,0); root=nil+((n+3)/2); for (i=1;i<=m;i++){ scanf ("%d",&q); if (q==1){ scanf ("%d %d %d",&j,&k,&l); update (j+1,k+1,l); } if (q==2){ scanf ("%d %d",&j,&k); rever (j+1,k+1); } if (q==3){ scanf ("%d %d",&j,&k); query (j+1,k+1); } } return 0; }