分块板子求调！悬赏1关注

rt

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>

#define maxn 100005
using namespace std;

long long N,Q;
long long Tmp,Num;
long long V[maxn];
long long L[maxn],R[maxn],Sum[maxn],Lazy[maxn],Pos[maxn];

long long pos,Left,Right,Value;
long long Answer;

int main()
{
    scanf("%lld%lld",&N,&Q);
    for(long long i = 1 ; i<= N ; i++)
        scanf("%lld",&V[i]);
    Tmp = sqrt(N);
    Num = (N-1)/Tmp+1;
    for(long long i = 1 ; i<= N ; i++)
    {
        Pos[i] = (i-1)/Tmp+1;
        Sum[Pos[i]] += V[i];
        if(Pos[i] != Pos[i-1]) L[Pos[i]] = i, R[Pos[i-1]] = i-1;
    }
    R[Num] = N;
    while(Q--)
    {
        scanf("%lld%lld%lld",&pos,&Left,&Right);
        if(pos == 1)
        {
            scanf("%lld",&Value);
            if(Pos[Left] == Pos[Right])
            {
                for(long long i = Left ; i <= Right ; i++)
                    V[i] += Value;
                Sum[Pos[Left]] += Value*(Right-Left+1);
            }
            else
            {
                for(long long i = Pos[Left]+1 ; i< Pos[Right] ; i++)
                    Lazy[i] += Value, Sum[i] += (R[i]-L[i]+1)*Value;
                for(long long i = Left ; i<= R[Pos[Left]] ; i++)
                    V[i] += Value;
                Sum[Pos[Left]] += Value*(R[Pos[Left]]-Left+1);
                for(long long i = L[Pos[Right]] ; i<= Right ; i++)
                    V[i] += Value;
                Sum[Pos[Right]] += Value*(Right-L[Pos[Right]]+1);
            }
        }
        else
        {
            Answer = 0;
            if(Pos[Left] == Pos[Right])
            {
                for(long long i = Left ; i<= Right ; i++)
                    Answer += V[i];
                Answer += Lazy[Pos[Left]]*(Right-Left+1);
            }
            else
            {
                for(long long i = Pos[Left]+1 ; i< Pos[Right] ; i++)
                    Answer += Sum[i] + Lazy[i]*(R[i]-L[i]+1);
                for(long long i = Left ; i<= R[Pos[Left]] ; i++)
                    Answer += V[i];
                Answer += Lazy[Pos[Left]]*(R[Pos[Left]]-Left+1);
                for(long long i = L[Pos[Right]] ; i<= Right ; i++)
                    Answer += V[i];
                Answer += Lazy[Pos[Right]]*(Right-L[Pos[Right]]+1); 
            }
            printf("%lld\n",Answer);
        }
    }
    return 0;
}