学步园

题目大意：维护区间的最大值，要求可以区间翻转和区间加减。

思路：弱化版的1500，好长时间没写带标记的Splay了，错误重重。这个题可以当作带标记的Splay模板了。

CODE：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define INF 0x3f3f3f3f
#define WORKPATH (root->son[1]->son[0])
using namespace std;

struct SplayTree{
	int val,size;
	int change,_max;
	bool reverse;
	SplayTree *son[2],*father;
	
	SplayTree(int _);
	bool Check() {
		return father->son[1] == this;
	}
	void Combine(SplayTree *a,bool dir) {
		son[dir] = a;
		a->father = this;
	}
	void Plus(int c);
	void Reverse();
	void PushUp();
	void PushDown();
}none(0),*nil = &none,*root;
SplayTree:: SplayTree(int _) {
	val = _;
	size = 1;
	_max = change = 0;
	reverse = false;
	son[0] = son[1] = nil;
}
void SplayTree:: Plus(int c) {
	if(this == nil)	return ;
	change += c;
	val += c;
	_max += c;
}
void SplayTree:: Reverse() {
	if(this == nil)	return ;
	reverse ^= 1;
	swap(son[0],son[1]);
}
void SplayTree:: PushUp() {
	if(this == nil)	return ;
	size = son[0]->size + son[1]->size + 1;
	_max = max(val,max(son[0]->_max,son[1]->_max));
}
void SplayTree:: PushDown() {
	if(this == nil)	return ;
	if(change) {
		son[0]->Plus(change);
		son[1]->Plus(change);
		change = 0;
	}
	if(reverse) {
		son[0]->Reverse();
		son[1]->Reverse();
		reverse = false;
	}
}

int cnt,asks;

SplayTree *BuildTree(int l,int r)
{
	if(r < l)	return nil;
	int mid = (l + r) >> 1;
	SplayTree *re = new SplayTree(0);
	re->Combine(BuildTree(l,mid - 1),false);
	re->Combine(BuildTree(mid + 1,r),true);
	re->PushUp();
	return re;
}

void Pretreatment()
{
	nil->size = 0;
	nil->father = nil;
	nil->val = nil->_max = -INF;
	root = BuildTree(0,cnt + 1);
	root->father = nil;
}

inline void Rotate(SplayTree *a,bool dir)
{
	SplayTree *f = a->father;
	f->PushDown(),a->PushDown();
	f->son[!dir] = a->son[dir];
	f->son[!dir]->father = f;
	a->son[dir] = f;
	f->father->son[f->Check()] = a;
	a->father = f->father;
	f->father = a;
	f->PushUp();
	if(root == f)	root = a;
}

inline void Splay(SplayTree *a,SplayTree *aim)
{
	while(a->father != aim) {
		if(a->father->father == aim)
			Rotate(a,!a->Check());
		else if(!a->father->Check()) {
			if(!a->Check())
				Rotate(a->father,true),Rotate(a,true);
			else	Rotate(a,false),Rotate(a,true);
		}
		else {
			if(a->Check())
				Rotate(a->father,false),Rotate(a,false);
			else	Rotate(a,true),Rotate(a,false);
		}
	}
	a->PushUp();
}

SplayTree *Kth(SplayTree *a,int k)
{
	a->PushDown();
	if(k <= a->son[0]->size)	return Kth(a->son[0],k);
	k -= a->son[0]->size;
	if(k == 1)	return a;
	return Kth(a->son[1],k - 1);
}

inline void SplaySeg(int x,int y)
{
	x++,y++;
	Splay(Kth(root,x - 1),nil);
	Splay(Kth(root,y + 1),root);
}

int main()
{
	cin >> cnt >> asks;
	Pretreatment();
	for(int flag,x,y,z,i = 1; i <= asks; ++i) {
		scanf("%d",&flag);
		if(flag == 1) {
			scanf("%d%d%d",&x,&y,&z);
			SplaySeg(x,y);
			WORKPATH->Plus(z);
			root->son[1]->PushUp();
			root->PushUp();
		}
		else if(flag == 2) {
			scanf("%d%d",&x,&y);
			SplaySeg(x,y);
			WORKPATH->Reverse();
		}
		else {
			scanf("%d%d",&x,&y);
			SplaySeg(x,y);
			printf("%d\n",WORKPATH->_max);
		}
	}
	return 0;
}