摘苹果
分析：
修改相当于单点修改，但加了 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;
}