线段树模板二（区间加 + 区间乘，求区间加）

一时失言乱红尘 2022-09-12 05:55 196阅读 0赞

[https://www.luogu.com.cn/problem/P3373][https_www.luogu.com.cn_problem_P3373]

#include <iostream>
    using namespace std;
    #define ll long long 
    #define ls (i<<1)
    #define rs (i<<1|1)
    const int N = 1e5 + 10;
    
    struct Node{ 
    	int l, r;
    	ll data, add, mul;
    }tr[N<<2];
    
    ll input[N];
    
    int n, m, p;
    
    inline void pushup(int i)
    { 
    	tr[i].data = (tr[ls].data + tr[rs].data) % p;
    }
    
    inline void eval(Node &t, int add, int mul)
    { 
    	t.data = (t.data * mul + (ll)(t.r - t.l + 1)*add) % p;
    	// 重点理解
    	t.mul =  t.mul * mul % p;
    	t.add = (t.add * mul + add) % p;  
    }
    
    inline void pushdown(int i)
    { 
    	eval(tr[ls], tr[i].add, tr[i].mul);
    	eval(tr[rs], tr[i].add, tr[i].mul);
    	tr[i].add = 0, tr[i].mul = 1;
    }
    
    void build(int i, int l, int r)
    { 
    	if(l==r)
    	{ 
    		tr[i] = { l,r,input[r],0,1}; // add 0, mul 1
    		return ;
    	}
    	tr[i] = { l,r,0,0,1}; // data 0
    	int mid = (l + r) >> 1;
    	build(ls,l,mid); build(rs,mid+1,r);
    	pushup(i);
    }
    
    
    inline void change(int i, int l, int r, int mul, int add)
    { 
    	if(tr[i].r <= r and tr[i].l >= l)	// 在区间内
    		eval(tr[i],add,mul);
    	else{ 
    		pushdown(i);
    		//int mid = (tr[i].l + tr[i].r) >> 1;
    		if(l <= tr[ls].r) change(ls,l,r,mul,add);
    		if(r >= tr[rs].l) change(rs,l,r,mul,add);
    		pushup(i);
    	}
    }
    
    inline ll ask(int i, int l, int r)
    { 
    	if(tr[i].l >= l and tr[i].r <= r)
    		return tr[i].data;
    		
    	//if(tr[i].r < l or tr[i].l > r) return 0;
    	
    	pushdown(i);
    	
    	//int mid = (tr[i].l + tr[i].r) >> 1;
    	
    	ll res = 0;
    	if(l <= tr[ls].r) res += ask(ls,l,r);
    	res %= p;
    	if(r >= tr[rs].l) res += ask(rs,l,r);
    	res %= p;
    	return res;
    }
    
    int main()
    { 
    // cin >> n >> p >> m;
    	scanf("%d %d %d", &n, &m, &p);
    	
    	for(int i = 1; i <= n; i++) 
    		scanf("%lld", &input[i]);
    		
    	build(1, 1, n);
    	
    	while(m--)
    	{ 
    		int op, l, r, k;
    		scanf("%d %d %d", &op, &l, &r);
    		if(op == 1)
    		{ 
    			scanf("%d", &k);
    			change(1,l,r,k,0); 
    		}
    		else if (op == 2)
    		{ 
    			scanf("%d", &k);
    			change(1,l,r,1,k);
    		}
    		else printf("%lld\n",ask(1,l,r)%p);
    	}
    	return 0;
    }

[https_www.luogu.com.cn_problem_P3373]: https://www.luogu.com.cn/problem/P3373