i hate it(线段树) .cpp

杭电acm解题报告2001---2099.

#include<cstdio>
#include<string>
#define Max 200100
int max_pos = 1<<19 -1;
int n,m,left,right;
int stu[4*Max];
int pos,deep,pt;
int a,b;

inline int MAX(int x,int y)
{
	if(x>y)	return x;
	return y;
}

int dfs(int x,int y,int pos)
{
	if(x==y)
	{
		return stu[pos];
	}
	if(a <= x && y <= b)
	{
		return stu[pos];
	}
	int mid = (x+y)>>1;
	int leftpos = pos<<1;
	if( mid+1 <= a )//a in right
	{
		return dfs(mid+1, y, leftpos+1);
	}
	else//a in left
	{
		if(mid+1 <= b)//b in right
		{
			return MAX( dfs(x, mid, leftpos), dfs(mid+1, y, leftpos+1));
		}
		else
		{
			return dfs(x, mid, leftpos);
		}
	}
}

int main()
{
	int i,j,t;
	char ch;
	
	while(scanf("%d %d",&n,&m)==2)
	{
		//memset(stu,0,sizeof(stu));
		pos =1;
		deep=0;
		while(pos<n)
		{
			deep++;
			pos = pos<<1;
		}
		pt =pos;
		for(i=0;i<n;i++)
		{
			scanf("%d",stu+pos+i);
		}
		for(;i<=pos;i++)
			stu[pos+i] = 0;
		while(pt>0)
		{
			t= pt;
			i = t;
			pt = pt>>1;
			for(j=pt;j<t;j++)
			{
				stu[j] = MAX( stu[i],stu[i+1] );
				i += 2;
			}
		}
		for(i=0;i<m;i++)
		{
			getchar();
			scanf("%c %d %d",&ch,&a,&b);
			if(ch=='Q')
			{
				if(a>b)
				{
					t=a;
					a=b;
					b=t;
				}
				if(b>n)	b=n;
				if(a>n) a=n;
				if(a<=0) a=1;
				if(b<=0) b=1;
				printf("%d\n",dfs(1,pos,1));
			}
			else
			{
				stu[pos+a-1] = b;
				t = pos+a-1;
				for(j=deep;j>0;j--)
				{
					stu[t>>1] = MAX( stu[t],stu[t+1] );
					t = t>>1;
				}
			}
		}
	}
}