为何MLE。。。。

P4513 小白逛公园

Zroom @ 2018-10-14 20:34:29

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
struct node{
    int data;
}tr[N*4];
int a[N],n,m;
int find_c(int l,int r)
{
    int sum1 = 0,sum2 = 0;
    int sum = 0;
    int mid = (l + r)>>1;
    for (int i = mid;i >= l;i--)
    {
        sum += a[i];
        if(sum > sum1) sum1 = sum;
    }
    sum = 0;
    for (int i = mid+1;i <= r;i++) {
        sum += a[i];
        if(sum > sum2) sum2 = sum;
    }
    return sum1 + sum2;
}
int build(int x,int l,int r)
{
    if(l == r){return tr[x].data = a[l];}
    int mid = (l + r)>>1;
    int ml = build(x<<1,l,mid);
    int mr = build((x<<1)|1,mid+1,r);
    int mc = find_c(l,r);
    return tr[x].data = max(max(ml,mr),mc);
}
void change(int x,int l,int r,int pos,int k)
{
    if(l == r){tr[x].data = k;return ;}
    int mid = (l + r)>>1;
    if(pos <= mid) change(x<<1,l,mid,pos,k);
    else change((x<<1)|1,mid+1,r,pos,k);
    tr[x].data = max(tr[x<<1].data,tr[(x<<1)|1].data);
}
int getsum(int x,int l,int r,int ll,int rr)
{
    if(l == ll && r == rr) {return tr[x].data;}
    int mid = (l + r)>>1;
    if(rr <= mid) return getsum(x<<1,l,mid,ll,rr);
    else 
    if(ll > mid) return getsum((x<<1)|1,mid+1,r,ll,rr);
    else return max(getsum((x<<1),l,mid,ll,mid),getsum((x<<1)|1,mid+1,r,mid+1,rr));
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i = 1;i <= n;i++)scanf("%d",&a[i]);
    build(1,1,n);
    for(int i = 1;i <= m;i++)
    {
        int op,x,y;
        scanf("%d",&op);
        if(op == 1)
        {
            scanf("%d%d",&x,&y);
            printf("%d\n",getsum(1,1,n,x,y));
        }
        if(op == 2)
        {
            scanf("%d%d",&x,&y);
            change(1,1,n,x,y);
        }
    }
    return 0;
}

|