这个线段树板子我已经过了【模板】线段树 1,大体上应该是没有问题的。
在 test 处输出线段树内容发现全部为空(全 0 结构体),有没有熟悉 AtCoder Library 库的人可以解释一下这是什么情况?
#include<bits/stdc++.h>
using namespace std;
#define ep emplace
#define eb emplace_back
#define ef emplace_front
#define ll long long
const int N = 600000;
struct tag{
int sum,lmx,rmx,mx,mxn;
};
int n,m,x,y,z,tmp;
ll w;
tag d[N << 2];
vector<tag> a;
inline int ceil_pow2(int n){
int x = 0;while ((1u << x) < (unsigned int)(n)) x ++;
return x;
}
inline tag op(tag a,tag b){
return {a.sum + b.sum,max(a.lmx,a.sum + b.lmx),max(b.rmx,b.sum + a.rmx),max(a.rmx + b.lmx,max(a.mx,b.mx)),max(a.mxn,b.mxn)};
}
inline tag e(){return {0,0,0,0,-10000};}
inline tag mapping(int a,tag b){return {max(0,a),max(0,a),max(0,a),max(0,a),a};}
inline int id(){return 0;}inline int composition(int a,int b){return id();}//单点修改用不上这些
template <class S,//保存信息类型
S (*op)(S,S),//信息的合并函数
S (*e)(),//信息单位元
class F,//懒标记类型
S (*mapping)(F,S),//标记对信息的影响
F (*composition)(F,F),//标记的合并函数
F (*id)()>//标记单位元
struct lazy_segtree{
lazy_segtree() : lazy_segtree(0){}
lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())){}
lazy_segtree(const vector<S>& v) : _n(int(v.size())){
log = ceil_pow2(_n);
size = 1 << log;
d = vector<S>(2 * size, e());
lz = vector<F>(size, id());
for(int i = 0;i < _n;i ++) d[size + i] = v[i];
for(int i = size - 1;i >= 1;i --){
update(i);
}
}
void set(int p,S x){
assert(0 <= p && p < _n);
p += size;
for(int i = log;i >= 1;i --) push(p >> i);
d[p] = x;
for(int i = 1;i <= log;i ++) update(p >> i);
}
S get(int p){
assert(0 <= p && p < _n);
p += size;
for(int i = log;i >= 1;i --) push(p >> i);
return d[p];
}
S prod(int l, int r){
assert(0 <= l && l <= r && r <= _n);
if (l == r) return e();
l += size;
r += size;
for(int i = log;i >= 1;i --){
if(((l >> i) << i) != l) push(l >> i);
if(((r >> i) << i) != r) push(r >> i);
}
S sml = e(),smr = e();
while(l < r){
if(l & 1) sml = op(sml,d[l ++]);
if(r & 1) smr = op(d[-- r],smr);
l >>= 1;
r >>= 1;
}
return op(sml, smr);
}
S all_prod(){return d[1];}
void apply(int p,F f){
assert(0 <= p && p < _n);
p += size;
for(int i = log;i >= 1;i --) push(p >> i);
d[p] = mapping(f,d[p]);
for(int i = 1;i <= log;i ++) update(p >> i);
}
void apply(int l,int r,F f){
assert(0 <= l && l <= r && r <= _n);
if(l == r) return;
l += size;
r += size;
for(int i = log;i >= 1;i --){
if(((l >> i) << i) != l) push(l >> i);
if(((r >> i) << i) != r) push((r - 1) >> i);
}
{
int l2 = l,r2 = r;
while(l < r){
if(l & 1) all_apply(l ++,f);
if(r & 1) all_apply(-- r,f);
l >>= 1;
r >>= 1;
}
l = l2;
r = r2;
}
for(int i = 1;i <= log;i ++){
if(((l >> i) << i) != l) update(l >> i);
if(((r >> i) << i) != r) update((r - 1) >> i);
}
}
template <bool (*g)(S)> int max_right(int l){
return max_right(l,[](S x){return g(x);});
}
template <class G> int max_right(int l,G g){
assert(0 <= l && l <= _n);
assert(g(e()));
if(l == _n) return _n;
l += size;
for(int i = log;i >= 1;i --) push(l >> i);
S sm = e();
do{
while(l % 2 == 0) l >>= 1;
if(!g(op(sm,d[l]))){
while(l < size){
push(l);
l = (2 * l);
if(g(op(sm,d[l]))){
sm = op(sm, d[l]);
l ++;
}
}
return l - size;
}
sm = op(sm,d[l]);
l ++;
}while((l & -l) != l);
return _n;
}
template <bool (*g)(S)> int min_left(int r){
return min_left(r,[](S x){return g(x);});
}
template <class G> int min_left(int r,G g){
assert(0 <= r && r <= _n);
assert(g(e()));
if (r == 0) return 0;
r += size;
for(int i = log;i >= 1;i --) push((r - 1) >> i);
S sm = e();
do{
r --;
while (r > 1 && (r % 2)) r >>= 1;
if(!g(op(d[r],sm))){
while(r < size){
push(r);
r = (2 * r + 1);
if(g(op(d[r],sm))){
sm = op(d[r],sm);
r --;
}
}
return r + 1 - size;
}
sm = op(d[r],sm);
}while((r & -r) != r);
return 0;
}
int _n,size,log;
vector<S> d;
vector<F> lz;
void update(int k){d[k] = op(d[2 * k],d[2 * k + 1]);}
void all_apply(int k, F f){
d[k] = mapping(f,d[k]);
if(k < size) lz[k] = composition(f,lz[k]);
}
void push(int k){
all_apply(2 * k,lz[k]);
all_apply(2 * k + 1,lz[k]);
lz[k] = id();
}
};
int main(){
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
a.resize(n,e());
for(auto &i : a) cin >> tmp,i.sum = i.mx = i.lmx = i.rmx = max(0,tmp),i.mxn = tmp;
lazy_segtree<tag,op,e,int,mapping,composition,id> tree(a);
for(int i = 0;i < n;i ++){
tree.set(i,a[i]);
}
for(int i = 1;i <= n;i ++){//test
for(int j = i;j <= n;j ++){
auto a = tree.prod(i - 1,j);
printf("[%d, %d], [%d, %d, %d, %d, %d]\n",i,j,a.sum,a.lmx,a.rmx,a.mx,a.mxn);
}
}
for(int i = 1;i <= m;i ++){
cin >> x >> y >> z;
if(x == 1){
if(y > z) swap(y,z);
auto i = tree.prod(y - 1,z);
printf("%d\n",i.mx ? i.mx : i.mxn);
}
else{
tree.apply(y - 1,z);
for(int i = 1;i <= n;i ++){
for(int j = i;j <= n;j ++){
auto a = tree.prod(i - 1,j);
printf("[%d, %d], [%d, %d, %d, %d, %d]\n",i,j,a.sum,a.lmx,a.rmx,a.mx,a.mxn);
}
}
}
}
return 0;
}