洛谷 P3373 线段树模板题

    科技2025-06-04  32

    链接:https://www.luogu.com.cn/problem/P3373 题意:一个区间 三种操作 1 给lr范围内乘一个数 2 给lr范围内加一个数 3 询问lr范围内的和 啊这题真·做了一上午 啊这 还是自己太菜了 因为需要两个标记 需要考虑运算顺序的问题(是先加后乘还是先乘后加)(自己也没明白 题解都说是先乘后加) 但是需要另处理加法标记 下面剖析一下代码吧 首先build函数没什么说的

    void build(int k,int l,int r){ t[k].l=l,t[k].r=r,t[k].lazy1=1,t[k].lazy2=0; if(l==r){ t[k].sum=a[l]%mod; }else{ int mid=(l+r)>>1; build(k<<1,l,mid); build(k<<1|1,mid+1,r); pushup(k); } }

    然后是pushdown函数 注意先乘后加是sum 然后注意lazy1是乘 直接乘就完了 然后注意lazy2是加 要注意lazy2也要先乘后加!!!是孩子的lazy2*父亲的lazy1 + 父亲的lazy2(先乘后加) 最后父亲俩lazy初始化。

    void pushdown(int k){ t[k<<1].sum*=t[k].lazy1;t[k<<1].sum%=mod; t[k<<1|1].sum*=t[k].lazy1;t[k<<1|1].sum%=mod; t[k<<1].lazy1*=t[k].lazy1;t[k<<1].lazy1%=mod; t[k<<1|1].lazy1*=t[k].lazy1;t[k<<1|1].lazy1%=mod; t[k<<1].sum+=t[k].lazy2*(t[k<<1].r-t[k<<1].l+1);t[k<<1].sum%=mod; t[k<<1|1].sum+=t[k].lazy2*(t[k<<1|1].r-t[k<<1|1].l+1);t[k<<1|1].sum%=mod; t[k<<1].lazy2=t[k].lazy1*t[k<<1].lazy2+t[k].lazy2;t[k<<1].lazy2%=mod; t[k<<1|1].lazy2=t[k].lazy1*t[k<<1|1].lazy2+t[k].lazy2;t[k<<1|1].lazy2%=mod; t[k].lazy1=1; t[k].lazy2=0; }

    然后是乘的updata 要注意lazy2也要更新(当前的乘变了 加lazy也要变)

    void updata1(int k,int l,int r,int val){ if(l<=t[k].l&&t[k].r<=r){ t[k].sum*=val; t[k].sum%=mod; //if(t[k].l<t[k].r) { t[k].lazy1*=val; t[k].lazy1%=mod; t[k].lazy2*=val; t[k].lazy2%=mod; //} }else{ pushdown(k); int mid=(t[k].l+t[k].r)>>1; if(l<=mid) updata1(k<<1,l,r,val); if(mid<r) updata1(k<<1|1,l,r,val); pushup(k); } }

    改了好多次啊老是不对 感谢lc大佬帮看代码 and 这篇好好留着 要注意加乘顺序对lazy的影响 多个地方都需要修改lazy更改顺序!!!

    下面是AC代码

    #include<algorithm> #include<iostream> #include<cstdio> #include<cstring> #include<string> #include<cmath> #include<queue> #include<map> #include<set> #define ll long long #define inf 0x3f3f3f3f #define sd(a) scanf("%d",&a) #define sdd(a,b) scanf("%d%d",&a,&b) #define cl(a,b) memset(a,b,sizeof(a)) #define rep(i,a,n) for(int i=a;i<=n;i++) #define sddd(a,b,c) scanf("%d%d%d",&a,&b,&c) #define dbg() printf("aaa\n") using namespace std; const int maxn=1e5+10; int n,m,mod; ll a[maxn]; struct node{ int l,r; ll sum,lazy1,lazy2;//lazy1是乘 lazy2是加 }t[maxn<<2]; void pushup(int k){ t[k].sum=(t[k<<1].sum+t[k<<1|1].sum)%mod; } void pushdown(int k){ t[k<<1].sum*=t[k].lazy1;t[k<<1].sum%=mod; t[k<<1|1].sum*=t[k].lazy1;t[k<<1|1].sum%=mod; t[k<<1].lazy1*=t[k].lazy1;t[k<<1].lazy1%=mod; t[k<<1|1].lazy1*=t[k].lazy1;t[k<<1|1].lazy1%=mod; t[k<<1].sum+=t[k].lazy2*(t[k<<1].r-t[k<<1].l+1);t[k<<1].sum%=mod; t[k<<1|1].sum+=t[k].lazy2*(t[k<<1|1].r-t[k<<1|1].l+1);t[k<<1|1].sum%=mod; t[k<<1].lazy2=t[k].lazy1*t[k<<1].lazy2+t[k].lazy2;t[k<<1].lazy2%=mod; t[k<<1|1].lazy2=t[k].lazy1*t[k<<1|1].lazy2+t[k].lazy2;t[k<<1|1].lazy2%=mod; t[k].lazy1=1; t[k].lazy2=0; } void build(int k,int l,int r){ t[k].l=l,t[k].r=r,t[k].lazy1=1,t[k].lazy2=0; if(l==r){ t[k].sum=a[l]%mod; }else{ int mid=(l+r)>>1; build(k<<1,l,mid); build(k<<1|1,mid+1,r); pushup(k); } } void updata1(int k,int l,int r,int val){ if(l<=t[k].l&&t[k].r<=r){ t[k].sum*=val; t[k].sum%=mod; //if(t[k].l<t[k].r) { t[k].lazy1*=val; t[k].lazy1%=mod; t[k].lazy2*=val; t[k].lazy2%=mod; //} }else{ pushdown(k); int mid=(t[k].l+t[k].r)>>1; if(l<=mid) updata1(k<<1,l,r,val); if(mid<r) updata1(k<<1|1,l,r,val); pushup(k); } } void updata2(int k,int l,int r,int val){ if(l<=t[k].l&&t[k].r<=r){ t[k].sum+=(t[k].r-t[k].l+1)*val; t[k].sum%=mod; //if(t[k].l<t[k].r) { t[k].lazy2+=val; t[k].lazy2%=mod; //} }else{ pushdown(k); int mid=(t[k].l+t[k].r)>>1; if(l<=mid) updata2(k<<1,l,r,val); if(mid<r) updata2(k<<1|1,l,r,val); pushup(k); } } ll query(int k,int l,int r){ if(l<=t[k].l&&t[k].r<=r){ return t[k].sum%mod; }else{ pushdown(k); int mid=(t[k].l+t[k].r)>>1; ll ans=0; if(l<=mid) ans+=query(k<<1,l,r); ans%=mod; if(mid<r) ans+=query(k<<1|1,l,r); ans%=mod; return ans; } } int main(){ sddd(n,m,mod); rep(i,1,n){ scanf("%lld",&a[i]); } build(1,1,n); rep(i,1,m){ int op,l,r,val; sd(op); if(op==1){ sddd(l,r,val); updata1(1,l,r,val); }else if(op==2){ sddd(l,r,val); updata2(1,l,r,val); }else if(op==3){ sdd(l,r); ll ans=query(1,l,r)%mod; printf("%lld\n",ans); } } return 0; }

    题目描述 如题,已知一个数列,你需要进行下面三种操作:

    将某区间每一个数乘上 xx

    将某区间每一个数加上 xx

    求出某区间每一个数的和

    输入格式 第一行包含三个整数 n,m,pn,m,p,分别表示该数列数字的个数、操作的总个数和模数。

    第二行包含 nn 个用空格分隔的整数,其中第 ii 个数字表示数列第 ii 项的初始值。

    接下来 mm 行每行包含若干个整数,表示一个操作,具体如下:

    操作 11: 格式:1 x y k 含义:将区间 [x,y][x,y] 内每个数乘上 kk

    操作 22: 格式:2 x y k 含义:将区间 [x,y][x,y] 内每个数加上 kk

    操作 33: 格式:3 x y 含义:输出区间 [x,y][x,y] 内每个数的和对 pp 取模所得的结果

    输出格式 输出包含若干行整数,即为所有操作 33 的结果。

    输入输出样例 输入 #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% 的数据:n \le 8n≤8,m \le 10m≤10 对于 70%70% 的数据:n \le 10^3n≤10 3 ,m \le 10^4m≤10 4

    对于 100%100% 的数据:n \le 10^5n≤10 5 ,m \le 10^5m≤10 5

    除样例外,p = 571373p=571373

    Processed: 0.010, SQL: 8