ABC426F题解
2025-10-04 23:10:48
发布于：广东
可恶的 ABC，前几场 F 这么水，这场这么逆天，害得我惯性思维先做 F 掉大分。
掉大分了，所以：
我常常追忆过去。
生命瞬间定格在脑海。我将背后的时间裁剪、折叠、蜷曲，揉捻成天上朵朵白云。
云朵之间亦有分别：积云厚重，而卷云飘渺。生命里震撼的场景掠过我的思绪便一生无法忘怀，而更为普通平常的记忆在时间的冲刷下只留下些许残骸。追忆宛如入梦，太过清楚则无法愉悦自己的幻想，过分模糊却又坠入虚无。只有薄雾间的山水，面纱下的女子，那恰到好处的朦胧，才能满足我对美的苛求。
追忆总在不经意间将我裹进泛黄的纸页里。分别又重聚的朋友，推倒又重建的街道，种种线索协助着我从一个具体的时刻出发沿时间的河逆流而上。曾经的日子无法重来，我只不过是一个过客。但我仍然渴望在每一次追忆之旅中留下闲暇时间，在一个场景前驻足，在岁月的朦胧里瞭望过去的自己，感受尽可能多的甜蜜。美好的时光曾流过我的身体，我便心满意足。
过去已经凝固，我带着回忆向前，只是时常疏于保管，回忆也在改变着各自的形态。这给我的追忆旅程带来些许挑战。
我该在哪里停留？我问我自己。
好了，说解法。
赛时想了半个小时没想到除了数据结构以外的解法，那正解应该就是数据结构了。
考虑线段树。
注意到把一种商品买空最多只有 次，其余的要么买 个要么买 个。
所以我们可以维护：
- ：没被买空的商品种数，即不为 的 个数。
- ：在没被买空的商品中，商品个数的最小值，也就是不为 的 最小值。为方便记录，如果该区间所有商品都被买空，则 。
push_up函数如下：
void push_up(int u){
if(!tree[u << 1]) tree[u] = tree[u << 1 | 1];
else if(!tree[u << 1 | 1]) tree[u] = tree[u << 1];
else tree[u] = min(tree[u << 1], tree[u << 1 | 1]);
cnt[u] = cnt[u << 1] + cnt[u << 1 | 1];
}
好的，然后看怎么修改、查询。
注意到上面提到的把一种商品买空最多只有 次，所以我们可以分为两种情况：有商品数量小于等于 ，没有商品数量小于等于 。
当一个区间有商品数量小于等于 时，我们可以不管左右区间是否已经在查询区间内，继续递归下去，直到查到具体的那几个商品，然后清空。
当全部大于 时，和正常线段树操作一样，在查询区间内打个标记结束。
注意正常买的商品种数不是 ，而是 。
int _query(int u, int l, int r, int k){
if(tree[u] == 0) return 0;
if(tree[u] <= k){
if(left[u] == right[u]){
int ans = tree[u];
tree[u] = 0, cnt[u] = 0;
return ans;
}
push_down(u);
int ans = 0, mid = left[u] + right[u] >> 1;
if(l <= mid) ans += _query(u << 1, l, r, k);
if(r > mid) ans += _query(u << 1 | 1, l, r, k);
push_up(u);
return ans;
}
if(left[u] >= l && right[u] <= r){
tree[u] -= k, lazytag[u] += k;
return k * cnt[u];
}
push_down(u);
int ans = 0, mid = left[u] + right[u] >> 1;
if(l <= mid) ans += _query(u << 1, l, r, k);
if(r > mid) ans += _query(u << 1 | 1, l, r, k);
push_up(u);
return ans;
}
int query(int l, int r, int k){
return _query(1, l, r, k);
}
这样的时间复杂度是多少呢？
首先分析都大于 的情况，很显然左右子节点的结果也会大于 ，所以单次询问时间复杂度是 的。
然后再看有小于等于 的情况，会分成两个，其中如果有一个是大于 ，则会落到上面那个情况，单次 ；否则会分成具体的商品。根据上面清空不超过 次的结论，也可以轻松得出清空的总复杂度是 的。
所以总时间复杂度是 。
代码如下：
#include <iostream>
#include <cstdio>
#include <vector>
#define int long long
using namespace std;
int a[300005];
int n, m;
class Segtree{
private:
vector <int> tree, lazytag, cnt, left, right;
void push_up(int u){
if(!tree[u << 1]) tree[u] = tree[u << 1 | 1];
else if(!tree[u << 1 | 1]) tree[u] = tree[u << 1];
else tree[u] = min(tree[u << 1], tree[u << 1 | 1]);
cnt[u] = cnt[u << 1] + cnt[u << 1 | 1];
}
void push_down(int u){
if(tree[u << 1]){
lazytag[u << 1] += lazytag[u];
tree[u << 1] -= lazytag[u];
}
if(tree[u << 1 | 1]){
lazytag[u << 1 | 1] += lazytag[u];
tree[u << 1 | 1] -= lazytag[u];
}
lazytag[u] = 0;
}
void build(int u, int l, int r){
left[u] = l, right[u] = r;
if(l == r){
tree[u] = a[l];
if(a[l]) cnt[u] = 1;
return;
}
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
push_up(u);
}
int _query(int u, int l, int r, int k){
if(tree[u] == 0) return 0;
if(tree[u] <= k){
if(left[u] == right[u]){
int ans = tree[u];
tree[u] = 0, cnt[u] = 0;
return ans;
}
push_down(u);
int ans = 0, mid = left[u] + right[u] >> 1;
if(l <= mid) ans += _query(u << 1, l, r, k);
if(r > mid) ans += _query(u << 1 | 1, l, r, k);
push_up(u);
return ans;
}
if(left[u] >= l && right[u] <= r){
tree[u] -= k, lazytag[u] += k;
return k * cnt[u];
}
push_down(u);
int ans = 0, mid = left[u] + right[u] >> 1;
if(l <= mid) ans += _query(u << 1, l, r, k);
if(r > mid) ans += _query(u << 1 | 1, l, r, k);
push_up(u);
return ans;
}
public:
Segtree(){}
void init(){
tree.resize(n << 2 | 1, 0);
left.resize(n << 2 | 1, 0);
right.resize(n << 2 | 1, 0);
lazytag.resize(n << 2 | 1, 0);
cnt.resize(n << 2 | 1, 0);
build(1, 1, n);
}
int query(int l, int r, int k){
return _query(1, l, r, k);
}
}t;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
t.init();
cin >> m;
while(m--){
int l, r, k;
cin >> l >> r >> k;
cout << t.query(l, r, k) << '\n';
}
return 0;
}
全部评论 6
我常常追忆过去。
生命瞬间定格在脑海。我将背后的时间裁剪、折叠、蜷曲，揉捻成天上朵朵白云。
云朵之间亦有分别：积云厚重，而卷云飘渺。生命里震撼的场景掠过我的思绪便一生无法忘怀，而更为普通平常的记忆在时间的冲刷下只留下些许残骸。追忆宛如入梦，太过清楚则无法愉悦自己的幻想，过分模糊却又坠入虚无。只有薄雾间的山水，面纱下的女子，那恰到好处的朦胧，才能满足我对美的苛求。
追忆总在不经意间将我裹进泛黄的纸页里。分别又重聚的朋友，推倒又重建的街道，种种线索协助着我从一个具体的时刻出发沿时间的河逆流而上。曾经的日子无法重来，我只不过是一个过客。但我仍然渴望在每一次追忆之旅中留下闲暇时间，在一个场景前驻足，在岁月的朦胧里瞭望过去的自己，感受尽可能多的甜蜜。美好的时光曾流过我的身体，我便心满意足。
过去已经凝固，我带着回忆向前，只是时常疏于保管，回忆也在改变着各自的形态。这给我的追忆旅程带来些许挑战。
我该在哪里停留？我问我自己。
2025-10-04 来自 广东
0
有帮助，赞一个