同时做多种区间修改和区间查询
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<queue>
#define PI atan(1.0)*4
#define e 2.718281828
#define rp(rt,s,t) for (rt = (s); rt <= (t); rt++)
#define RP(rt,s,t) for (rt = (t); rt >= (s); rt--)
#define ll long long
#define ull unsigned long long
#define mst(a,b) memset(a,b,sizeof(a))
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
inline int read()
{
int a=0,b=1;
char val=getchar(); //读取用户键入缓存区的一个字符
while(val<'0'||val>'9')
{
if(val=='-')
b=-1;
val=getchar();
}
while(val>='0'&&val<='9')
{
a=(a<<3)+(a<<1)+val-'0';
val=getchar();
}
return a*b;
}
const int mod=10007;
const int N = 1e5+7;
struct node{
int l,r;
int lazy1,lazy2,lazy3; //对应三种操作的懒标记
int sum1,sum2,sum3; //维护一次方，二次方，三次方的值
}tree[N<<2];
void pushdown(int rt) //下传，最复杂的部分
{
if(tree[rt].l == tree[rt].r) return;
if(tree[rt].lazy3 != 0) //先处理有等号标记的情况
{
//直接初始化儿子加和乘两种情况的lazy标记
tree[rt<<1].lazy3 = tree[(rt<<1)|1].lazy3 = tree[rt].lazy3;
tree[rt<<1].lazy1 = tree[(rt<<1)|1].lazy1 = 0;
tree[rt<<1].lazy2 = tree[(rt<<1)|1].lazy2 = 1;
//更新左右儿子维护的值
tree[rt<<1].sum1 = (tree[rt<<1].r - tree[rt<<1].l + 1)*tree[rt<<1].lazy3%mod;
tree[rt<<1].sum2 = (tree[rt<<1].r - tree[rt<<1].l + 1)*tree[rt<<1].lazy3%mod*tree[rt<<1].lazy3%mod;
tree[rt<<1].sum3 = (tree[rt<<1].r - tree[rt<<1].l + 1)*tree[rt<<1].lazy3%mod*tree[rt<<1].lazy3%mod*tree[rt<<1].lazy3%mod;
tree[(rt<<1)|1].sum1 = (tree[(rt<<1)|1].r - tree[(rt<<1)|1].l + 1)*tree[(rt<<1)|1].lazy3%mod;
tree[(rt<<1)|1].sum2 = (tree[(rt<<1)|1].r - tree[(rt<<1)|1].l + 1)*tree[(rt<<1)|1].lazy3%mod*tree[(rt<<1)|1].lazy3%mod;
tree[(rt<<1)|1].sum3 = (tree[(rt<<1)|1].r - tree[(rt<<1)|1].l + 1)*tree[(rt<<1)|1].lazy3%mod*tree[(rt<<1)|1].lazy3%mod*tree[(rt<<1)|1].lazy3%mod;
//不要忘记清空标记
tree[rt].lazy3 = 0;
}
if(tree[rt].lazy1 != 0 || tree[rt].lazy2 != 0) //有加号标记或者乘号标记
{
//更新左儿子的两种标记
tree[rt<<1].lazy1 = ( tree[rt].lazy2*tree[rt<<1].lazy1%mod + tree[rt].lazy1 )%mod; //父节点乘标记乘以子节点的加标记 + 父节点加标记
tree[rt<<1].lazy2 = tree[rt<<1].lazy2*tree[rt].lazy2%mod; //父节点乘标记乘以子节点的乘标记
//更新左儿子的值
int sum1,sum2,sum3;
sum1 = (tree[rt<<1].sum1 * tree[rt].lazy2%mod + (tree[rt<<1].r - tree[rt<<1].l + 1)*tree[rt].lazy1%mod)%mod; //(父节点标记乘*子节点和+区间*父节点标记加)
sum2 = (tree[rt].lazy2 * tree[rt].lazy2 % mod * tree[rt<<1].sum2 % mod + 2*tree[rt].lazy1*tree[rt].lazy2%mod * tree[rt<<1].sum1%mod + (tree[rt<<1].r - tree[rt<<1].l + 1)*tree[rt].lazy1%mod*tree[rt].lazy1%mod)%mod; //父节点标记乘^2 * 子节点平方和 + 2父节点标记乘*父节点标记加*子节点和 + 区间*父节点标记加^2
sum3 = tree[rt].lazy2 * tree[rt].lazy2 % mod * tree[rt].lazy2 % mod * tree[rt<<1].sum3 % mod; //三次项展开
sum3 = (sum3 + 3*tree[rt].lazy2 % mod * tree[rt].lazy2 % mod * tree[rt].lazy1 % mod * tree[rt<<1].sum2) % mod;
sum3 = (sum3 + 3*tree[rt].lazy2 % mod * tree[rt].lazy1 % mod * tree[rt].lazy1 % mod * tree[rt<<1].sum1) % mod;
sum3 = (sum3 + (tree[rt<<1].r - tree[rt<<1].l + 1)*tree[rt].lazy1%mod * tree[rt].lazy1 % mod * tree[rt].lazy1 % mod) % mod;
tree[rt<<1].sum1 = sum1;
tree[rt<<1].sum2 = sum2;
tree[rt<<1].sum3 = sum3;
//更新右儿子的两种标记
tree[(rt<<1)|1].lazy1 = ( tree[rt].lazy2*tree[(rt<<1)|1].lazy1%mod + tree[rt].lazy1 )%mod;
tree[(rt<<1)|1].lazy2 = tree[(rt<<1)|1].lazy2 * tree[rt].lazy2 % mod;
//更新右儿子的值
sum1 = (tree[(rt<<1)|1].sum1*tree[rt].lazy2%mod + (tree[(rt<<1)|1].r - tree[(rt<<1)|1].l + 1)*tree[rt].lazy1%mod)%mod;
sum2 = (tree[rt].lazy2 * tree[rt].lazy2 % mod * tree[(rt<<1)|1].sum2 % mod + 2*tree[rt].lazy1*tree[rt].lazy2%mod * tree[(rt<<1)|1].sum1%mod + (tree[(rt<<1)|1].r - tree[(rt<<1)|1].l + 1)*tree[rt].lazy1%mod*tree[rt].lazy1%mod)%mod; //
sum3 = tree[rt].lazy2 * tree[rt].lazy2 % mod * tree[rt].lazy2 % mod * tree[(rt<<1)|1].sum3 % mod;
sum3 = (sum3 + 3*tree[rt].lazy2 % mod * tree[rt].lazy2 % mod * tree[rt].lazy1 % mod * tree[(rt<<1)|1].sum2) % mod;
sum3 = (sum3 + 3*tree[rt].lazy2 % mod * tree[rt].lazy1 % mod * tree[rt].lazy1 % mod * tree[(rt<<1)|1].sum1) % mod;
sum3 = (sum3 + (tree[(rt<<1)|1].r - tree[(rt<<1)|1].l + 1)*tree[rt].lazy1%mod * tree[rt].lazy1 % mod * tree[rt].lazy1 % mod) % mod;
tree[(rt<<1)|1].sum1 = sum1;
tree[(rt<<1)|1].sum2 = sum2;
tree[(rt<<1)|1].sum3 = sum3;
tree[rt].lazy1 = 0;
tree[rt].lazy2 = 1;
}
}
void pushup(int rt){ //上传根据子节点信息更新父节点
if(tree[rt].l==tree[rt].r) return ; //叶子节点返回
tree[rt].sum1=(tree[rt<<1].sum1+tree[rt<<1|1].sum1)%mod;
tree[rt].sum2=(tree[rt<<1].sum2+tree[rt<<1|1].sum2)%mod;
tree[rt].sum3=(tree[rt<<1].sum3+tree[rt<<1|1].sum3)%mod;
}
void build(int l,int r,int rt){ //左右区间，编号
tree[rt].l=l,tree[rt].r=r;
tree[rt].lazy1=tree[rt].lazy3=0; //追加,赋值
tree[rt].lazy2=1; //系数
tree[rt].sum1=tree[rt].sum2=tree[rt].sum3=0; //节点信息的初始化
int m=(l+r)>>1;
if(l==r) return ;
build(lson);
build(rson);
}
void update(int rt,int L,int R,int opt,int val){
if(L==tree[rt].l&&R==tree[rt].r){ //全覆盖
val%=mod;
if(opt==1){ //加
tree[rt].lazy1 += val;
tree[rt].lazy1 %= mod;
tree[rt].sum3 = (tree[rt].sum3 + 3*tree[rt].sum2%mod*val%mod + 3*tree[rt].sum1%mod*val%mod*val%mod + (tree[rt].r - tree[rt].l + 1)*val%mod*val%mod*val%mod)%mod; //立方和：(x + a)^3 = x^3 + 3ba^2 + 3ab^2 + b^3
tree[rt].sum2 = (tree[rt].sum2 + 2*tree[rt].sum1%mod*val%mod + (tree[rt].r - tree[rt].l + 1)*val%mod*val%mod)%mod; //平方和：(x + a)^2 = x^2 + 2ax + a^2
tree[rt].sum1 = (tree[rt].sum1 + (tree[rt].r - tree[rt].l + 1)*val%mod)%mod; //求和：x + a
}
else if(opt==2){ //乘
tree[rt].lazy1 = tree[rt].lazy1*val%mod;
tree[rt].lazy2 = tree[rt].lazy2*val%mod;
tree[rt].sum1 = tree[rt].sum1*val%mod;
tree[rt].sum2 = tree[rt].sum2*val%mod*val%mod;
tree[rt].sum3 = tree[rt].sum3*val%mod*val%mod*val%mod;
}
else{ //赋值
tree[rt].lazy1 = 0;
tree[rt].lazy2 = 1;
tree[rt].lazy3 = val%mod; //赋值标记
tree[rt].sum1 = val*(tree[rt].r - tree[rt].l + 1)%mod;
tree[rt].sum2 = val*(tree[rt].r - tree[rt].l + 1)%mod*val%mod;
tree[rt].sum3 = val*(tree[rt].r - tree[rt].l + 1)%mod*val%mod*val%mod;
}
return ;
}
pushdown(rt);
int m=(tree[rt].l+tree[rt].r)>>1;
if(R<=m) update(rt<<1,L,R,opt,val); //剪枝：未被覆盖跳过
else if(m<L) update(rt<<1|1,L,R,opt,val);
else{
update(rt<<1,L,m,opt,val); //左儿子
update(rt<<1|1,m+1,R,opt,val); //右儿子
}
pushup(rt);
}
int query(int rt,int L,int R,int p){
if(L==tree[rt].l&&R==tree[rt].r){ //覆盖全区间输出区间和
if(p==1) return tree[rt].sum1;
else if(p==2) return tree[rt].sum2;
else return tree[rt].sum3;
}
pushdown(rt);
int m=(tree[rt].l+tree[rt].r)>>1;
if(R<=m) return query(rt<<1,L,R,p);
else if(m<L) return query(rt<<1|1,L,R,p);
else return (query(rt<<1,L,m,p)+query(rt<<1|1,m+1,R,p))%mod;
}
int main(){
int n,m;
while(~scanf("%d%d",&n,&m)){ //数列长度，操作次数
if(!n&&!m) break;
build(1,n,1); //建树
while(m--){
int opt = read(), x = read(), y = read(), val = read();
if(opt==4) printf("%d\n",query(1,x,y,val));
else update(1,x,y,opt,val);
}
}
return 0;
}
笔记：这个头文件挺全的，包括Π和自然数e，三个lazy标记分别是加法运算，乘法运算与重新赋值，三个sum分别是求和，求平方和与立方和。修改完父节点时更新子节点，修改求和里的平方和与立方和用的是二项式与三项式的展开
版权声明：
本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。本文链接：https://blog.csdn.net/qq_43472263/article/details/103597326