线段树的区间加法与区间乘法

你的名字 2023-05-21 11:57 127阅读 0赞

## P3372 【模板】线段树 1 ##

题目描述  
如题，已知一个数列，你需要进行下面两种操作：

将某区间每一个数加上 kk。  
求出某区间每一个数的和。  
输入格式  
第一行包含两个整数 n, mn,m，分别表示该数列数字的个数和操作的总个数。

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

接下来 mm 行每行包含 33 或 44 个整数，表示一个操作，具体如下：

1 x y k：将区间 \[x, y\]\[x,y\] 内每个数加上 kk。  
2 x y：输出区间 \[x, y\]\[x,y\] 内每个数的和。  
输出格式  
输出包含若干行整数，即为所有操作 2 的结果。

输入输出样例  
输入 \#1 复制  
5 5  
1 5 4 2 3  
2 2 4  
1 2 3 2  
2 3 4  
1 1 5 1  
2 1 4  
输出 \#1 复制  
11  
8  
20

#include<iostream>
    #include<cstdio>
    #include<cstdio>
    using namespace std;
    typedef long long ll;
    struct node{ 
    	int l,r;
    	ll data,lz;
    }tree[4000010]; 
    ll a[4000010];
    void build(int l,int r,int now)
    { 
    	tree[now].l=l;tree[now].r=r;tree[now].lz=0;
    	if(l==r)
    	{ 
    		tree[now].data=a[l];return;
    	}
    	int mid=(l+r)>>1;
    	build(l,mid,now*2);
    	build(mid+1,r,now*2+1);
    	tree[now].data=tree[now*2].data+tree[now*2+1].data;
    }
    void pushdown(int x)
    { 
    	if(tree[x].lz)
    	{ 
    		tree[x*2].lz+=tree[x].lz;
    		tree[x*2+1].lz+=tree[x].lz;
    		int mid=(tree[x].l+tree[x].r)/2;
    		tree[x*2].data+=tree[x].lz*(mid-tree[x*2].l+1);
    		tree[x*2+1].data+=tree[x].lz*(tree[x*2+1].r-mid);
    		tree[x].lz=0;
    	}
    }
    //update三种情况：1.区间完全被包含 2.左儿子区间部分包含 3.右儿子区间部分包含 
    void update(int l,int r,int now,int k)
    { 
    	if(tree[now].l>=l&&tree[now].r<=r)
    	{ 
    		tree[now].data+=k*(tree[now].r-tree[now].l+1);//这一步注意一下
    		tree[now].lz+=k;//加一个懒标记 注意+= 
    		return; 
    	}
    	pushdown(now);
    	if(tree[now*2].r>=l)update(l,r,now*2,k);
    	if(tree[now*2+1].l<=r)update(l,r,now*2+1,k);
    	tree[now].data=tree[now*2].data+tree[now*2+1].data;
    }
    ll get_sum(int l,int r,int now)
    { 
    	if(tree[now].l>=l&&tree[now].r<=r)
    	{ 
    		return tree[now].data;
    	}
    	pushdown(now);
    	ll ans=0;
    	if(tree[now*2].r>=l)ans=ans+get_sum(l,r,now*2);
    	if(tree[now*2+1].l<=r)ans=ans+get_sum(l,r,now*2+1);
    	return ans;
    }
    int main()
    { 
    	int n,m,x,y,k,t;
    	scanf("%d%d",&n,&m);
    	for(int i=1;i<=n;i++)
    	scanf("%lld",&a[i]);
    	build(1,n,1);
    	while(m--)
    	{ 
    		scanf("%d%d%d",&t,&x,&y);
    		if(t==1)
    		{ 
    			scanf("%d",&k);update(x,y,1,k);
    		} 
    		else 
    		{ 
    			printf("%lld\n",get_sum(x,y,1));
    		}
    	}
    	return 0;
    }

## P3373 【模板】线段树 2 ##

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

将某区间每一个数乘上 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

#include<iostream>
    #include<cstdio>
    #define MAXN 1000001
    #define ll long long
    using namespace std;
    ll a[500010],tree[500010],tag1[500010],tag2[500010];
    int x,y,p;
    void build(int start,int end,int now)
    { 
    	tag2[now]=1;//乘法的tag初始化为1 
    	if(start==end){ 
    		tree[now]=a[start];
    	}
    	else{ 
    		int mid = (start+end)/2;
    		int l = now<<1;
    		int r= now<<1|1;
    		build(start,mid,l);build(mid+1,end,r);
    		tree[now]=(tree[l]+tree[r])%p;
    	}
    }
    //a是加法的参数 b是乘法的参数 
    void pushlazy(int l,int r,int now,ll a,ll b)
    { 
    	tag1[now]=(tag1[now]*b+a)%p;//import
    	tag2[now]=(tag2[now]*b)%p;
    	tree[now]=(tree[now]*b+(r-l+1)*a)%p;
    	//这里只是把当前的now更新了，now下面的节点的值没用更新 ，所以需要dow_lazy 
    }
    void dowlazy(int l,int r,int now)
    { 
    	int mid=(l + r) >> 1;
    	pushlazy(l,mid,now*2,tag1[now],tag2[now]);
    	pushlazy(mid+1,r,now*2+1,tag1[now],tag2[now]);
    	tag1[now]=0;tag2[now]=1;
    	return;
    } 
    void fun(int l,int r,int now,ll a,ll b)
    { 
    	if(x<=l&&r<=y)pushlazy(l,r,now,a,b);
    	else{ 
    		if(tag1[now]||tag2[now]!=1)dowlazy(l,r,now);
    		int mid = (l+r)/2;
    		if(x<=mid)fun(l,mid,now*2,a,b);
    		if(mid<y)fun(mid+1,r,now*2+1,a,b);
    		tree[now]=(tree[now<<1]+tree[now<<1|1])%p;
    	}
    }
    ll ask(int l,int r,int now){ 
    	if(x<=l&&y>=r)
    	return tree[now];
    	if(tag1[now]||tag2[now]!=1)dowlazy(l,r,now);
    	int mid   = (l+r)/2;
    	ll ans=0;
    	if(x<=mid)ans=(ans+ask(l,mid,now*2))%p;
    	if(mid<y)ans=(ans+ask(mid+1,r,now*2+1))%p;
    	return ans;
    }
    int main()
    { 
    	int n,m,k,flag;
    	cin>>n>>m>>p;
    	for(int i=1;i<=n;i++)
    	{ 
    		scanf("%lld",&a[i]);
    	}
    	build(1,n,1);
    	while(m--)
    	{ 
    		scanf("%d",&flag);
    		if(flag==1)
    		{ //乘 
    			scanf("%d%d%d",&x,&y,&k);
    			fun(1,n,1,0,k);
    		}
    		else if(flag==2)
    		{ //加 
    			scanf("%d%d%d",&x,&y,&k);
    			fun(1,n,1,k,1);
    		} 
    		else
    		{ 
    			scanf("%d%d",&x,&y);
    			printf("%lld\n",ask(1,n,1));
    		}
    	}
     }