C++(clang++11) 解法, 执行用时: 1730ms, 内存消耗: 97668K, 提交时间: 2021-01-10 20:47:24

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

#define N 200000
#define M 500

#define fo(i, x, y) for(ll i = x, end_##i = y; i <= end_##i; ++ i)
#define fd(i, x, y) for(ll i = x, end_##i = y; i >= end_##i; -- i)
#define Max(x, y) (x > y ? x : y)

#define ll long long

void read(ll &x) {
    char ch = getchar(); x = 0; ll f = 1;
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + ch - 48, ch = getchar();
    x *= f;
}

ll Fast(ll x, ll p, ll Mod) {
    ll res = 1;
    while (p) {
        if (p & 1)
            res = 1ll * res * x % Mod;
        x = 1ll * x * x % Mod;
        p >>= 1;
    }
    return res;
}

ll lk[N + 1][2], li[N + 1], a[N + 1];

ll n, Q, sqrt_n, suf, tot;

struct HASH {
    ll mod, p, inv_p;
    ll has[N + 1], inv[N + 1], mi[N + 1], ak[N + 1], ck[N + 1], add[M + 1], bk[M + 1];
    void Init(ll Mod, ll P) {
        mod = Mod, p = P, inv_p = Fast(p, Mod - 2, Mod);
        mi[0] = inv[0] = 1, has[0] = ak[0] = 0;
        fo(i, 1, n) mi[i] = 1ll * mi[i - 1] * p % mod;
        fo(i, 1, n) inv[i] = 1ll * inv[i - 1] * inv_p % mod;
        fo(i, 1, n) has[i] = (has[i - 1] + 1ll * mi[i - 1] * a[i] % mod) % mod;
        fo(i, 1, n) ak[i] = (ak[i - 1] + mi[i - 1]) % mod;
        fo(i, 1, n) ck[i] = (ak[i] - ak[lk[li[i]][0] - 1] + mod) % mod;
        fo(i, 0, tot) bk[i] = add[i] = 0;
    }
    #define Has(u) (((has[u] + 1ll * ck[u] * ((bk[li[u]] + mod) % mod) % mod) % mod + add[li[u]]) % mod)
    ll Hash(ll x, ll y) {
        return 1ll * (Has(y) - Has(x - 1) + mod) % mod * inv[x - 1] % mod;
    }
    ll Hash(ll x) {
        return 1ll * (Has(x) - Has(x - 1) + mod) % mod * inv[x - 1] % mod;
    }
    void Rebuild(ll k, ll u, ll v, ll w) {
        fo(i, lk[k][0], lk[k][1]) has[i] = Has(i);
        fo(i, lk[k][0], lk[k][1])
        a[i] += bk[k];
        fo(i, u, v) a[i] += w;
        has[lk[k][0]] = (Has(lk[k][0] - 1) + 1ll * mi[lk[k][0] - 1] * a[lk[k][0]] % mod) % mod;
        fo(i, lk[k][0] + 1, lk[k][1])
        has[i] = (has[i - 1] + 1ll * mi[i - 1] * a[i] % mod) % mod;
        add[k] = bk[k] = 0;
    }
    void Add(ll l, ll r, ll w) {
        if (li[l] == li[r]) {
            Rebuild(li[l], l, r, w);
            fo(i, li[r] + 1, tot)
            add[i] = (add[i] + 1ll * (((ak[r] - ak[l - 1] + mod) % mod) * ((w + mod) % mod) % mod)) % mod;
            return;
        }
        Rebuild(li[l], l, lk[li[l]][1], w);
        fo(i, li[l] + 1, li[r] - 1) {
            bk[i] += w;
            add[i] = (add[i] + 1ll * (((ak[lk[i][0] - 1] - ak[l - 1] + mod) % mod) * ((w + mod) % mod) % mod)) % mod;
        }
        Rebuild(li[r], lk[li[r]][0], r, w);
        fo(i, li[r] + 1, tot)
        add[i] = (add[i] + 1ll * (((ak[r] - ak[l - 1] + mod) % mod) * ((w + mod) % mod) % mod)) % mod;
    }
} h1;

bool Pd(ll x, ll y, ll u, ll v) {
    return h1.Hash(x, y) == h1.Hash(u, v);
}

ll LCP(ll u, ll v, ll w) {
    ll l = 1, r = w - Max(u, v) + 1, mid = 0;
    while (l <= r) {
        mid = l + r >> 1;
        Pd(u, u + mid - 1, v, v + mid - 1) ? 
            l = mid + 1
        :
            r = mid - 1;
    }
    return l - 1;
}

int Cmp(ll u, ll v, ll w) {
    ll k = LCP(u, v, w);
    if (k + Max(u, v) > w) return 0;
    return h1.Hash(u + k) - h1.Hash(v + k);
}

struct Tree {
    struct Suf {
        ll x[20], cnt;
    } s[N << 2];
    ll lazy[N << 2];
    void Pushup(ll t, ll r) {
        int lson = t << 1, rson = t << 1 | 1;
        s[t].cnt = s[rson].cnt;
        fo(i, 1, s[t].cnt) s[t].x[i] = s[rson].x[i];
        fo(i, 1, s[lson].cnt) {
            while (1) {
                int x = s[lson].x[i], y = s[t].x[s[t].cnt];
                int c = Cmp(x, y, r);
                if (c > 0) break;
                if (! c) {
                    if ((r - y + 1 << 1) > r - x + 1) -- s[t].cnt;
                    s[t].x[++ s[t].cnt] = x;
                    break;
                }
                if (! -- s[t].cnt) {
                    s[t].x[++s[t].cnt] = x;
                    break;
                }
            }
        }
    }
    #define lson (t << 1)
    #define rson (t << 1 | 1)
    void Init(ll t, ll l, ll r) {
        if (l == r) {
            s[t] = (Suf) { { 0, l }, 1 };
            return;
        }
        int mid = l + r >> 1;
        Init(lson, l, mid), Init(rson, mid + 1, r);
        Pushup(t, r);
    }
    void Chang(ll t, ll l, ll r, ll x, ll y) {
        if (x <= l && r <= y) return;
        int mid = l + r >> 1;
        if (x <= mid) Chang(lson, l, mid, x, y);
        if (y > mid) Chang(rson, mid + 1, r, x, y);
        Pushup(t, r);
    }
    void Find(ll t, ll l, ll r, ll x, ll y, ll R) {
        if (x <= l && r <= y) {
            fo(j, 1, s[t].cnt) {
                if (Cmp(s[t].x[j], suf, R) < 0)
                    suf = s[t].x[j];
            }
            return;
        }
        int mid = l + r >> 1;
        if (y > mid) Find(rson, mid + 1, r, x, y, R);
        if (x <= mid) Find(lson, l, mid, x, y, R);
    }
    #undef lson
    #undef rson
} tr;

void Ycl() {
    sqrt_n = sqrt(n + 1);
    lk[1][0] = li[1] = tot = 1;
    fo(i, 2, n) {
        li[i] = tot;
        if (i - lk[tot][0] + 1 >= sqrt_n)
            lk[tot][1] = i, lk[ ++ tot ][0] = i + 1;
    }
    lk[tot][0] <= n ? lk[tot][1] = n : -- tot;
    h1.Init(19260817, 29);
    tr.Init(1, 1, n);
}

const ll inf = 2e4;

int main() {
    read(n), read(Q);
    fo(i, 1, n) read(a[i]);

    fo(i, 1, n) a[i] += inf;

    Ycl();

    ll opt, x, y, d;

    fo(qu, 1, Q) {
        read(opt), read(x), read(y);
        if (opt == 1) {
            read(d);
            h1.Add(x, y, d);
            tr.Chang(1, 1, n, x, y);
        } else {
            suf = y;
            tr.Find(1, 1, n, x, y, y);
            printf("%lld\n", suf);
        }
    }

    return 0;
}