分块，样例没过求条

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N = 1e6 + 5, B = 1e4;
const ll INF = 1e18;
int n, m, len, cnt;
int id[N];
ll a[N],maxn[B],t1[B],t2[B];
void add (int l, int r, ll k)
{
    for (int i = l; i <= r; i ++)
    {
        if (i % len == 1)
        {
            maxn[id[i]] += k;
            t1[id[i]] += k;
            i += len - 1;
        }
        else
        {
            a[i] += k;
            maxn[id[i]] = max (maxn[id[i]], a[i]);
        }
    }
}
void update (int l, int r, ll x)
{
    for (int i = l; i <= n; i ++)
    {
        if (i % len == 1)
        {
            maxn[id[i]] = x;
            t2[id[i]] = x;
            t1[id[i]] = 0;
            i += len - 1;
        }
        else
        {
            a[i] = x;
            maxn[id[i]] = max (maxn[id[i]], a[i]);
        }
    }
}
ll query (int l, int r)
{
    ll ans=-INF;
    for (int i = l; i <= r; i ++)
    {
        if (i % len == 1)
        {
            ans = max (ans, maxn[id[i]]);
            i += len - 1;
        }
        else
        {
            ll temp = t2[id[i]];
            if (temp == -INF)
            {
                temp = a[i];
            }
            ans = max (ans, temp + t1[id[i]]);
        }
    }
    return ans;
}
int main ()
{
    scanf ("%d %d", &n, &m);
    len = sqrt (n);
    for (int i = 1; i <= n; i ++)
    {
        scanf ("%d", &a[i]);
        if (i % len == 1)
        {
            cnt ++;
        }
        id[i] = cnt;
        maxn[cnt] = max (maxn[cnt], a[i]);
        t2[cnt] = -INF;
    }
    while (m --)
    {
        int op, l, r;
        scanf ("%d %d %d", &op, &l, &r);
        if (op == 1)
        {
            ll x;
            scanf ("%lld", &x);
            add (l, r, x);
        }
        else if (op == 2)
        {
            ll x;
            scanf ("%lld", &x);
            update (l, r, x);
        }
        else
        {
            printf ("%lld \n", query (l, r));
        }
    }
    return 0;
}