摘苹果

分析：

修改相当于单点修改，但加了 return 过的飞快
裸线段树基本操作

实现：

#include <bits/stdc++.h>
using namespace std;
#define mst(x, y) memset(x, y, sizeof x)
#define endl '\n'
#define INF LONG_LONG_MAX
#define int long long
#define Lson u << 1, l, mid
#define Rson u << 1 | 1, mid + 1, r
#define FAST ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const int N = 2000010, MOD = 1e9 + 7;
const double EPS = 1e-6;
typedef pair<int, int> PII;
int T;
int n, m;
int a[N];
struct Node
{
    int l, r;
    int sum, maxv, cnt;
} tr[N << 2];
void pushup(Node &u, Node &l, Node &r)
{
    u.cnt = l.cnt + r.cnt;
    u.sum = l.sum + r.sum;
    u.maxv = max(l.maxv, r.maxv);
}
void pushup(int u)
{
    pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}
void build(int u, int l, int r)
{
    if (l == r)
        tr[u] = {r, r, a[r], a[r], (a[r] < 100)};
    else
    {
        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(Lson), build(Rson);
        pushup(u);
    }
}
void modify(int u, int l, int r)
{
    if (tr[u].maxv < 10)
        return;
    if (tr[u].l == tr[u].r)
    {
        tr[u].sum = tr[u].sum * 2 / 3;
        tr[u].cnt = tr[u].sum < 100 ? 1 : 0;
        tr[u].maxv = tr[u].sum;
    }
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid)
            modify(u << 1, l, r);
        if (r > mid)
            modify(u << 1 | 1, l, r);
        pushup(u);
    }
}
Node query(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r)
        return tr[u];
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if (r <= mid)
            return query(u << 1, l, r);
        else if (l > mid)
            return query(u << 1 | 1, l, r);
        else
        {
            auto ll = query(u << 1, l, r), rr = query(u << 1 | 1, l, r);
            Node res;
            pushup(res, ll, rr);
            return res;
        }
    }
}
void solve()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    build(1, 1, n);

    for (int i = 1, op, l, r; i <= m; i++)
    {
        cin >> op >> l >> r;
        if (op == 1)
            modify(1, l, r);
        else if (op == 2)
            cout << query(1, l, r).cnt << endl;
        else
            cout << query(1, l, r).sum << endl;
    }
}
signed main()
{
    FAST;
    T = 1;
    // cin >> T;
    while (T--)
        solve();
    return 0;
}