学步园

Description

Little Ming很喜欢训练自己的快速读能力，他最近找到一种新的考验并训练快速读能力的方法，在一行具有很多数的数列里任意指定某一段长度，从左往右扫视一遍后说出这段数列中的最大值，但他不想一直只使用一个数列，所以他请了他的好朋友，一位非常喜欢编程的学生，Little Little来帮忙在原数列上时不时的做一些修改，给他出题并检验他的答案是否正确。Little Little在做修改操作时会选取某个点修改它的值，在做出题操作时给出某一段的左右端点。

Input

本题目包含多组测试，请处理到文件结束。

在每个测试的第一行，有两个正整数 N 和 M (  0<N<=200000,0<M<5000 )

第二行包含N个整数，代表初始时数列中的数据。

接下来有M行。每一行有一个字符 C (只取'Q'或'S') ，和两个正整数A，B。

当C为'Q'的时候，表示这是一条出题操作，A,B为端点下标值，有可能A比B大。

当C为'S'的时候，表示这是一条修改操作，要求把第A个数修改为B。

Output

对于每一次出题操作，在一行里面输出最大的数。

相邻2组测试之间要有一个空行。

Sample Input

5 6

1 2 3 4 5

Q 1 5

S 3 6

Q 3 4

Q 4 5

S 2 9

Q 1 5

Sample Output

5

6

5

9

这道题一开始做的时候暴力做的，TLE后来大神告诉说是线段树才知道，学了线段树之后自己写的代码也有很大压力。。。。

一开始交的时候总是runtime error，大神说一般原因有递归爆栈了，或者是数组越界，访问非法内存。还有就是用数组做线段树，空间要开四倍，我一开始开了两倍，然后还是runtime error 我自己找了找，改了改发现函数里有几个long int 被我写成int了。。改完就开始wa，把调用的n都改成了n-1,然后就过了……

总之，写的稀里糊涂的……

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<memory.h>
#include<limits.h>
using namespace std;
long a[200010],flag=0; 
struct tr
{
	long beg,end,max;
} b[800100]; 

int search(long be,long en,long w)
{
	long max,max2,x=b[w].beg,y=b[w].end;
	if(be==x&&en==y)
	      return b[w].max;
	else if(x==y)
		return b[w].max;
	x=(x+y)/2;
	y=2*w;
	if(be>x)
		max=search(be,en,y+1);
	else if(en<=x)
		max=search(be,en,y);
	else if(be<=x&&en>x)
	{
		max=search(be,x,y);
		max2=search(x+1,en,y+1);
		max=max>max2?max:max2;
	}
	return max;
} 

int update(long n,long m,long w)
{
	long i,j,p,q,be=b[w].beg,en=b[w].end;
	if(be==en)
	{
		b[w].max=m;
		return 0;
	}
	if(n>(be+en)/2) 
	    update(n,m,2*w+1);
	else if(n<=(be+en)/2)
		update(n,m,2*w);
	p=b[2*w+1].max;
	q=b[2*w].max;
	b[w].max=p>q?p:q;
	return 0;
}

int act()
{
	long a,b,p;
	char c;
	while(1)
	{
		c=getchar();
		if(c=='Q'||c=='S')
		    break;
	}
	scanf("%d%d",&a,&b);
	if(c=='Q')
	{
		p=a>b?a:b;
		a=a<b?a:b;
		b=p;
	}
	switch(c)
	{
		case 'S':update(a-1,b,1);break;
		case 'Q':printf("%d\n",search(a-1,b-1,1));break;
	}
	return 0;
}

int create(long n,long be,long e)
{
	long p,q; 
	b[n].beg=be;
	b[n].end=e;
	if(e>be)
	{
		create(2*n,be,(be+e)/2); 
		create(2*n+1,(be+e)/2+1,e);
		p=b[2*n].max;
		q=b[2*n+1].max;
		b[n].max=p>q?p:q;
		return 0;
	}
	else if(be==e)
	{
		b[n].max=a[e]; 
		return 0;
	}
	else
	return 0; 
	
} 

int main()
{
	long n,m,i,j;
	char c; 
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		if(flag)
		cout<<endl;
		flag=1;
		memset(b,0,sizeof(b));
		memset(a,0,sizeof(a));
		for(i=0;i<n;i++)
			scanf("%d",a+i);
		create(1,0,n-1); 
		for(i=0;i<m;i++)
		act(); 
	} 
	return 0;
}