嗯嗯，听朋友说要用线段树，能讲解下否？

ACM就肯定谈不上了……

我来仔细分析一下这道题吧，表示今天提交一次AC了，相当高兴

首先，我们可以看出题目给出一段长为n的序列，然后有m次询问，每次询问给定序列[L,R]中的最大子和序列

最直观的想法：
对于每次询问，在[L,R]区间内枚举起点和终点，这样每次询问花费的时间为O(N^2*M)，即LZ所用的方法，在此基础上虽然进行了一定的优化，但毫无疑问，远远不够

动态规划：
我们想想有没有更好的方法来解决如何寻找给定序列的最大子和问题，真如laoyang 3L说的，用动态规划，我们用f[i]表示第i个数结尾的序列能组成的最大子序列和，考虑f[i]的正负，如果f[i]>=0,那么f[i]=f[i-1]+a[i].为什么等于0时也要转移呢？因为题目说了要求有相同解需要左边界尽量小，如果f[i-1]<0,那么f[i]=a[i];
得到这个动态转移方程之后我们就可以在O(n)时间内找到最大子和序列，m次询问花费的时间为O(n*m)，由于本题数据量实在过大，依然超时TLE（昨天做的），以下是这种方法对应的代码

#include <stdio.h>
#include <stdlib.h>

int a[100001],n,m,L,R,i,j,ans,now,pi,pj;

int main()
{
    scanf("%d%d",&n,&m);
    for (i=1; i<=n; i++) scanf("%d",a+i);
    while (m--)
    {
        scanf("%d%d",&L,&R);
        ans=-10001;  now=0;
        i=L;
        for (j=L; j<=R; j++)
        {
            if (now>=0) now+=a[j]; 
            else 
            {
                now=a[j]; i=j;
            }
            if (now>ans)
            {
                pi=i; pj=j; ans=now;
            }
        }
        printf("%d %d %d\n",pi,pj,ans);
    }
    return 0;
}

                

进一步优化：
RMQ算法：线段树的一种特殊形式，对一个序列经过O(nlog2(n))时间的预处理后能在O(1)时间内找出任意区间[L,R]内的最大最小值

对f函数和s函数（表示前i项的和）进行RMQ预处理

然后循环下列过程：
1、对区间[L,R]进行f_RMQ查找，假设找到的为p
2、如果p所代表的子序列未超界或者p=r，更新答案后推出循环
3、对[L-1,P-1]使用s_RMQ，这样就能找到p在这个区间内所对应的最大子和序列
4、可以证明以[L,P-1]结尾的序列不会是答案，所以忽略，然后对[p+1,R]区间进行f_RMQ查找，这样回到第一步

下面是ac的代码

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int n,m,L,R,ans,a[100001],s[100001],f[100001],pre[100001],RMQ_s[100001][17],RMQ_f[100001][17],two[17];

void dp()
{
    int i,j;
    s[1]=a[1]; pre[1]=1; f[1]=a[1];
    for (i=1; i<=n; i++)
    {
        s[i]=s[i-1]+a[i];
        if (f[i-1]>=0) 
        {
            f[i]=f[i-1]+a[i]; pre[i]=pre[i-1];
        }
        else
        {
            f[i]=a[i]; pre[i]=i;
        }
    }
}

void Prepare_RMQ_S()
{
    int i,j=log(n)/log(2),k;
    for (i=1; i<=n; i++) RMQ_s[i][0]=i;
    for (k=1; k<=j; k++)
      for (i=1; i<n; i++)
      {
          if (i+two[k]-1>n) break;
          if (s[RMQ_s[i][k-1]]<s[RMQ_s[i+two[k-1]][k-1]]) RMQ_s[i][k]=RMQ_s[i][k-1]; else RMQ_s[i][k]=RMQ_s[i+two[k-1]][k-1];
      }
}

void Prepare_RMQ_F()
{
    int i,j=log(n)/log(2),k;
    for (i=1; i<=n; i++) RMQ_f[i][0]=i;
    for (k=1; k<=j; k++)
      for (i=1; i<n; i++)
      {
          if (i+two[k]-1>n) break;
          if (f[RMQ_f[i][k-1]]>f[RMQ_f[i+two[k-1]][k-1]]) RMQ_f[i][k]=RMQ_f[i][k-1]; else RMQ_f[i][k]=RMQ_f[i+two[k-1]][k-1];
      }
}

int Get_RMQ_C(int p,int q)
{
    int l=log(q-p+1)/log(2);
    if (s[RMQ_s[p][l]]<=s[RMQ_s[q-two[l]+1][l]]) return RMQ_s[p][l]; else return RMQ_s[q-two[l]+1][l];
}

int Get_RMQ_F(int p,int q)
{
    int l=log(q-p+1)/log(2);
    if (f[RMQ_f[p][l]]>=f[RMQ_f[q-two[l]+1][l]]) return RMQ_f[p][l]; else return RMQ_f[q-two[l]+1][l];
}

void FindMaxL()
{
    int p,q,t,ans,GL,GR;
    p=Get_RMQ_F(L,R);
    if (pre[p]>=L) printf("%d %d %d\n",pre[p],p,f[p]);
    else
    {
        q=Get_RMQ_C(L-1,p-1);
        ans=s[p]-s[q]; GL=q+1,GR=p;
        while (p<R)
        {
            p=Get_RMQ_F(p+1,R);
            if (pre[p]>=L)
            {
                if (ans<f[p])
                {
                    ans=f[p]; GL=pre[p]; GR=p;
                }
                break;
            }
            q=Get_RMQ_C(L-1,p-1);
            if (ans<s[p]-s[q])
            {
                ans=s[p]-s[q]; GL=q+1; GR=p;
            }
        }
        printf("%d %d %d\n",GL,GR,ans);
    }
}    

int main()
{
    int i;
    scanf("%d%d",&n,&m);
    for (i=1; i<=n; i++) scanf("%d",&a[i]);
    two[0]=1;
    for (i=1; i<=16; i++) two[i]=two[i-1]*2;
    dp();
    Prepare_RMQ_S();
    Prepare_RMQ_F();
    while (m--)
    {
        scanf("%d%d",&L,&R);
        FindMaxL();
    }
    return 0;
}

估计LZ可能理解起来有点难，因为这道题难度确实有点大，LZ最好首先先理解好第二种方法

非常非常感谢，我尽力理解下……（顺便问一句，你也是中大的吗？）

不是,这个OJ我是baidu到的，我在上海读大学

交大？

这都能猜到？

夜猫子。。