求助卡常（序列分块+操作分块）

#include <bits/stdc++.h>
// #include <iostream>
// #include <vector>
// #include <algorithm>
// #include <cmath>
#define all(v) v.begin(),v.end()
#define fro(i,a,b) for (int i = a; i <= b; i++)
using PII = std::pair<int,int>; using std :: cerr ;
inline void chkmin (int &x , int y) { x <= y ? x : x = y; }
inline void chkmax (int &x , int y) { x >= y ? x : x = y; }
constexpr int inf = (sizeof (int) == 4 ? 0x3f3f3f3f : 0x3f3f3f3f3f3f3f3f);
namespace FastRead
{
    char buf[1 << 23] , *p1 = buf ,*p2 = buf , obuf[1 << 23] , *O = obuf;
    #define Fastest_GetChar (p1 == p2 && (p2 = (p1 = buf) + \
        fread (buf , 1 , 1 << 21 , stdin) , p1 == p2) ? EOF : *p1++)
    inline int read () 
    {
        int x = 0 , f = 1; char ch = Fastest_GetChar;
        while (!isdigit (ch)) {if (ch == '-') f = -1; ch = Fastest_GetChar;}
        while (isdigit (ch)) x = x * 10 + (ch ^ 48) , ch = Fastest_GetChar;
        return x * f;
    }
}
using FastRead :: read ;
using i64 = long long;
constexpr int N = 3e5 + 5 , sqN = 2005 , Qb = 2005;

int coun = 0 ;

template <class T>
struct Vector
{
    int tot ;
    int head[N];
    struct edge
    {
        T to;
        int nxt;
    } a[N];
    inline void addedge (int u , T val)
    {
        a[++tot] = {val , head[u]};
        head[u] = tot;
    }
} ;

int n , m ;
PII ar[N];
Vector <int> t;

int c[N];
int idx;
struct dsu {int L , R;} a[N << 2];
int top;
struct node { int id , pos , id1 , id2 , L , R , w; } st[N << 2];

inline i64 wight (int x) { if (x < 0) return 0; return i64<%x%> * (x + 1) >> 1; }
inline i64 wight (const dsu x) { return wight (x.R - x.L + 1); }

int pre[N] ;

int tot , B;
int L[sqN] , R[sqN];
i64 val[sqN];

struct Node 
{
    int id , pos , va;
} b[N];

i64 ans[Qb];
struct Q { int opt , l , r , x , id; } q[Qb] , q1[Qb] , q2[Qb];
Vector < Q > e;

inline void merge (int x , int y , int id , int pos1 , int w)
{
    val[id] -= wight (a[x]) + wight (a[y]);
    st[++top] = {id , pos1 , x , y , a[y].L , a[y].R , w};
    b[a[x].R].id = b[a[x].L].id = y;
    chkmax (a[y].R , a[x].R) , chkmin (a[y].L , a[x].L);
    val[id] += wight (a[y]);
}
inline void remove ()
{
    auto& [id , pos , x , y , L , R , w] = st[top--];
    if (x == -2)
    {
        val[id] -= w * (b[pos].va == 0);
        if (b[pos].va == 0) b[pos].id = 0;
        return ;
    }
    b[pos].va -= w;
    if (b[pos].va || x == -1) return ;
    b[a[x].R].id = b[a[x].L].id = x;
    val[id] -= wight (a[y]) , a[y] = {L , R};
    val[id] += wight (a[x]) + wight (a[y]);
}

inline bool in (dsu x , dsu y) { return y.L <= x.L && x.R <= y.R; }
inline void change (int x)
{
    Node& now = b[x];
    if (now.va) return void ((now.va++ , st[++top] = {now.pos , x , -1 , -1 , -1 , -1 , 1})); 
    now.va++;
    if (!now.id) a[now.id = ++idx] = {x , x} , val[now.pos]++;
    int w = 1;
    st[++top] = {now.pos , x , -2 , -1 , -1 , -1 , 1};
    bool chk1 = (x + 1 <= R[now.pos] && b[x + 1].va && now.id != b[x + 1].id
        && !in (a[now.id] , a[b[x + 1].id]));
    bool chk2 = (x - 1 >= L[now.pos] && b[x - 1].va
        && now.id != b[x - 1].id && !in (a[now.id] , a[b[x - 1].id]));
    if (chk1 && chk2)
    {
        merge (now.id , b[x + 1].id , now.pos , x , 0);
        merge (now.id , b[x - 1].id , now.pos , x , 1) , w--;
    }
    else if (chk1)
        merge (now.id , b[x + 1].id , now.pos , x , w) , w--;
    else if (chk2)
        merge (now.id , b[x - 1].id , now.pos , x , w) , w--;
    if (w == 1)
        st[++top] = {now.pos , x , -1 , -1 , -1 , -1 , 1};
}
inline i64 query (int l , int r , i64 res = 0)
{
    int now = 0 ;
    if (b[l].pos == b[r].pos)
    {
        for (int i = l; i <= r ; i++)
        {
            if (b[i].va) now ++;
            else res += wight (now) , now = 0;
        }
        res += wight (now) , now = 0 ;
        return res;
    }

    now = 0 ;
    for (int i = l; i <= R[b[l].pos] ; i++)
    {
        if (b[i].va) now ++;
        else res += wight (now) , now = 0;
    }
    if (!b[R[b[l].pos] + 1].va) res += wight (now);

    now = 0;
    bool op = 0 ;
    for (int i = L[b[r].pos]; i <= r; i++)
    {
        if (b[i].va) now ++;
        else
        {
            if (op || !b[L[b[r].pos] - 1].va) res += wight (now);
            op = 1 , now = 0;
        }
    }
    if (op || !b[L[b[r].pos] - 1].va) res += wight (now) , now = 0;

    int ql = n + 1 , qr = 0 ;
    for (int i = b[l].pos + 1; i <= b[r].pos; i++)
    {
        if (i < b[r].pos) res += val[i];
        if (b[R[i - 1]].va && b[L[i]].va)
        {
            int& y = b[L[i]].id ; int& x = b[R[i - 1]].id;

            res -= wight (a[y]) * (i < b[r].pos) +
                wight (a[x]) * (i - 1 > b[l].pos && (a[x].L != L[i - 1] || ql > qr));
            chkmin (ql , std :: max (a[x].L , l));
            if (a[y].L == L[i])
                qr = std :: min (r , a[y].R);
        }
        if (ql <= qr && qr != R[i])
        {
            res += wight ({ql , qr});
            ql = n + 1 , qr = 0;
        }
    }
    if (ql <= qr) res += wight ({ql , qr});
    return res;
}

bool vis[N] , de[N];
int Rid[N];

inline void FakeQuery (int m)
{
    int m1 = 0 , m2 = 0;
    for (int i = 1; i <= m; i++)
    {
        if (q[i].opt == 1) q1[++m1] = q[i];
        else q2[++m2] = q[i] , Rid[q2[m2].id] = m2;
    }

    for (int i = 1; i <= n; i++) c[i] = ar[i].first , pre[ar[i].second] = i;

    // for (int i = 1; i <= m2; i++)
    for (int i = m2; i ; --i)
        e.addedge (q2[i].x , q2[i]);
    m2 = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = e.head[i]; j ; j = e.a[j].nxt)
            q2[++m2] = e.a[j].to;
        e.tot = e.head[i] = 0;
    }

    for (int i = 1; i <= m1; i++)
        vis[q1[i].l] = 1;

    int now = 1 , lst = 0 ;
    for (int i = 1; i <= m2; i++)
    {
        while (now <= n && ar[now].first <= q2[i].x)
        {
            if (!vis[ar[now].second])
                change (ar[now].second);
            now ++;
            coun ++;
        }

        lst = top;
        for (int j = 1; j <= m1 && q1[j].id <= q2[i].id; j++)
            c[pre[q1[j].l]] = q1[j].r , de[q1[j].l] = 1;
        for (Q* j = q1 + 1; j != q1 + m1 + 1; j++)
        {
            if ((*j).r <= q2[i].x && (*j).id <= q2[i].id && c[pre[(*j).l]] == (*j).r)
                c[pre[(*j).l]] = -1 , change ((*j).l);
            if (ar[pre[(*j).l]].first <= q2[i].x && (*j).id > q2[i].id && !de[(*j).l])
                change ((*j).l);
                // coun ++;
        }
        ans[Rid[q2[i].id]] += query (q2[i].l , q2[i].r);
        while (top ^ lst) remove ();
        for (int j = 1; j <= m1 && q1[j].id <= q2[i].id; j++)
        {
            c[pre[q1[j].l]] = ar[pre[q1[j].l]].first;
            de[q1[j].l] = 0;
            // coun ++;
        }
    }

    if (m1)
    {
        for (int i = 1; i <= m1; i++)
            ar[pre[q1[i].l]].first = q1[i].r;
        for (int i = 1; i <= n; i++)
            t.addedge (ar[i].first , ar[i].second);
        now = 0;
        for (int i = 1; i <= n; i++)
        {
            for (int j = t.head[i]; j ; j = t.a[j].nxt)
                ar[++now] = {i , t.a[j].to};
            t.tot = t.head[i] = 0;
            // coun ++;
        }
    }
    
    for (int i = 1; i <= n; i++)
    {
        b[i].va = 0 , de[i] = 0 , b[i].id = 0;
        if (i <= tot) val[i] = 0;
        vis[i] = 0; c[i] = 0;
        // coun ++;
    }
        
    top = 0; idx = 0 ;

    for (int i = 1; i <= m2; i++)
        std :: cout << ans[i] << "\n" , ans[i] = 0 ;
}

signed main ()
{
    n = read () , m = read ();
    for (int i = 1; i <= n; i++) ar[i].first = read () , ar[i].second = i;
    std :: sort (ar + 1 , ar + n + 1);

    tot = sqrt (n);
    for (int i = 1; i <= tot; i++)
        L[i] = R[i - 1] + 1 , R[i] = L[i] + n / tot - 1;
    if (R[tot] < n) R[tot] = n;
    for (int i = 1; i <= tot; i++)
        for (int j = L[i]; j <= R[i]; j++)
            b[j].pos = i;

    int B = sqrt (m) * 3.5;
    for (int i = 1 , cnt = 0; i <= m; )
    {
        while (cnt < B && i <= m)
        {
            q[++cnt].opt = read () , q[cnt].l = read () , q[cnt].r = read ();
            if (q[cnt].opt == 2) q[cnt].x = read (); q[cnt].id = cnt;
            i++;
        }
        FakeQuery (cnt) , cnt = 0;
    }
    cerr << coun;
    return 0;
}