西部虚拟主机网站后台不能访问,wordpress自定义登录页,工长网站开发,怎么把网址做成网页链接【模板】线段树 2
题目描述
如题#xff0c;已知一个数列#xff0c;你需要进行下面三种操作#xff1a;
将某区间每一个数乘上 x x x#xff1b;将某区间每一个数加上 x x x#xff1b;求出某区间每一个数的和。
输入格式
第一行包含三个整数 n , q , m n,q,m n,…【模板】线段树 2
题目描述
如题已知一个数列你需要进行下面三种操作
将某区间每一个数乘上 x x x将某区间每一个数加上 x x x求出某区间每一个数的和。
输入格式
第一行包含三个整数 n , q , m n,q,m n,q,m分别表示该数列数字的个数、操作的总个数和模数。
第二行包含 n n n 个用空格分隔的整数其中第 i i i 个数字表示数列第 i i i 项的初始值。
接下来 q q q 行每行包含若干个整数表示一个操作具体如下
操作 1 1 1 格式1 x y k 含义将区间 [ x , y ] [x,y] [x,y] 内每个数乘上 k k k
操作 2 2 2 格式2 x y k 含义将区间 [ x , y ] [x,y] [x,y] 内每个数加上 k k k
操作 3 3 3 格式3 x y 含义输出区间 [ x , y ] [x,y] [x,y] 内每个数的和对 m m m 取模所得的结果
输出格式
输出包含若干行整数即为所有操作 3 3 3 的结果。
样例 #1
样例输入 #1
5 5 38
1 5 4 2 3
2 1 4 1
3 2 5
1 2 4 2
2 3 5 5
3 1 4样例输出 #1
17
2提示
【数据范围】
对于 30 % 30\% 30% 的数据 n ≤ 8 n \le 8 n≤8 q ≤ 10 q \le 10 q≤10。 对于 70 % 70\% 70% 的数据$n \le 10^3 q \le 10^4$。 对于 100 % 100\% 100% 的数据 1 ≤ n ≤ 1 0 5 1 \le n \le 10^5 1≤n≤105 1 ≤ q ≤ 1 0 5 1 \le q \le 10^5 1≤q≤105。
除样例外 m 571373 m 571373 m571373。
数据已经过加强 _
样例说明 故输出应为 17 17 17、 2 2 2 40 m o d 38 2 40 \bmod 38 2 40mod382。
大致思路
线段树模板不过多解释 建树
首先线段树是二叉树因此具有二叉树的性质其左儿子节点与右儿子节点是固定的具体实现如下其中 l c ( x ) lc(x) lc(x)为左儿子 r c ( x ) rc(x) rc(x)为右儿子对应2n与21
#define lc(x) (x1)
#define rc(x) ((x1)|1)其次线段树的建立为递归建立最底层的节点对应的就是 a [ 1... n ] a[1...n] a[1...n]
void build(int x,int l,int r){tag_add[x]0;tag_mul[x]1;if(lr){sm[x]a[l];return;}int mid(lr)1;build(lc(x),l,mid);build(rc(x),mid1,r);pushup(x);return;
}s m [ x ] s m [ l c ( x ) ] s m [ r c ( x ) ] sm[x]sm[lc(x)]sm[rc(x)] sm[x]sm[lc(x)]sm[rc(x)]通常会被单独写做一个函数pushup pushup
void pushup(int x){sm[x](sm[lc(x)]sm[rc(x)])%mod;
}区间修改与查询
单点修改与查询只需如同建树一样查找到节点修改并pushup或return即可不过多赘述。
对于区间修改我们需要用到 lazy_tag 对于一次修改操作我们先不全部进行修改当火烧眉毛不得不用到这个值时再进行修改对于一种运算使用一个tag[]数组实现。 此模板题有两种运算因此用 tag_add 与 tag_mul 分别记录
int sm[N2],a[N2],tag_add[N2],tag_mul[N2];cover 两种运算我们先乘后加对于乘法节点 x 对应的 sm[x] 就是一段区间的和根据乘法分配律我们直接 s m [ x ] ∗ m u l sm[x]*mul sm[x]∗mul 即可同样 tag_add也要乘mul已有的 tag_mul 根据乘法结合律直接 t a g . m u l [ x ] ∗ m u l tag.mul [ x ] * mul tag.mul[x]∗mul,记得最后取模
void cover(int x,int l,int r,int ad,int mul){sm[x]sm[x]*mul%mod;sm[x](r-l1)*ad%mod;sm[x]%mod;tag_mul[x]*mul;tag_mul[x]%mod;tag_add[x]*mul;tag_add[x]ad;tag_add[x]%mod;
}pushdown 实现 tag 下传配合cover使用分别下传到左儿子和右儿子之后清空父节点的 lazy_tag 。
void pushdown(int x,int l,int r){int mid(lr)1;cover(lc(x),l,mid,tag_add[x],tag_mul[x]);cover(rc(x),mid1,r,tag_add[x],tag_mul[x]);tag_add[x]0;tag_mul[x]1;
}update 关键部分实现区间加法与区间乘法同样配合 coverpushdown 使用。以下给出两种写法将注释掉的内容解开并将 if (Lmid)…两行注释即为第二种写法
void update(int x,int l,int r,int L,int R,int ad,int mul){
// if(rL||lR)return;if(lLRr){cover(x,l,r,ad,mul);//若已被完全包含进行一次计算return;}pushdown(x,l,r);//注意下传tagint mid(lr)1;if(Lmid)update(lc(x),l,mid,L,R,ad,mul);//下传左儿子if(Rmid) update(rc(x),mid1,r,L,R,ad,mul);//下传右儿子
// update(lc(x),l,mid,L,R,ad,mul);
// update(rc(x),mid1,r,L,R,ad,mul);pushup(x);
}query 关键部分 实现区间询问原理基本与 update 一致注意区间被完全包含后返回值与取模。同样给出三种写法将注释掉的内容解开并将 if (Lmid)…两行注释即为第二种写法
int query(int x,int l,int r,int L,int R){
// if(rL||lR)return 0;int res0;if(lLRr){return sm[x];}pushdown(x,l,r);int mid(lr)1;if(Lmid)res(query(lc(x),l,mid,L,R)%mod);if(Rmid) res(query(rc(x),mid1,r,L,R)%mod);
// res(query(lc(x),l,mid,L,R)%mod);
// res(query(rc(x),mid1,r,L,R)%mod);return res%mod;
}int query(int x,int l,int r,int L,int R){if(rL||lR)return 0;if(lLRr){return sm[x];}pushdown(x,l,r);int mid(lr)1;return (query(lc(x),l,mid,L,R)query(rc(x),mid1,r,L,R))%mod;
}真的快被线段树ex吐了
AC CODE
#includebits/stdc.h
using namespace std;
#define int long long int
const int N1e62233;
#define lc(x) (x1)
#define rc(x) ((x1)|1)
int n,m,mod;
int sm[N2],a[N2],tag_add[N2],tag_mul[N2];
void pushup(int x){sm[x](sm[lc(x)]sm[rc(x)])%mod;
}
void build(int x,int l,int r){tag_add[x]0;tag_mul[x]1;if(lr){sm[x]a[l];return;}int mid(lr)1;build(lc(x),l,mid);build(rc(x),mid1,r);pushup(x);return;
}
void cover(int x,int l,int r,int ad,int mul){sm[x]sm[x]*mul%mod;sm[x](r-l1)*ad%mod;sm[x]%mod;tag_mul[x]*mul;tag_mul[x]%mod;tag_add[x]*mul;tag_add[x]ad;tag_add[x]%mod;
}
void pushdown(int x,int l,int r){int mid(lr)1;cover(lc(x),l,mid,tag_add[x],tag_mul[x]);cover(rc(x),mid1,r,tag_add[x],tag_mul[x]);tag_add[x]0;tag_mul[x]1;
}
void update(int x,int l,int r,int L,int R,int ad,int mul){
// if(rL||lR)return;if(lLRr){cover(x,l,r,ad,mul);return;}pushdown(x,l,r);int mid(lr)1;if(Lmid)update(lc(x),l,mid,L,R,ad,mul);if(Rmid) update(rc(x),mid1,r,L,R,ad,mul);
// update(lc(x),l,mid,L,R,ad,mul);
// update(rc(x),mid1,r,L,R,ad,mul);pushup(x);
}
int query(int x,int l,int r,int L,int R){
// if(rL||lR)return 0;int res0;if(lLRr){return sm[x];}pushdown(x,l,r);int mid(lr)1;if(Lmid)res(query(lc(x),l,mid,L,R)%mod);if(Rmid) res(query(rc(x),mid1,r,L,R)%mod);
// res(query(lc(x),l,mid,L,R)%mod);
// res(query(rc(x),mid1,r,L,R)%mod);return res%mod;
}
signed main(){scanf(%lld %lld %lld,n,m,mod);for(int i1;in;i){scanf(%lld,a[i]);}build(1,1,n);while(m--){int op,xx,yy,kk;scanf(%lld,op);if(op1){scanf(%lld %lld %lld,xx,yy,kk);update(1,1,n,xx,yy,0,kk);}if(op2){scanf(%lld %lld %lld,xx,yy,kk);update(1,1,n,xx,yy,kk,1);}if(op3){scanf(%lld %lld,xx,yy);printf(%lld\n,query(1,1,n,xx,yy));}}return 0;
}附封面佐仓大法好
