sicily 1136 山海经

//听过大牛线段树讲座。。感觉新手赛要多用线段树 //这题线段树RMQ。。一开始真以为是普通RMQ，水了点代码交上去果断TLE //下来看discuss找到建树方法，但是想不出find方法。。放了3天后才重新拿起 //find一个区间的时候可以建一条它的线段，处理好左右孩子的有效量转移就可以了 /*线段记录: left,right 左右端点 xl mxl 从左端到xl有最大和mxl xr mxr 类似 a b mxall 从a到b有此段最大值 all 线段所有元素和 ll rr 想到find函数写法后才加上去的，左右孩子下标 find(p,x,y) 如果是左右完全分支则往下走 如果覆盖到mid就建新段，段的ll rr递归求得 段的left right 最终可以生成 端点x y的线段 return [x,y] 下标。 因为buildTree 和 find 写的时间隔了三天所以写得很丑。。 另外最后写出来之后TLE了n次，最后改用printf 0.26s 额，珍爱生命，远离cout */ #include <iostream> #include <cstdio> #define mx 100010 using namespace std; int s[mx],n,m,v,u,findfrom; struct Seg { int left,right,xl,xr,a,b,mxl,mxr,mxall,all,ll,rr; //作用看头注释 }seg[mx*4]; void buildTree( int p,int x,int y ) { seg[p].left = x; seg[p].right = y; seg[p].ll = 2*p; seg[p].rr = 2*p+1; if( x == y ) { seg[p].mxl = seg[p].mxr = seg[p].mxall = seg[p].all = s[x]; seg[p].a = seg[p].b = seg[p].xl = seg[p].xr = x; return ; } int mid = ( x+y ) / 2; buildTree(2*p,x,mid); buildTree(2*p+1,mid+1,y); seg[p].all = seg[2*p].all + seg[2*p+1].all; //记录段全部元素和 int mx1,_a,_b,mx2; if( seg[2*p].mxall >= seg[2*p+1].mxall ) //处理最大字段和mxall { mx1 = seg[2*p].mxall; _a = seg[2*p].a; _b = seg[2*p].b; } else { mx1 = seg[2*p+1].mxall; _a = seg[2*p+1].a; _b = seg[2*p+1].b; } mx2 = seg[2*p].mxr+seg[2*p+1].mxl; if( mx2 > mx1 || mx2 == mx1 && ( seg[2*p].xr < _a || seg[2*p].xr == _a && seg[2*p+1].xl < _b ) ) { mx1 = mx2; _a = seg[2*p].xr; _b = seg[2*p+1].xl; } seg[p].mxall = mx1; seg[p].a = _a; seg[p].b = _b; mx1 = seg[2*p].all + seg[2*p+1].mxl; //处理mxl 包含做端点最大字段和 if( mx1 > seg[2*p].mxl ) { seg[p].mxl = mx1; seg[p].xl = seg[2*p+1].xl; } else { seg[p].mxl = seg[2*p].mxl; seg[p].xl = seg[2*p].xl; } mx1 = seg[2*p].mxr + seg[2*p+1].all; //处理mxr 包含右端点最大字段和 if( mx1 >= seg[2*p+1].mxr ) { seg[p].mxr = mx1; seg[p].xr = seg[2*p].xr; } else { seg[p].mxr = seg[2*p+1].mxr; seg[p].xr = seg[2*p+1].xr; } } int find( int p,int x,int y ) { int result; if( seg[p].left == x && seg[p].right == y ) { result = p; } else { int mid = (seg[p].left+seg[p].right)/2; if( mid >= y ) { result = find( seg[p].ll,x,y ); } else if( mid < x ) { result = find( seg[p].rr,x,y ); } else { int p1 = find( seg[p].ll,x,mid ); int p2 = find( seg[p].rr,mid+1,y ); result = 3*mx + findfrom++; //建立适合 [x y] 的新段 seg[result].ll = p1; //以下操作与建树一样，可以用三个函数解决 seg[result].rr = p2; seg[result].left = seg[p1].left; seg[result].right = seg[p2].right; seg[result].all = seg[p1].all + seg[p2].all; int mx1,mx2,_a,_b; if( seg[p1].mxall >= seg[p2].mxall ) { mx1 = seg[p1].mxall; _a = seg[p1].a; _b = seg[p1].b; } else { mx1 = seg[p2].mxall; _a = seg[p2].a; _b = seg[p2].b; } mx2 = seg[p1].mxr + seg[p2].mxl; if( mx2 > mx1 || mx2 == mx1 && ( seg[p1].xr < _a || seg[p1].xr == _a && seg[p2].xl < _b ) ) { mx1 = mx2; _a = seg[p1].xr; _b = seg[p2].xl; } seg[result].mxall = mx1; seg[result].a = _a; seg[result].b = _b; mx1 = seg[p1].all + seg[p2].mxl; if( mx1 > seg[p1].mxl ) { seg[result].mxl = mx1; seg[result].xl = seg[p2].xl; } else { seg[result].mxl = seg[p1].mxl; seg[result].xl = seg[p1].xl; } mx1 = seg[p1].mxr + seg[p2].all; if( mx1 >= seg[p2].mxr ) { seg[result].mxr = mx1; seg[result].xr = seg[p1].xr; } else { seg[result].mxr = seg[p2].mxr; seg[result].xr = seg[p2].xr; } } } return result; } int main() { //freopen( "1.txt","r",stdin ); scanf("%d%d",&n,&m); for(int i = 1;i <= n;i++) scanf("%d",s+i); buildTree(1,1,n); while( m-- ) { scanf("%d%d",&v,&u); findfrom = 1; //新段从 3*mx+findfrom 开始存 int p = find( 1,v,u ); printf("%d %d %d/n",seg[p].a,seg[p].b,seg[p].mxall); } return 0; }