hdu 1754 I hate it

これは1本の線分の木の特別な場の出た問題で、ずっと前にすでに線分の木ACを使って過ぎて、最近それをもとにして省試合の選抜試合に道の問題を出して、また考えてみて、暴力も過ぎるべきだと思って、少し最適化して、渡してやっと線分の木より速いことを発見しました...ORZ.

#include<stdio.h>
#include<stdlib.h>
#define MAX 200005
#define NT 1000
int p[MAX],b[MAX],n; int readInt(){ char c;int n=0;
    c=getchar(); while(c<'0'||c>'9')c=getchar(); while(c>='0'&&c<='9'){
        n*=10;
        n+=(c-'0');
        c=getchar(); } return n; } void outInt(int n){ char c[10]; int i=0,j; while(n>0){
        j=n%10;
        c[i++]=j+'0';
        n/=10; } while(--i>=0)putchar(c[i]); } int main(){ int i,j,m,cnt=0,x,y,t,q,k; char c; while(scanf("%d %d",&n,&m)!=EOF){ if(n<=NT){ for(i=1;i<=n;i++)   p[i]=readInt(); for(i=0;i<m;i++){
                c=getchar();   x=readInt();   y=readInt(); if(c=='Q'){ if(x>y){j=x,x=y,y=j;}
                    t=0; for(j=x;j<=y;j++) if(p[j]>t)t=p[j]; 
                    outInt(t);         putchar('
'); }else{
                    p[x]=y; } } }else{
            t=0;j=0; for(i=1;i<=n;i++){
                p[i]=readInt(); if((i%NT)==0){
                    b[j++]=t;  t=0; } if(p[i]>t)t=p[i]; }
            b[j]=t; for(i=0;i<m;i++){
                c=getchar(); x=readInt(); y=readInt(); if(c=='Q'){ if(x>y){j=x;x=y;y=j;}
                    q=x/NT;   k=y/NT; t=0; if(q<k){ for(j=q+1;j<=k-1;j++) if(b[j]>t)  t=b[j]; for(j=x;j<(q+1)*NT;j++) if(p[j]>t)  t=p[j]; for(j=k*1000;j<=y;j++) if(p[j]>t)  t=p[j]; }else{ for(j=x;j<=y;j++) if(p[j]>t)t=p[j]; }  
                    outInt(t);  putchar('
'); }else{ 
                    p[x]=y;
                    q=x/NT; if(y>b[q])b[q]=y; } } } } return 0; }