锰锌刚学OI一毫秒，板子TLE #8，9，10求助！！

rt

悬赏一关注

#include <iostream>
#include <cstdio>

using namespace std;

long long N;
long long T;
long long Value[100006];

struct Tree
{
    long long Ls,Rs,Sum,Lazy;
    Tree(){Ls = Rs = Sum = Lazy = 0;}
}A[500006];

void UpDate(long long K)
{
    A[K].Sum = A[(K<<1)].Sum + A[(K<<1)|1].Sum;
    return ;
}

void PushDown(long long K)
{
    if(A[K].Ls == A[K].Rs)
        A[K].Lazy = 0;
    else
    {
        long long l = (K<<1);
        long long r = l+1;
        A[l].Sum += (A[l].Rs-A[l].Ls+1)*A[K].Lazy;
        A[l].Lazy += A[K].Lazy;
        A[r].Sum += (A[r].Rs-A[r].Ls+1)*A[K].Lazy;
        A[r].Lazy += A[K].Lazy;
        A[K].Lazy = 0;
    }
    return ;
}

void Built(long long K,long long l,long long r)
{
    A[K].Ls = l;
    A[K].Rs = r;
    if(l == r)
    {
        A[K].Sum = Value[l];
        return ;
    }
    long long Mid = (l+r) >> 1;
    Built((K<<1),l,Mid);
    Built((K<<1)|1,Mid+1,r);
    UpDate(K);
    return ;
}   

void Change(long long K,long long x,long long V)
{
    if(A[K].Ls == A[K].Rs)
    {
        A[K].Sum = V;
        return ;
    }
    long long Mid = (A[K].Ls+A[K].Rs) >> 1 ;
    if(x <= Mid)
        Change((K<<1),x,V);
    else
        Change((K<<1)|1,x,V);
    UpDate(K);
}

void ChangeSegment(long long K,long long l,long long r,long long V)
{
    PushDown(K);
    if(A[K].Ls == l && A[K].Rs == r)
    {
        A[K].Sum += (r-l+1)*V;
        A[K].Lazy += V;
        return ;
    }
    long long Mid = (A[K].Ls+A[K].Rs) >> 1;
    if(l > Mid)
        ChangeSegment((K<<1)|1,l,r,V);
    else if(r <= Mid)
        ChangeSegment((K<<1),l,r,V);
    else
    {
        ChangeSegment((K<<1),l,Mid,V);
        ChangeSegment((K<<1)|1,Mid+1,r,V);
    }
    UpDate(K);
}

long long Query(long long K,long long l,long long r)
{
    PushDown(K);
    if(A[K].Ls == A[K].Rs)
        return A[K].Sum;
    long long Mid = (A[K].Ls+A[K].Rs) >> 1;
    if(r <= Mid)
        return Query((K<<1),l,r);
    else if(l > Mid)
        return Query((K<<1)|1,l,r);
    else
        return Query((K<<1),l,Mid) + Query((K<<1)|1,Mid+1,r);
}

long long Opt,L,R,Val;

int main()
{
    scanf("%lld%lld",&N,&T);
    for(long long i = 1 ; i<= N ; i++)
        scanf("%lld",&Value[i]);
    Built(1,1,N);
    for(long long i = 1 ; i<= T ; i++)
    {
        scanf("%lld",&Opt);
        if(Opt == 1)
        {
            scanf("%lld%lld%lld",&L,&R,&Val);
            ChangeSegment(1,L,R,Val);
        }
        else
        {
            scanf("%lld%lld",&L,&R);
            printf("%lld\n",Query(1,L,R));
        }
    }
    return 0;
}