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。
这道题是很明显的平衡树，所以当然可以用treap或者是splay来写，但是我写这道题主要是为了学习fhq treap的用法。
fhq treap所有的操作可以说都是用merge（合并）和spilt（分裂）来实现的。merge不难，难点是在spilt上。所以要加强练习啊。
merge函数返回的是两棵树合并后新树的地址，spilt函数记得加传值调用。
写的是指针版（这也是我用指针写的第一道题2333），其实也不难看懂。
具体实现细节看代码：
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> const int M=5e4+10; using namespace std; int n,m,k,l,r,v; struct node{ node *l,*r; int v,rnd,mx,size,rev,tag; void init(){rnd=rand();size=1;} void revs(){rev^=1;swap(l,r);} void add(int w){v+=w;tag+=w;mx+=w;} void dn(){ if(rev){ if(l)l->revs(); if(r)r->revs(); rev=0; } if(tag){ if(l)l->add(tag); if(r)r->add(tag); tag=0; } } void up(){ size=1;mx=v; if(l)mx=max(mx,l->mx),size+=l->size; if(r)mx=max(mx,r->mx),size+=r->size; } void spilt(node *&a,node *&b,int k){ if(!this){a=0;b=0;return;} int sz=l?l->size:0; dn(); if(k<=sz){ l->spilt(a,l,k); b=this; } else{ r->spilt(r,b,k-sz-1); a=this; } up(); } }tree[M],*rt; int read() { int ans=0,f=1;char c=getchar(); while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){ans=ans*10+c-48;c=getchar();} return ans*f; } node *merge(node *a,node *b) { if(!a)return b; if(!b)return a; if(a->rnd<b->rnd){ a->dn(); a->r=merge(a->r,b); a->up(); return a; } b->dn(); b->l=merge(a,b->l); b->up(); return b; } int main() { n=read();m=read(); for(int i=1;i<=n;i++)tree[i].init(),rt=merge(rt,tree+i); while(m--){ node *p1,*p2,*p3; k=read();l=read();r=read(); rt->spilt(p2,p3,r); p2->spilt(p1,p2,l-1); if(k==1) v=read(),p2->add(v); else if(k==2)p2->revs(); else printf("%d\n",p2->mx); rt=merge(merge(p1,p2),p3); } return 0; }
原文：http://www.cnblogs.com/JKAI/p/7260903.html
