【BZOJ1500】维修数列

  想要写题练练手，于是就盯准了这个维修数列...

  一直都很害怕写线段树，现在看来用不着写线段树了

  写完心情愉悦...然而被求0个数的和之类的数据恶心到了...

  总体来说代码一遍敲下来没什么问题还是很鼓舞人心的。

  记录一下当时写出错误总结出的心得：

    1.Rotate操作时关于每个节点的父亲节点和儿子节点的变更。先更新fa的fa的儿子节点，再更新旋转节点的子节点的fa，然后再处理那两个旋转的节点。

  借(chao)鉴(xi)了一下陈老师的代码。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long LL;
const int maxn=500010,inf=~0U>>1;
using namespace std;

struct Node
{
	Node *c[2],*p;
	int size;
	int v,sum;
	int lmax,rmax,vmax;
	bool tag_same,tag_rev;
	int samev;

	bool w() {return p->c[1]==this;}
}*root,*Null;

namespace Memory
{
	Node Mem[maxn];
	Node *Stack[maxn];
	int top;

	void Memory_Init() {for (int i=0;i<maxn;i++) Stack[i]=&Mem[i];top=maxn-1;}
	void Delete_Node(Node *t) {Stack[++top]=t;}
	Node* New_Node() {return Stack[top--];}
};

struct Splay_Tree
{
	#define ls x->c[0]
	#define rs x->c[1]
	void Update(Node *x)
	{
		if (x==Null) return;
		x->sum=ls->sum+rs->sum+x->v;
		x->size=ls->size+rs->size+1;
		int L_rmax=max(ls->rmax,0),R_lmax=max(rs->lmax,0);
		x->lmax=max(ls->lmax,ls->sum+x->v+R_lmax);
		x->rmax=max(rs->rmax,rs->sum+x->v+L_rmax);
		x->vmax=max(ls->vmax,rs->vmax);
		x->vmax=max(x->vmax,L_rmax+x->v+R_lmax);
	}

	void Update_Same(Node *x,int samev)
	{
		if (x==Null) return;
		x->v=samev;
		x->sum=x->size*samev;
		x->lmax=x->rmax=x->vmax=max(x->sum,samev);
		x->samev=samev;
		x->tag_same=1;
	}

	void Update_Rev(Node *x)
	{
		if (x==Null) return;
		swap(ls,rs);
		swap(x->lmax,x->rmax);
		x->tag_rev^=1;
	}

	void Push_Down(Node *x)
	{
		if (x->tag_same)
		{
			Update_Same(ls,x->samev);
			Update_Same(rs,x->samev);
			x->tag_same=0;
			x->samev=0;
		}
		if (x->tag_rev)
		{
			Update_Rev(ls);
			Update_Rev(rs);
			x->tag_rev=0;
		}
	}

	void Rotate(Node *x)
	{
		Node *p=x->p;
		Push_Down(p);Push_Down(x);
		bool w=x->w();
		p->p->c[p->w()]=x;
		x->p=p->p;p->c[w]=x->c[!w];
		x->c[!w]->p=p;
		x->c[!w]=p;p->p=x;
		Update(p);
		if (p==root) root=x;
	}

	void Splay(Node *x,Node *head) 
	{
		if (x==Null) return;
		Push_Down(x);
		while (x->p!=head)
			if (x->p->p==head) Rotate(x);
		else if (x->w()==x->p->w()) Rotate(x->p),Rotate(x);
			else Rotate(x),Rotate(x);
		Update(x);
	}

	Node* Select(int kth)
	{
		Node *x=root;
		while (kth)
		{
			Push_Down(x);
			int lsize=ls->size;
			if (lsize+1==kth) return x;
			if (kth>lsize) kth-=lsize+1,x=rs;
			else x=ls;
		}
		return x;
	}

	Node* Get_Seq(int l,int r)
	{
		if (l==1 && r==root->size) return root;
		if (l==1 && r< root->size) {Splay(Select(r+1),Null);return root->c[0];}
		if (l> 1 && r==root->size) {Splay(Select(l-1),Null);return root->c[1];}
		Splay(Select(l-1),Null);
		Splay(Select(r+1),root);
		return root->c[1]->c[0];
	}

	void Mark_Same(Node *x,int samev)
	{
		Update_Same(x,samev);
		Splay(x,Null);
	}

	void Mark_Rev(Node *x)
	{
		Update_Rev(x);
		Splay(x,Null);
	}

	Node* New_Node(int v)
	{
		Node *x=Memory::New_Node();
		x->v=v;
		x->samev=x->tag_same=x->tag_rev=0;
		return x;
	}

	Node* Make_Tree(int *a,int l,int r)
	{
		if (l>r) return Null;
		int mid=(l+r)>>1;
		Node *x=New_Node(a[mid]);
		ls=Make_Tree(a,l,mid-1);
		rs=Make_Tree(a,mid+1,r);
		if (ls!=Null) ls->p=x;
		if (rs!=Null) rs->p=x;
		Update(x);
		return x;
	}

	Splay_Tree()
	{
		Memory::Memory_Init();
		Null=Memory::New_Node();
		Null->v=Null->sum=Null->size=Null->samev=0;
		Null->tag_same=Null->tag_rev=0;
		Null->lmax=Null->rmax=Null->vmax=-inf;
		Null->p=Null->c[0]=Null->c[1]=NULL;
		root=Null;
	}

	void Insert(int *a,int posi,int tot)
	{
		Node *x=Make_Tree(a,1,tot);
		if (root==Null) root=x,root->p=Null,Null->c[0]=root;
		else if (posi==root->size) {
			Splay(Select(root->size),Null);
			root->c[1]=x;
			x->p=root;
			Update(root);
		} else if (posi==0) {
			Splay(Select(1),Null);
			root->c[0]=x;
			x->p=root;
			Update(root);
		} else {
			Splay(Select(posi),Null);
			Splay(Select(posi+1),root);
			root->c[1]->c[0]=x;
			x->p=root->c[1];
			Splay(x,Null);
		}
	}

	void Delete_DFS(Node *x)
	{
		if (ls!=Null) Delete_DFS(ls);
		if (rs!=Null) Delete_DFS(rs);
		Memory::Delete_Node(x);
	}

	void Delete(int posi,int tot)
	{
		Node *x=Get_Seq(posi,posi+tot-1);
		if (x==root) root=Null;
		else x->p->c[x->w()]=Null,Splay(x->p,Null);
		Delete_DFS(x);
	}

	void Make_Same(int posi,int tot,int c)
	{
		Node *x=Get_Seq(posi,posi+tot-1);
		Mark_Same(x,c);
		Splay(x,Null);
	}

	void Make_Rev(int posi,int tot)
	{
		Node *x=Get_Seq(posi,posi+tot-1);
		Mark_Rev(x);
		Splay(x,Null);
	}

	void Get_Sum(int posi,int tot)
	{
		Node *x=Get_Seq(posi,posi+tot-1);
		printf("%d\n",x->sum);
		Splay(x,Null);
	}

	void Max_Sum()
	{
		printf("%d\n",(root==Null)?0:root->vmax);
	}
	
	void Print(Node *x)
	{
		if (x==Null) {if (x==root) printf("\n");return;}
		Push_Down(x);
		Print(ls);
		printf("%d ",x->v);
		Print(rs);
		if (x==root) printf("\n");
	}
}T;

int a[maxn];
char ctr[20];
int n,m;

inline void read(int &x)
{
	char ch;
	int flag=0;
	while (((ch=getchar())<'0' || ch>'9') && ch!='-');
	if (ch=='-') flag=-1,x=0;
	else flag=1,x=ch-'0';
	while ((ch=getchar())<='9' && ch>='0') x=x*10+ch-'0';
	x=x*flag;
}

int main()
{
	read(n),read(m);
	for (int i=1;i<=n;i++) read(a[i]);
	T.Insert(a,0,n);
	for (int i=1;i<=m;i++)
	{
		scanf("%s",ctr+1);
		int tot,posi,c;
		if (ctr[1]=='I') {read(posi),read(tot);for (int i=1;i<=tot;i++) read(a[i]);T.Insert(a,posi,tot);}
		else if (ctr[1]=='D') {read(posi),read(tot);T.Delete(posi,tot);}
		else if (ctr[1]=='R') {read(posi),read(tot);T.Make_Rev(posi,tot);}
		else if (ctr[1]=='G') {read(posi),read(tot);T.Get_Sum(posi,tot);}
		else if (ctr[3]=='K') {read(posi),read(tot),read(c);T.Make_Same(posi,tot,c);}
		else T.Max_Sum();
		//T.Print(root);
	}
	return 0;
}