Bzoj1798 Ahoi2009行星序列 双标记线段树

本来看见这个题第一反应是好水啊。。。

后来仔细想想好难啊因为乘法和加法的顺序是不能变的。。。

后来仔细想想才反应过来只需要双标记就可以了

这算是线段树双标记的经典题目了吧，对理解线段树的标记以及标记的下传有着很大的作用

两个标记加和乘

如果ax+b要乘一个数c就变成acx+bc

一直维护就好了

我对标记的理解是，当前节点的标记只是用于下穿才用的，换句话说，就是说当前节点的值已经算完了，标记的唯一作用就是下穿

理解好down函数！

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define MAX 100009
#define ll long long

using namespace std;

int n,m,mod,l[4*MAX],r[4*MAX];
ll he[4*MAX],add[4*MAX],mul[4*MAX];
int a[MAX];

void build(int x,int la,int ra)
{
	l[x]=la;
	r[x]=ra;
	add[x]=0;
	mul[x]=1;
	if(la==ra)
	{
		he[x]=a[la]%mod;
		return;
	}
	int mid=(la+ra)>>1;
	build(2*x,la,mid);
	build(2*x+1,mid+1,ra);
	he[x]=(he[2*x]+he[2*x+1])%mod;
	return;
}

void down(int x)
{
	if(mul[x]==1&&add[x]==0)
		return;
	int mid=(l[x]+r[x])>>1;
	mul[2*x]=(mul[2*x]*mul[x])%mod;
	mul[2*x+1]=(mul[2*x+1]*mul[x])%mod;
	add[2*x]=(add[2*x]*mul[x]+add[x])%mod;
	add[2*x+1]=(add[2*x+1]*mul[x]+add[x])%mod;
	he[2*x]=(he[2*x]*mul[x]+add[x]*(r[2*x]-l[2*x]+1))%mod;
	he[2*x+1]=(he[2*x+1]*mul[x]+(r[2*x+1]-l[2*x+1]+1)*add[x])%mod;
	mul[x]=1;
	add[x]=0;
}

void multiply(int x,int la,int ra,int num)
{
	if(l[x]>ra||r[x]<la)
		return;
	if(la<=l[x]&&r[x]<=ra)
	{
		mul[x]=(mul[x]*num)%mod;
		add[x]=(add[x]*num)%mod;
		he[x]=(he[x]*num)%mod;
		return;
	}
	if(l[x]==r[x])
		return;
	down(x);
	multiply(2*x,la,ra,num);
	multiply(2*x+1,la,ra,num);
	he[x]=(he[2*x]+he[2*x+1])%mod;
}

void Add(int x,int la,int ra,int num)
{
	if(l[x]>ra||r[x]<la)
		return;
	if(la<=l[x]&&r[x]<=ra)
	{
		add[x]=(add[x]+num)%mod;
		he[x]=(he[x]+(r[x]-l[x]+1)*num)%mod;
		return;
	}
	if(l[x]==r[x])
		return;
	down(x);
	Add(2*x,la,ra,num);
	Add(2*x+1,la,ra,num);
	he[x]=(he[2*x]+he[2*x+1])%mod;
	return;
}

long long ask(int x,int la,int ra)
{
	if(l[x]>ra||r[x]<la)
		return 0;
	if(la<=l[x]&&r[x]<=ra)
		return he[x]%mod;
	if(l[x]==r[x])
		return 0;
	down(x);
	return (ask(2*x,la,ra)+ask(2*x+1,la,ra))%mod;
}

int main()
{
	scanf("%d%d",&n,&mod);
	rep(i,1,n)
		scanf("%d",&a[i]);
	build(1,1,n);
	scanf("%d",&m);
	while(m--)
	{
		int control,a1,a2,a3;
		scanf("%d",&control);
		if(control==1)
		{
			scanf("%d%d%d",&a1,&a2,&a3),multiply(1,a1,a2,a3);
		}
		else
			if(control==2)
				scanf("%d%d%d",&a1,&a2,&a3),Add(1,a1,a2,a3);
			else
				scanf("%d%d",&a1,&a2),printf("%lld\n",ask(1,a1,a2)%mod);
	}
	return 0;
}

Bzoj1798 Ahoi2009行星序列 双标记线段树,布布扣,bubuko.com

Bzoj1798 Ahoi2009行星序列 双标记线段树

原文：http://blog.csdn.net/wbysr/article/details/22896779