线段树区间乘、加,范围求和,QWQ
原题
#include <bits/stdc++.h>
#define PII pair <int, int>
#define int long long
#define DB double
namespace FastIO
{
inline int read(int MOD, int &ret){
char ch = getchar();int ngtv = 1;
if(MOD == 0) {while(ch < '0' || ch > '9'){if(ch == '-') ngtv = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){ret = ret * 10 + (ch - '0');ch = getchar();}}
else {while(ch < '0' || ch > '9'){if(ch == '-') ngtv = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){ret = (ret * 10 % MOD + (ch - '0') % MOD) % MOD;ch = getchar();} }
return ret * ngtv;}
inline char cread(char &ch){while(ch == ' ' || ch == '\n' || ch == '\r' || ch == 0) ch = getchar();ch = getchar();return ch;}
}
using namespace FastIO;
using namespace std;
const int N = 4e5 + 10, M = 1e5 + 10;
int A[M], mod, n, q;
int opt, x, y, k;
struct Node
{
int sum, tag1, tag2;
// sum:区间和;tag1子节点未加的值;tag2:子节点未乘的值
int left, right;
// 左右节点(sum的范围)
}Tree[N];
void init_tree(int x, int left, int right)
{
Tree[x].left = left;
Tree[x].right = right;
if(left == right)
{
Tree[x].sum = A[left];
return ;
}
Tree[x].tag1 = 0;
Tree[x].tag2 = 1;
int mid = (left + right) >> 1;
init_tree(x * 2, left, mid);
init_tree(x * 2 + 1, mid + 1, right);
Tree[x].sum = (Tree[x * 2].sum + Tree[x * 2 + 1].sum) % mod;
}
void pushdown(int x)
{
int l = Tree[x].left, r = Tree[x].right;
int m = (l + r) >> 1;
Tree[x * 2].sum = (Tree[x * 2].sum * Tree[x].tag2 + (m - l + 1) * Tree[x].tag1) % mod;
Tree[x * 2 + 1].sum = (Tree[x * 2 + 1].sum * Tree[x].tag2 + (r - m) * Tree[x].tag1) % mod;
Tree[x * 2].tag1 = (Tree[x * 2].tag1 * Tree[x].tag2 + Tree[x].tag1) % mod;
Tree[x * 2 + 1].tag1 = (Tree[x * 2 + 1].tag1 * Tree[x].tag2 + Tree[x].tag1) % mod;
Tree[x * 2].tag2 = (Tree[x].tag2 * Tree[x * 2].tag2) % mod;
Tree[x * 2 + 1].tag2 = (Tree[x].tag2 * Tree[x * 2 + 1].tag2) % mod;
Tree[x].tag1 = 0;
Tree[x].tag2 = 1;
}
void add(int x, int l, int r, int ad)
{
if(l > Tree[x].right || Tree[x].left > r)
return ;
if(l <= Tree[x].left && Tree[x].right <= r)
{
Tree[x].tag1 = (Tree[x].tag1 + ad) % mod;
Tree[x].sum = (Tree[x].sum + (Tree[x].right - Tree[x].left + 1) * ad % mod) % mod;
return ;
}
pushdown(x);
add(x * 2, l , r, ad);
add(x * 2 + 1, l, r, ad);
Tree[x].sum = (Tree[x * 2].sum + Tree[x * 2 + 1].sum) % mod;
}
void ride(int x, int l, int r, int rid)
{
if(l > Tree[x].right || Tree[x].left > r)
return ;
if(l <= Tree[x].left && Tree[x].right <= r)
{
Tree[x].sum = (Tree[x].sum * rid) % mod;
Tree[x].tag1 = (Tree[x].tag1 * rid) % mod;
Tree[x].tag2 = (Tree[x].tag2 * rid) % mod;
return ;
}
pushdown(x);
ride(x * 2, l, r, rid);
ride(x * 2 + 1, l, r, rid);
Tree[x].sum = (Tree[x * 2].sum + Tree[x * 2 + 1].sum) % mod;
}
int sum(int x, int l, int r)
{
if(l > Tree[x].right || Tree[x].left > r)
return 0;
if(l <= Tree[x].left && Tree[x].right <= r)
return Tree[x].sum;
pushdown(x);
return (sum(x * 2, l, r) + sum(x * 2 + 1, l, r)) % mod;
}
signed main()
{
read(0, n), read(0, q), read(0, mod);
for(int i = 1; i <= n; i ++ )
read(0, A[i]);
init_tree(1, 1, n);
// 创建一个线段树 √
for(; q; q -- )
{
scanf("%d", &opt);
if(opt == 1)
{
scanf("%d%d%d", &x, &y, &k);
ride(1, x, y, k);
}
if(opt == 2)
{
scanf("%d%d%d", &x, &y, &k);
add(1, x, y, k);
}
if(opt == 3)
{
scanf("%d%d", &x, &y);
k = sum(1, x, y);
printf("%lld\n", k);
}
}
return 0;
}
标签:ch,洛谷,tag1,tag2,原题,int,sum,Tree,P3373
From: https://www.cnblogs.com/Hu-yan-xin/p/18365609