hdu1754 I Hate It

给个传送门

AC的第一个线段树的题目，但不是做的第一个线段树题目。原来做过一两道吧，杭电上有一道，不过线段树超时了。。要用树状数组做，所以一直还没AC

这道题目写代码的时候，让我对于二分，和递归这两个重要思想都有了比较清晰的认识。

二分呢，一定要确定好两个部分的边界。决不能重复边界。

递归呢，注意递归分为迭代（从上到下）和回溯（从下到上）两个过程的。我们经常忽略第二个过程。

#include <cstdio>
#define max(x,y) ((x)>(y)?(x):(y))
int max;

struct Node
{
	int L,R;
	int max;
	Node *pLeft,*pRight;
	Node(){
		pLeft=pRight=NULL;
		max=0;
	}
};/*很多人喜欢开个很大的节点数组来存放节点数据。左右儿子不是用指针而是用整型来存放数组下标。我不是很喜欢。我还是喜欢用指针。
不过有个坏处就是这样吃内存，每次都要记得销毁这个树*/
void initTree(Node *root,int L,int R)
{
	root->L=L;
	root->R=R;
	if(L!=R)
	{
		Node *LNode = new Node();
		Node *RNode = new Node();
		root->pLeft=LNode;
		root->pRight=RNode;
		initTree(LNode,L,(L+R)/2);
		initTree(RNode,(L+R)/2+1,R);
	}
}
void insert(Node *root,int i,int s)
{
	if(root->L==i&&root->R==i)
	{
		root->max=s;
		return ;
	}
	if(i<=(root->L+root->R)/2)
		insert(root->pLeft,i,s);
	else if(i>=(root->L+root->R)/2+1)	
		insert(root->pRight,i,s);
	root->max=max(root->pLeft->max,root->pRight->max);
}
void query(Node *root,int L,int R)
{
	if(root->max<max)
		return ;
	if(root->L==L&&root->R==R)
	{
		max=root->max;
		return ;
	}
	if((root->L+root->R)/2+1<=L)
		query(root->pRight,L,R);
	else if((root->L+root->R)/2>=R)
		query(root->pLeft,L,R);
	else 
	{
		query(root->pLeft,L,(root->L+root->R)/2);
		query(root->pRight,(root->L+root->R)/2+1,R);
	}
}
void deleTree(Node *root)
{
	if(root->pLeft)
		deleTree(root->pLeft);
	if(root->pRight)
		deleTree(root->pRight);
	delete(root);
}
int main()
{
	int n,m;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		Node *root = new Node();
		initTree(root,1,n);
		int tem;
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&tem);
			insert(root,i,tem);
		}
		getchar();
		char cmd;
		int s,e;
		for(int i=1;i<=m;i++){
			scanf("%c%d%d",&cmd,&s,&e);
			if(cmd=='Q')
			{
				max=0;
				query(root,s,e);
				printf("%d
",max);
			}
			else if(cmd=='U')
			{
				insert(root,s,e);
			}
			getchar();
		}
		deleTree(root);
	}
	return 0;
}