P3373 【模板】线段树 2

题目

link

题解

线段树

考虑两个tag，mul与add

表示[l, mid] [mid + 1, r]这两个区间分别需要* mul + tag

下传标记的时候[l, mid] [mid + 1, r]这两个子区间的tag，mul tag直接*mul[u]，add tag要* mul[u] + tag[u]

锅

1.change最后返回前要pushup一下

2.下传的时候u要穿ls，rs（

3.不开longlong见祖宗

代码

#include<bits/stdc++.h>
const int N = 1e5 + 10;
int n;
using namespace std;
#define int long long
int a[N];
const int mod = 571373;

namespace Segmenttree
{
	#define ls (u << 1)
	#define rs ((u << 1) | 1)
	int tree[N << 2];
	int tagcheng[N << 2], tagjia[N << 2];
	void init()
	{
		for(int i = 1;i < 4 * n;i++)
			tagcheng[i] = 1, tagjia[i] = 0; 
	}
	void pushup(int u)
	{
		tree[u] = (tree[ls] + tree[rs]) % mod;
	}

	void build(int u, int l, int r)
	{
		if(l == r)
		{
			tree[u] = a[l];
			return;
		}
		int mid = (l + r) >> 1;
		build(ls, l, mid);
		build(rs, mid + 1, r);
		pushup(u);
	}

	void pushdown(int u, int l, int r)
	{
		int mid = (l + r) >> 1;
		//[l, mid]、[mid + 1, r] 
		tree[ls] = (tree[ls] * tagcheng[u] + tagjia[u] * (mid - l + 1)) % mod;
		tree[rs] = (tree[rs] * tagcheng[u] + tagjia[u] * (r - mid)) % mod;
		tagcheng[ls] = tagcheng[ls] * tagcheng[u] % mod;
		tagcheng[rs] = tagcheng[rs] * tagcheng[u] % mod;
		tagjia[ls] = (tagjia[ls] * tagcheng[u] + tagjia[u]) % mod; 
		tagjia[rs] = (tagjia[rs] * tagcheng[u] + tagjia[u]) % mod; 
		tagjia[u] = 0;
		tagcheng[u] = 1;
	}

	void change(int u, int l, int r, int L, int R, int val, int type)
	{
		if(L <= l && r <= R)
		{
//			cout << l << " " << r << " was included"<<endl;
			if(type == 0)
			{
				tree[u] = (tree[u] + val * (r - l + 1)) % mod;
				tagjia[u] = (tagjia[u] + val) % mod; 
			}
			else
			{
			
				tree[u] = tree[u] * val % mod;
				tagcheng[u] = tagcheng[u] * val % mod;
				tagjia[u] = tagjia[u] * val % mod;
//				if(l == 4 && r == 4) cout << u<<" "<< val << " " << type << "qaqaqaq"<< "  " << tree[u]  << " "<< endl; 
			}
			return;
		}
//		cout << l << " " << r << endl;
		pushdown(u, l, r);
		int mid = (l + r) >> 1;
		if(L <= mid) change(ls, l, mid, L, R, val, type);
		if(R > mid) change(rs, mid + 1, r, L, R, val, type);
		pushup(u);
	}

	int query(int u, int l, int r, int L, int R)
	{
		if(L <= l && r <= R)
		{
//			cout << "query : " << l << " " << r << "sum: " << tree[u] << "    " << u << endl;
			return tree[u];
		}
		int ans = 0;
		pushdown(u, l, r);
		int mid = (l + r) >> 1;
		if(L > r || R < l) return 0;
		if(L <= mid) ans = (ans + query(ls, l, mid, L, R)) % mod;
		if(R > mid) ans = (ans + query(rs, mid + 1, r, L, R)) % mod;
//		cout << "query : " << l << " " << r << "sum: " << ans << "    " << u << endl;
		return ans;
	}
}
signed main()
{
//	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int q, m;
	cin >> n >> q >> m;
	for(int i = 1;i <= n;i++)
		cin >> a[i];
	int opt;
	Segmenttree::init();
	Segmenttree::build(1, 1, n);
	while(q--)
	{
		int x, y, k;
		cin >> opt;
		if(opt == 1)
		{
			cin >> x >> y >> k;
			Segmenttree::change(1, 1, n, x, y, k, 1);
//			cout << "qwq" << Segmenttree::query(1, 1, n, 4, 4) << '\n';
		}
		else if(opt == 2)
		{
			cin >> x >> y >> k;
			Segmenttree::change(1, 1, n, x, y, k, 0);
//			cout << "qwq" << " " << Segmenttree::query(1, 1, n, x, y) << '\n';
		}
		else
		{
			cin >> x >> y;
			cout << Segmenttree::query(1, 1, n, x, y) << '\n';
		}
	}
	return 0;
}