i hate it(模板改进版).cpp

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

//套模板，去掉了很多对此题没用的函数和变量
//直接模板会TLE因为节点是动态内存分配的，速度比较慢
//解决方法开个静态的大数组，模拟内存分配
#include<cstdio>
#include<algorithm>
using namespace std;

typedef struct ITREE_NODE {
	ITREE_NODE * pLChild, * pRChild;
	int left, right;		// 左端点，右端点
	int mmax; 		// 最大值
}*PITREE_NODE;

ITREE_NODE mem[410000];
int alloc;

inline int MAX(int v, int va) {
    if(v>va)	return v;
	return		va;
}
//模拟内存分配
inline PITREE_NODE new_node() {
	memset(mem+alloc+1, 0, sizeof(ITREE_NODE));
	return mem + (alloc++);
}

void itree_splite(PITREE_NODE pParent, const int iLeft, const int iRight) {
    if (iRight - iLeft <= 0) return;
    int iMid = (iLeft + iRight) >> 1;
    pParent -> pLChild = new_node();
    pParent -> pRChild = new_node();
    pParent -> pLChild -> left = iLeft;
    pParent -> pLChild -> right = iMid;
    pParent -> pRChild -> left = iMid+1;
    pParent -> pRChild -> right = iRight;
    itree_splite(pParent -> pLChild, iLeft, iMid);
    itree_splite(pParent -> pRChild, iMid+1, iRight);
}

PITREE_NODE itree_generate(const int iListCount) {
    PITREE_NODE pRoot = new_node();
    memset(pRoot, 0, sizeof(ITREE_NODE));
    pRoot -> left = 1;
    pRoot -> right = iListCount;
    itree_splite(pRoot, 1, iListCount);
    return pRoot;
}

int itree_update(PITREE_NODE pParent, const int left, const int right, const int value) {
    if (pParent -> left == left && pParent -> right == right) {
        pParent -> mmax = MAX(pParent -> mmax, value);
    } else {
        if (pParent -> pLChild -> right >= left) {
            if (pParent -> pLChild -> right >= right) {
                pParent -> mmax = 
					MAX(pParent -> mmax, itree_update(pParent -> pLChild, left, right, value));
            } else {
                pParent -> mmax = 
					MAX(pParent -> mmax, itree_update(pParent -> pLChild, left, pParent -> pLChild -> right, value));
                pParent -> mmax = 
					MAX(pParent -> mmax, itree_update(pParent -> pRChild, pParent -> pRChild -> left, right, value));
            }
        } else {
            pParent -> mmax = 
				MAX(pParent -> mmax, itree_update(pParent -> pRChild, left, right, value));
        }
    }
	return pParent -> mmax; 
}

int Get_Max(PITREE_NODE pParent, int left, int right)
{
	if (pParent -> left == left && pParent -> right == right) {
        return pParent -> mmax ;
    } else {
        if (pParent -> pLChild -> right >= left) {
            if (pParent -> pLChild -> right >= right) {
                return Get_Max(pParent -> pLChild, left, right);
            } else {
                return MAX(Get_Max(pParent -> pLChild, left, pParent -> pLChild -> right),
							Get_Max(pParent -> pRChild, pParent -> pRChild -> left, right));
            }
        } else {
            return Get_Max(pParent -> pRChild, left, right);
        }
    }
}

PITREE_NODE pRoot;

int main()
{
	int i,j,t;
	char ch;
	int n,m,a,b;

	while(scanf("%d %d",&n,&m)==2)
	{
		alloc = 0;
		pRoot = itree_generate(n);
		for(i=1;i<=n;i++)
		{
			scanf("%d",&t);
			itree_update(pRoot, i, i, t);
		}
		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",Get_Max(pRoot, a, b) );
			}
			else
			{
				itree_update(pRoot, a, a, b);
			}
		}
	}
}