求助CSTN loves segment tree
  • 板块学术版
  • 楼主alpharchmage
  • 当前回复0
  • 已保存回复0
  • 发布时间2025/1/21 16:20
  • 上次更新2025/1/21 18:52:22
查看原帖
求助CSTN loves segment tree
411141
alpharchmage楼主2025/1/21 16:20
#include<bits/stdc++.h>
#define int long long
#define inf LLONG_MAX
using namespace std;
int n = 0 , m = 0;
array<int , 300100> a , b;
struct Tree{
	int l;
	int r;
	int tag_val[2];
	int tag_min[2];
	int the_max[2];
	int sec_max[2];
	int max_val[2][2];
};
array<Tree , 8000100> tree;
void pushup(int k)
{
	for(auto x : {0 , 1})
	{
		if(tree[k << 1].the_max[x] == tree[k << 1 | 1].the_max[x])
		{
			tree[k].the_max[x] = tree[k << 1].the_max[x];
			tree[k].sec_max[x] = max(tree[k << 1].sec_max[x] , tree[k << 1 | 1].sec_max[x]); 
		}
		else if(tree[k << 1].the_max[x] > tree[k << 1 | 1].the_max[x])
		{
			tree[k].the_max[x] = tree[k << 1].the_max[x];
			tree[k].sec_max[x] = max(tree[k << 1].sec_max[x] , tree[k << 1 | 1].the_max[x]); 
		}
		else
		{
			tree[k].the_max[x] = tree[k << 1 | 1].the_max[x];
			tree[k].sec_max[x] = max(tree[k << 1].the_max[x] , tree[k << 1 | 1].sec_max[x]);
		}
	}
	if(tree[k].the_max[0] == tree[k << 1].the_max[0] && tree[k].the_max[1] == tree[k << 1].the_max[1])
	{
		tree[k].max_val[1][1] = tree[k << 1].max_val[1][1];
		tree[k].max_val[0][1] = tree[k << 1].max_val[0][1];
		tree[k].max_val[1][0] = tree[k << 1].max_val[1][0];
		tree[k].max_val[0][0] = tree[k << 1].max_val[0][0];
	}
	else if(tree[k].the_max[0] == tree[k << 1].the_max[0] && tree[k].the_max[1] != tree[k << 1].the_max[1])
	{
		tree[k].max_val[1][1] = tree[k].max_val[0][1] = -inf;
		tree[k].max_val[1][0] = max(tree[k << 1].max_val[1][1] , tree[k << 1].max_val[1][0]);
		tree[k].max_val[0][0] = max(tree[k << 1].max_val[0][1] , tree[k << 1].max_val[0][0]);
	}
	else if(tree[k].the_max[0] != tree[k << 1].the_max[0] && tree[k].the_max[1] == tree[k << 1].the_max[1])
	{
		tree[k].max_val[1][1] = tree[k].max_val[1][0] = -inf;
		tree[k].max_val[0][1] = max(tree[k << 1].max_val[1][1] , tree[k << 1].max_val[0][1]);
		tree[k].max_val[0][0] = max(tree[k << 1].max_val[1][0] , tree[k << 1].max_val[0][0]);
	}
	else
	{
		tree[k].max_val[1][1] = tree[k].max_val[1][0] = tree[k].max_val[0][1] = -inf;
		tree[k].max_val[0][0] = max({tree[k << 1].max_val[0][0] , tree[k << 1].max_val[0][1] , tree[k << 1].max_val[1][0] , tree[k << 1].max_val[1][1]});
	}
	if(tree[k].the_max[0] == tree[k << 1 | 1].the_max[0] && tree[k].the_max[1] == tree[k << 1 | 1].the_max[1])
	{
		tree[k].max_val[1][1] = max(tree[k].max_val[1][1] , tree[k << 1 | 1].max_val[1][1]);
		tree[k].max_val[1][0] = max(tree[k].max_val[1][0] , tree[k << 1 | 1].max_val[1][0]);
		tree[k].max_val[0][1] = max(tree[k].max_val[0][1] , tree[k << 1 | 1].max_val[0][1]);
		tree[k].max_val[0][0] = max(tree[k].max_val[0][0] , tree[k << 1 | 1].max_val[0][0]);
	}
	else if(tree[k].the_max[0] == tree[k << 1 | 1].the_max[0] && tree[k].the_max[1] != tree[k << 1 | 1].the_max[1])
	{
		tree[k].max_val[1][0] = max({tree[k].max_val[1][0] , tree[k << 1 | 1].max_val[1][1] , tree[k << 1 | 1].max_val[1][0]});
		tree[k].max_val[0][0] = max({tree[k].max_val[0][0] , tree[k << 1 | 1].max_val[0][1] , tree[k << 1 | 1].max_val[0][0]});
	}
	else if(tree[k].the_max[0] != tree[k << 1 | 1].the_max[0] && tree[k].the_max[1] == tree[k  << 1 | 1].the_max[1])
	{
		tree[k].max_val[0][1] = max({tree[k].max_val[0][1] , tree[k << 1 | 1].max_val[1][1] , tree[k << 1 | 1].max_val[0][1]});
		tree[k].max_val[0][0] = max({tree[k].max_val[0][0] , tree[k << 1 | 1].max_val[1][0] , tree[k << 1 | 1].max_val[0][0]});
	}
	else
	{
		tree[k].max_val[0][0] = max({tree[k].max_val[0][0] , tree[k << 1 | 1].max_val[0][0] , tree[k << 1 | 1].max_val[0][1] , tree[k << 1 | 1].max_val[1][0] , tree[k << 1 | 1].max_val[1][1]});
	}
	return;
}
void pushmin(int k , int pos , int val)
{
	if(tree[k].the_max[pos] <= val) return;
	if(tree[k].max_val[1][1] != -inf) tree[k].max_val[1][1] += (val - tree[k].the_max[pos]);
	if(tree[k].max_val[!pos][pos] != -inf) tree[k].max_val[!pos][pos] += (val - tree[k].the_max[pos]);
	tree[k].the_max[pos] = tree[k].tag_min[pos] = val;
	return;
}
void pushsum(int k , int pos , int val)
{
	for(auto x : {0 , 1})
	{
		for(auto y : {0 , 1})
		{
			if(tree[k].max_val[x][y] != -inf) tree[k].max_val[x][y] += val;
		}
	}
	tree[k].the_max[pos] += val;
	if(tree[k].sec_max[pos] != -inf) tree[k].sec_max[pos] += val;
	if(tree[k].tag_min[pos] != inf) tree[k].tag_min[pos] += val;
	tree[k].tag_val[pos] += val;
	return;
}
void pushdown(int k)
{
	for(auto x : {0 , 1})
	{
		if(tree[k].tag_val[x])
		{
			pushsum(k << 1 , x , tree[k].tag_val[x]);
			pushsum(k << 1 | 1 , x , tree[k].tag_val[x]);
		}
	}
	for(auto x : {0 , 1})
	{
		if(tree[k].tag_min[x] != inf)
		{
			pushmin(k << 1 , x , tree[k].tag_min[x]);
			pushmin(k << 1 | 1 , x , tree[k].tag_min[x]);
		}
	}
	tree[k].tag_val[0] = tree[k].tag_val[1] = 0;
	tree[k].tag_min[0] = tree[k].tag_min[1] = inf;
	return;
}
void build(int k , int l , int r)
{
	tree[k].l = l;
	tree[k].r = r;
	tree[k].tag_val[0] = tree[k].tag_val[1] = 0;
	tree[k].tag_min[0] = tree[k].tag_min[1] = inf;
	if(l == r)
	{
		tree[k].the_max[0] = a[l] , tree[k].the_max[1] = b[l];
		tree[k].sec_max[0] = -inf , tree[k].sec_max[1] = -inf;
		tree[k].max_val[1][1] = a[l] + b[l];
		tree[k].max_val[0][1] = tree[k].max_val[1][0] = tree[k].max_val[0][0] = -inf;
		return;
	}
	int mid = l + (r - l) / 2;
	build(k << 1 , l , mid);
	build(k << 1 | 1 , mid + 1 , r);
	pushup(k);
	return;
}
int query_max(int k , int l , int r)
{
	if(l <= tree[k].l && tree[k].r <= r)
	{
		return max({tree[k].max_val[0][0] , tree[k].max_val[0][1] , tree[k].max_val[1][0] , tree[k].max_val[1][1]});
	}
	pushdown(k);
	int mid = tree[k].l + (tree[k].r - tree[k].l) / 2 , res = INT_MIN;
	if(l <= mid) res = max(res , query_max(k << 1 , l , r));
	if(r > mid) res = max(res , query_max(k << 1 | 1 , l , r));
	return res;
}
void update_min(int pos , int k , int l , int r , int c)
{
	if(c >= tree[k].the_max[pos]) return;
	if(l <= tree[k].l && tree[k].r <= r && c > tree[k].sec_max[pos])
	{
		pushmin(k , pos , c);
		return;
	}
	pushdown(k);
	int mid = tree[k].l + (tree[k].r - tree[k].l) / 2;
	if(l <= mid) update_min(pos , k << 1 , l , r , c);
	if(r > mid) update_min(pos , k << 1 | 1 , l , r , c);
	pushup(k);
	return;
}
void add(int pos , int k , int l , int r , int c)
{
	if(l <= tree[k].l && tree[k].r <= r)
	{
		pushsum(k , pos , c);
		return;
	}
	pushdown(k);
	int mid = tree[k].l + (tree[k].r - tree[k].l) / 2;
	if(l <= mid) add(pos , k << 1 , l , r , c);
	if(r > mid) add(pos , k << 1 | 1 , l , r , c);
	pushup(k);
	return;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> n >> m;
	for(int i = 1;i <= n;++ i)
	{
		cin >> a[i];
	}
	for(int i = 1;i <= n;++ i)
	{
		cin >> b[i];
	}
	build(1 , 1 , n);
	for(int i = 1;i <= m;++ i)
	{
		int opt = 0 , l = 0 , r = 0 , c = 0;
		cin >> opt;
		switch(opt)
		{
			case 1:{
				cin >> l >> r >> c;
				update_min(0 , 1 , l , r , c);
				break;
			}
			case 2:{
				cin >> l >> r >> c;
				update_min(1 , 1 , l , r , c);
				break;
			}
			case 3:{
				cin >> l >> r >> c;
				add(0 , 1 , l , r , c);
				break;
			}
			case 4:{
				cin >> l >> r >> c;
				add(1 , 1 , l , r , c);
				break;
			}
			case 5:{
				cin >> l >> r;
				cout << query_max(1 , l , r) << '\n';
				break;
			}
		}
	}
	cout << endl;
	return 0; 
}
/*

40 7
207034354 -246882716 418104869 16573831 4288587 -305140969 -448782876 -481742539 88128885 215113493 212491579 128282599 411892546 -332420438 231623436 -38249183 466152387 -269662562 -272492300 -183153310 195282267 329510247 -414629746 448170091 -206454920 53524444 -482959455 177919156 -436453310 207475873 -77247256 134493016 -314559848 175985713 -165087103 -79504499 198072451 453652620 212683079 -459590992 
-256820940 -113435747 -272254112 -49589201 -254487331 -136552134 136280867 -181854208 264961967 232722749 -193031034 302540000 365606572 -408348851 -387922201 -240668587 76886686 456514058 -205479941 -407122932 168767473 -486123015 120585240 236426037 -353951717 -455400474 -88500160 -21195848 -335876138 -389902909 32294556 -415007266 -388194896 294492344 18710218 132349706 -42967371 -267816193 381407299 -314765183
2 30 39 441717701
4 9 33 251153782
2 4 38 -390379152
3 3 28 -396007217
3 22 26 429478609
4 5 29 95002138
5 15 30
*/

U180387

2025/1/21 16:20