sicily 1800 线段树RMQ

//找给定序列的最小和子序列，子序列长度在[L,U] //s[i] // [1,i]和 //枚举 s[L]..s[n] 线段树找 s[i-U]..s[i-L] 最大值即可 //第一个线段树，又是百科教我的 #include <iostream> #include <cstdio> #define Mx 32770 #define INF (1<<30) #define _mx(a,b) ((a>b) ? (a):(b)) using namespace std; int n,L,U; int s[Mx]; struct Seq { int x,y; int mx; }seq[4*Mx]; void buildTree( int p,int x,int y ) { seq[p].x = x; seq[p].y = y; if( x == y ) seq[p].mx = s[x]; else { int mid = ( x + y ) / 2; buildTree( 2*p,x,mid); buildTree( 2*p+1,mid+1,y); seq[p].mx = _mx( seq[2*p].mx,seq[2*p+1].mx ); } } int findmx( int p,int x,int y ) { if( x > y ) return -INF; if( x == y ) return s[x]; if( seq[p].x == x && seq[p].y == y ) return seq[p].mx; int mid = ( seq[p].x + seq[p].y ) / 2; if( mid >= y ) return findmx( 2*p,x,y); if( mid < x ) return findmx( 2*p+1,x,y); return _mx( findmx( 2*p,x,mid),findmx( 2*p+1,mid+1,y) ); } int main() { while( scanf("%d",&n) && n != 0 ) { scanf("%d%d",&L,&U); s[0] = 0; for( int i = 1;i <= n;i++ ) { scanf("%d",s+i); s[i] += s[i-1]; } buildTree( 1,1,n ); int mn = INF; for( int i = L;i <= n;i++ ) { int temp = s[i] - findmx( 1,_mx( 0,i-U ),i-L ); if( mn > temp ) mn = temp; } cout<<mn<<endl; } return 0; }