Description
给定长度为 (n) 的非递增序列。在一段路上依次有 (n) 个商店，第 (i) 个商店有一种商品，价格为 (a_i)。有 (q) 次操作，每次操作有两种。
1 x y 表示对于任意 (i in [1,x])，令 (a_i = max(a_i, y))。
2 x y 表示从拿着 (y) 元钱从第 (x) 个商店开始，如果能购买就购买一份，并往右走，求购买了多少件商品。
Solution
由于序列是单调的，每个人的购买序列一定构成不超过 (log n) 个连续段，同时每次修改操作相当于区间覆盖。
因此考虑线段树上二分。
对于操作 (1)，我们需要找到第一个不大于 (y) 的元素，设这个元素的位置为 (pos)，则我们将 ([pos,x]) 区间覆盖为 (y) 即可，因此线段树需要一个表示区间覆盖的标记。
对于操作 (2)，我们从二分出下一个可以购买的元素在哪里（即二分找到第一个不大于 (key) 的元素的位置），再找到能从这个位置连续购买到哪个位置为止（即找到最后一个保持这段的和不超过 (key) 的位置），购买这一段，然后继续进行上述过程，直到到达序列末尾。
因此，线段树需要支持区间求和，二分答案找第一个不大于 (key) 的元素（在单调序列上），二分答案找最后一个前缀和不大于 (key) 的元素，区间覆盖，因此需要对于每个结点维护一个结点对应区间中的最大值最小值、区间和 (sum)、区间覆盖标记 (tag)，当标记为 (0) 时表示无标记，否则表示区间覆盖为多少。
首先我们实现一个支持以上功能的线段树，然后遍历所有操作，对于操作 (2) 循环处理，其它操作直接调用即可。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXNULL = 0;
const int MINNULL = 1e18;
const int BISECTNULL = -1;
#define dbg 0
struct SegmentTreeNode
{
int maximum, minimum;
long long sum;
int tag;
SegmentTreeNode operator+(const SegmentTreeNode &b)
{
return {max(maximum, b.maximum), min(minimum, b.minimum), sum + b.sum, 0};
}
};
class SegmentTree
{
public:
SegmentTreeNode *nodes;
private:
int size;
public:
SegmentTree(int size_)
{
size = size_;
nodes = new SegmentTreeNode[4 * size + 5];
}
private:
void put(int p, int l, int r, int key)
{
nodes[p].maximum = key;
nodes[p].minimum = key;
nodes[p].sum = 1ll * key * (r - l + 1);
nodes[p].tag = key;
}
void pushdown(int p, int l, int r)
{
if (nodes[p].tag)
{
int tmp = nodes[p].tag;
put(p * 2, l, (l + r) / 2, tmp);
put(p * 2 + 1, (l + r) / 2 + 1, r, tmp);
nodes[p].tag = 0;
}
}
void pushup(int p, int l, int r)
{
nodes[p] = nodes[p * 2] + nodes[p * 2 + 1];
}
void modify(int p, int l, int r, int ql, int qr, int key)
{
if (l > qr || r < ql)
return;
if (l >= ql && r <= qr)
{
put(p, l, r, key);
}
else
{
pushdown(p, l, r);
modify(p * 2, l, (l + r) / 2, ql, qr, key);
modify(p * 2 + 1, (l + r) / 2 + 1, r, ql, qr, key);
pushup(p, l, r);
}
}
SegmentTreeNode query(int p, int l, int r, int ql, int qr)
{
if (l > qr || r < ql)
{
return {MAXNULL, MINNULL, 0, 0};
}
if (l >= ql && r <= qr)
{
return nodes[p];
}
else
{
pushdown(p, l, r);
return query(p * 2, l, (l + r) / 2, ql, qr) + query(p * 2 + 1, (l + r) / 2 + 1, r, ql, qr);
}
}
public:
void Modify(int ql, int qr, int key)
{
modify(1, 1, size, ql, qr, key);
}
long long QuerySum(int ql, int qr)
{
return query(1, 1, size, ql, qr).sum;
}
int QueryMaximum(int ql, int qr)
{
return query(1, 1, size, ql, qr).maximum;
}
private:
void build(int p, int l, int r, vector<int> &src)
{
if (l == r)
{
nodes[p] = {src[l], src[l], src[l], 0};
}
else
{
build(p * 2, l, (l + r) / 2, src);
build(p * 2 + 1, (l + r) / 2 + 1, r, src);
pushup(p, l, r);
}
}
public:
void Build(vector<int> &src)
{
build(1, 1, size, src);
}
private:
int findFirstLeqKey(int p, int l, int r, int key)
{
if (l == r)
{
if (nodes[p].maximum <= key)
{
return l;
}
else
{
return BISECTNULL;
}
}
else
{
pushdown(p, l, r);
if (nodes[p * 2].minimum <= key)
{
return findFirstLeqKey(p * 2, l, (l + r) / 2, key);
}
else
{
return findFirstLeqKey(p * 2 + 1, (l + r) / 2 + 1, r, key);
}
}
}
public:
int FindFirstLeqKey(int key)
{
return findFirstLeqKey(1, 1, size, key);
}
private:
int findLastLeqSum(int p, int l, int r, long long sum)
{
if (l == r)
{
if (nodes[p].sum <= sum)
{
return l;
}
else
{
return l - 1;
}
}
else
{
pushdown(p, l, r);
if (nodes[p * 2].sum >= sum)
{
return findLastLeqSum(p * 2, l, (l + r) / 2, sum);
}
else
{
return findLastLeqSum(p * 2 + 1, (l + r) / 2 + 1, r, sum - nodes[p * 2].sum);
}
}
}
public:
int FindLastLeqSum(long long sum)
{
return findLastLeqSum(1, 1, size, sum);
}
int FindLastLeqRange(int startpos, long long sum)
{
int presum = QuerySum(1, startpos - 1);
sum += presum;
return findLastLeqSum(1, 1, size, sum);
}
};
signed main()
{
ios::sync_with_stdio(false);
int n, q;
cin >> n >> q;
vector<int> a(n + 2);
for (int i = 1; i <= n; i++)
cin >> a[i];
SegmentTree segtree(n);
segtree.Build(a);
for (int i = 1; i <= q; i++)
{
long long t, x, y;
cin >> t >> x >> y;
if (t == 1)
{
// i in [1,x], do max with y
int pos = segtree.FindFirstLeqKey(y);
if (~pos)
{
segtree.Modify(pos, x, y);
}
}
else
{
// do from x, total y
int ans = 0;
while (x <= n)
{
int pos = segtree.FindFirstLeqKey(y);
if (~pos)
{
pos = max(1ll * pos, x);
int endpos = segtree.FindLastLeqRange(pos, y);
long long sum = segtree.QuerySum(pos, endpos);
y -= sum;
ans += endpos - pos + 1;
x = endpos + 1;
if (y <= 0)
break;
if (dbg)
cout << "buy " << pos << " " << endpos << " sum=" << sum << endl;
}
else
{
break;
}
}
cout << ans << endl;
}
}
}
// 线段树功能测试
// signed main()
// {
// vector<int> a = {0, 4, 4, 4, 2, 1};
// SegmentTree segtree(5);
// segtree.Build(a);
// while (true)
// {
// string tmp;
// getline(cin, tmp);
// stringstream ss(tmp);
// string op;
// ss >> op;
// if (op == "qm")
// {
// int t1, t2;
// ss >> t1 >> t2;
// cout << segtree.QueryMaximum(t1, t2) << endl;
// }
// else if (op == "qs")
// {
// int t1, t2;
// ss >> t1 >> t2;
// cout << segtree.QuerySum(t1, t2) << endl;
// }
// else if (op == "m")
// {
// int t1, t2, t3;
// ss >> t1 >> t2 >> t3;
// segtree.Modify(t1, t2, t3);
// }
// else if (op == "ff")
// {
// int t1;
// ss >> t1;
// cout << segtree.FindFirstLeqKey(t1) << endl;
// }
// else if (op == "fl")
// {
// int t1;
// ss >> t1;
// cout << segtree.FindLastLeqSum(t1) << endl;
// }
// }
// } UPD: TLE on Test 99