hdu 1754 I hate it
18614 ワード
これは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; }