分块70求助

TLE on #8 ~ #10

#include <iostream>
#include <cmath>
using namespace std;

int n, len;
int a[100001], lazy[100001], s[100001], id[100001];

void add(int l, int r, int x)
{
    int lid = id[l], rid = id[r];
    if (lid == rid)
    {
        for (int i = l; i <= r; i++)
        {
            a[i] += x;
            s[lid] += x;
        }
        return;
    }

    for (int i = l; id[i] == lid; i++)
    {
        a[i] += x;
        s[lid] += x;
    }
    for (int i = r; id[i] == rid; i--)
    {
        a[i] += x;
        s[rid] += x;
    }
    for (int i = lid + 1; i < rid; i++)
    {
        lazy[i] += x;
        s[i] += len * x;
    }
}

long long sum(int l, int r)
{
    int lid = id[l], rid = id[r];
    long long ans = 0;
    if (lid == rid)
    {
        for (int i = l; i <= r; i++)
        {
            ans += a[i] + lazy[lid];
        }
        return ans;
    }

    for (int i = l; id[i] == lid; i++)
    {
        ans += a[i] + lazy[lid];
    }
    for (int i = r; id[i] == rid; i--)
    {
        ans += a[i] + lazy[rid];
    }
    for (int i = lid + 1; i < rid; i++)
    {
        ans += s[i];
    }
    return ans;
}

int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int m;
    cin >> n >> m;
    len = sqrt(n);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        id[i] = n / len;
    }

    while (m--)
    {
        int op, x, y;
        cin >> op >> x >> y;
        if (op == 1)
        {
            int k;
            cin >> k;
            add(x, y, k);
        }
        else
        {
            cout << sum(x, y) << endl;
        }
    }
}