拿 AT 线段树做 P4513 线段树存不进东西求助
  • 板块学术版
  • 楼主chenxi2009
  • 当前回复0
  • 已保存回复0
  • 发布时间2025/7/25 15:49
  • 上次更新2025/7/25 19:50:47
查看原帖
拿 AT 线段树做 P4513 线段树存不进东西求助
1020063
chenxi2009楼主2025/7/25 15:49

这个线段树板子我已经过了【模板】线段树 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;
}
2025/7/25 15:49
加载中...