1 #include 
        
            2 #include 
         
             3 using namespace std;   4 const int cmax = 100005;   5 const int minnum = -999999999;   6 int ans , s , x , posx , posy ;   7 struct Tnode   8 {
        9      10     int maxs , sum , maxl , maxr ; // maxs为当前区间最大的序列和 ， sum为当前区间的和 ， maxl为当前区间左端点开始的最大序列和 ， maxr  11 //为当前空间右端点结束的最大序列和  12     int posi , posj , posl , posr ; //posi为maxs的左端点 ， posj为maxs的右端点 ， posl为 maxl的右端点 ， posr为maxr的左端点  13     int right , left ;//区间左端点 ， 区间右端点  14 }tree[cmax * 4];  15 int temp , count = 0;  16 //从线段树的子节点往根节点更新信息  17 void PushUP(int p) {
       18     tree[p].sum = tree[ 2 * p ].sum + tree[ 2* p + 1].sum;  19     tree[p].maxl = tree[ 2 * p ].maxl ;  20     tree[p].maxr = tree[ 2* p + 1] .maxr ;  21     tree[p].posl = tree[ 2* p].posl;  22     tree[p].posr = tree[ 2 * p + 1].posr;  23     int temp_sum;  24     temp_sum = tree[ 2* p ].sum + tree[ 2 * p + 1].maxl;  25     if ( temp_sum > tree[p].maxl )  26     {
       27         tree[p].maxl = temp_sum;  28         tree[p].posl = tree[ 2 * p + 1 ] .posl;  29     }  30     temp_sum = tree[ 2 * p + 1].sum + tree[ 2 * p ].maxr ;  31     if ( temp_sum >= tree[p].maxr )  32     {
       33         tree[p].maxr = temp_sum;  34         tree[p].posr = tree[ 2 * p ].posr;  35     }  36     tree[p].maxs = tree[ 2 * p ].maxs;  37     tree[p].posi = tree[ 2 * p].posi;  38     tree[p].posj = tree[ 2 * p].posj;  39     temp_sum = tree[ 2 * p].maxr + tree[ 2 * p +1 ].maxl;  40      41      if(temp_sum > tree[p].maxs || ( temp_sum == tree[p].maxs && tree[p*2].posr < tree[p].posi ) )  42          {
       43           tree[p].maxs= temp_sum ;  44           tree[p].posi=tree[p*2].posr ;  45           tree[p].posj=tree[p*2+1].posl ;  46          }  47     if ( tree[p].maxs < tree[ 2 * p + 1].maxs )  48     {
       49         tree[p].maxs = tree[ 2 * p + 1].maxs;  50         tree[p].posi = tree[ 2 * p + 1].posi;  51         tree[p].posj = tree[ 2 * p + 1].posj;  52     }  53 }  54 //建立线段树 ， 初始化  55 void build( int p , int L , int R)  56 {
       57     if ( L == R )  58     {
       59         scanf("%d" , &temp);  60         tree[p].maxl = tree[p].maxr = tree[p].maxs = tree[p].sum = temp;  61         count++;  62         tree[p].posi = tree[p].posj = tree[p].posl = tree[p].posr = count;  63         tree[p].right = tree[p].left = L;  64         return ;  65     }  66     int mid = ( L + R ) /2 ;  67         build( p*2 , L , mid );  68         build( 2* p +1 , mid + 1 , R);  69         tree[p].right = R;  70         tree[p].left = L;  71     PushUP(p);//从叶子往父节点更新值 ， 递归地从底层往上更新值  72      73 }  74 //线段树的查询操作  75 void query( int p , int L , int R)  76 {
       77     if ( tree[p].left == L && tree[p].right == R)  78     {
       79         if ( s + tree[p].maxl > ans )  80         {
       81             ans = s + tree[p].maxl;  82             posx = x;  83             posy = tree[p].posl;  84         }  85      86         if ( tree[p].maxs > ans )  87         {
       88             ans = tree[p].maxs;  89             posx= tree[p].posi;  90             posy = tree[p].posj;  91  92         }  93         int temp;  94         temp = s + tree[p].sum;  95         if ( temp > tree[p].maxr)  96         {
       97             s = temp;  98         }  99         else 100         {
      101             s = tree[p].maxr; 102             x = tree[p].posr; 103         } 104         return ; 105     } 106 107         int mid = ( tree[p].left + tree[p].right) / 2 ; 108         if ( R <= mid ) 109         {
      110             query( 2 * p , L  , R); 111         } 112         else if ( L > mid ) 113         {
      114             query( 2 * p + 1 , L , R ); 115         } 116         else 117         {
      118             query( 2 * p , L , mid ); 119             query( 2 * p + 1 , mid + 1 , R ); 120         } 121 } 122 int main() 123 {
      124     int n , m , value ; 125     int a , b; 126     scanf( "%d%d" , &n , &m); 127     build( 1 ,1  , n ); 128 //    cout << tree[6].maxs << tree[7].maxs << tree[8].maxs << tree[9].maxs; 129 //    cout << tree[1].maxs << tree[2].maxs << tree[7].maxs; 130     while ( m --) 131     {
      132         scanf("%d%d" , &a , &b ); 133         s = 0 ; 134         x = a; 135         ans = minnum; 136         query( 1 , a , b ); 137         printf("%d %d %d\n",posx,posy,ans); 138     } 139     return 0 ; 140 }