社区讨论
求问编译器
学术版参与者 4已保存回复 4
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 4 条
- 当前快照
- 1 份
- 快照标识符
- @mkp59hmn
- 此快照首次捕获于
- 2026/01/22 15:42 4 周前
- 此快照最后确认于
- 2026/01/22 22:28 4 周前
如下是一份哈吉吉线段树的代码,在 GCC 11.5.0 的编译环境下会产生一个高达 60MB 大小的 exe 文件。
提交到 OJ 上会导致编译超限(Compiler Output Limit Exceeded)。
求问是不是产生了类似 CSP-S T3 那位选手的错误展开之类的问题。
CPP#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int n, q;
int a[N];
struct Node{
int min = INT_MAX;
int minb = INT_MAX;
int smin = INT_MAX;
int taga = 0, taga1 = 0;
int tagb = 0, tagb1 = 0;
friend Node operator +(const Node &L, const Node &R){
Node res;
res.min = std::min(L.min, R.min);
res.minb = std::min(L.minb, R.minb);
if (res.min == L.min) res.smin = std::min(res.smin, L.smin);
else res.smin = std::min(res.smin, L.min);
if (res.min == R.min) res.smin = std::min(res.smin, R.smin);
else res.smin = std::min(res.smin, R.min);
return res;
}
}tr[N << 2];
#define ls (p << 1)
#define rs (p << 1 | 1)
#define mid ((l + r) >> 1)
void build(int p, int l, int r){
if (l == r){
tr[p].minb = tr[p].min = a[l];
return;
}
build(ls, l, mid);
build(rs, mid + 1, r);
tr[p] = tr[ls] + tr[rs];
}
void Add(int p, int taga, int tagb, int taga1, int tagb1){
tr[p].minb = min(tr[p].minb, tr[p].min + tagb);
tr[p].min += taga;
tr[p].tagb = min(tr[p].tagb, tr[p].taga + tagb);
tr[p].taga += taga;
if (tr[p].smin != INT_MAX){
tr[p].smin += taga1;
tr[p].tagb1 = min(tr[p].tagb1, tr[p].taga1 + tagb1);
tr[p].taga1 += taga1;
}
}
void pushdown(int p){
int val = min(tr[ls].min, tr[rs].min);
if (tr[ls].min == val) Add(ls, tr[p].taga, tr[p].tagb, tr[p].taga1, tr[p].tagb1);
else Add(ls, tr[p].taga1, tr[p].tagb1, tr[p].taga1, tr[p].tagb1);
if (tr[rs].min == val) Add(rs, tr[p].taga, tr[p].tagb, tr[p].taga1, tr[p].tagb1);
else Add(rs, tr[p].taga1, tr[p].tagb1, tr[p].taga1, tr[p].tagb1);
tr[p].taga = tr[p].tagb = tr[p].taga1 = tr[p].tagb1 = 0;
}
void update1(int p, int l, int r, int s, int t, int v){
if (s <= l && r <= t){
Add(p, v, v, v, v);
return;
}
pushdown(p);
if (s <= mid) update1(ls, l, mid, s, t, v);
if (mid < t) update1(rs, mid + 1, r, s, t, v);
tr[p] = tr[ls] + tr[rs];
}
void update2(int p, int l, int r, int s, int t, int v){
if (tr[p].min >= v) return;
if (s <= l && r <= t){
if (l == r || tr[p].smin > v){
int x = v - tr[p].min;
Add(p, x, x, 0, 0);
return;
}
}
pushdown(p);
if (s <= mid) update2(ls, l, mid, s, t, v);
if (mid < t) update2(rs, mid + 1, r, s, t, v);
tr[p] = tr[ls] + tr[rs];
}
Node ask(int p, int l, int r, int s, int t){
if (s <= l && r <= t) return tr[p];
pushdown(p);
if (mid < s) return ask(rs, mid + 1, r, s, t);
if (t <= mid) return ask(ls, l, mid, s, t);
return ask(ls, l, mid, s, t) + ask(rs, mid + 1, r, s, t);
}
#undef ls
#undef rs
#undef mid
signed main(){
#ifndef DEBUG
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
#endif
cin >> n >> q;
for (int i = 1; i <= n; i ++) cin >> a[i];
build(1, 1, n);
for (int opt, l, r; q --; ){
cin >> opt >> l >> r;
if (opt == 1){
int v;
cin >> v;
update1(1, 1, n, l, r, v);
}
if (opt == 2){
int v;
cin >> v;
update2(1, 1, n, l, r, v);
}
if (opt == 3)
cout << ask(1, 1, n, l, r).min << "\n";
if (opt == 4)
cout << ask(1, 1, n, l, r).minb << "\n";
}
}
回复
共 4 条回复,欢迎继续交流。
正在加载回复...