P2023 [AHOI2009]维护序列题解（线段树）

题目链接

P2023 [AHOI2009]维护序列

解题思路

线段树板子。不难，但是...有坑。坑有多深？一页\(WA\)。

由于乘法可能乘\(k=0\)，我这种做法可能会使结果产生负数。于是就有了这篇题解。

（详情见代码注释）

AC代码

#include<stdio.h>

#define min(a,b) (a>b?b:a)

#define max(a,b) (a>b?a:b)

typedef long long ll;

int n,m;

ll mod,k,a[500010];

struct Tree{

	int left,right;

	ll data,lazy,mul;

}tree[2000010];

void build(int p,int left,int right){

	tree[p].left=left;

	tree[p].right=right;

	tree[p].mul=1;

	if(left==right){tree[p].data=a[left];return;}

	build(p<<1,left,(left+right)>>1);

	build(p<<1|1,((left+right)>>1)+1,right);

	tree[p].data=(tree[p<<1].data+tree[p<<1|1].data)%mod;

}

void pushdown(int p){

	ll mul=tree[p].mul,lazy=tree[p].lazy;

	tree[p<<1].lazy*=mul;

	tree[p<<1].lazy+=lazy;tree[p<<1].lazy%=mod;

	tree[p<<1].mul*=mul;tree[p<<1].mul%=mod;

	tree[p<<1|1].lazy*=mul;

	tree[p<<1|1].lazy+=lazy;tree[p<<1|1].lazy%=mod;

	tree[p<<1|1].mul*=mul;tree[p<<1|1].mul%=mod;

	tree[p].data*=tree[p].mul;

	tree[p].data+=(tree[p].right-tree[p].left+1)*tree[p].lazy;

	tree[p].data%=mod;

	tree[p].lazy=0;tree[p].mul=1;

}

void add(int left,int right,ll k,int p){

	int l=tree[p].left,r=tree[p].right;

	if(l>right||r<left||p>4*n)return;

	pushdown(p);

	if(l>=left&&r<=right){

		tree[p].lazy+=k;

		tree[p].lazy%=mod;

		return;

	}

	tree[p].data+=k*(min(right,r)-max(left,l)+1);

	tree[p].data%=mod;

	add(left,right,k,p<<1);

	add(left,right,k,p<<1|1);

}

ll multy(int left,int right,ll k,int p){

	int l=tree[p].left,r=tree[p].right;

	if(l>right||r<left||p>4*n)return 0;

	pushdown(p);

	if(l>=left&&r<=right){

		ll temp=tree[p].data*tree[p].mul+tree[p].lazy*(r-l+1);

		tree[p].lazy*=k;tree[p].lazy%=mod;

		tree[p].mul*=k;tree[p].mul%=mod;

		return ((k-1)*temp%mod+mod)%mod;//非常重要！！！！！！

	}

	ll temp=multy(left,right,k,p<<1)+multy(left,right,k,p<<1|1);

	tree[p].data+=temp;

	tree[p].data=;

	return temp;

}

ll query(int left,int right,int p){

	int l=tree[p].left,r=tree[p].right;

	if(l>right||r<left||p>4*n)return 0;

	pushdown(p);

	if(l>=left&&r<=right)return tree[p].data;

	return query(left,right,p<<1)+query(left,right,p<<1|1);

}

int main(){

	int s,x,y,i;

	scanf("%d%lld",&n,&mod);

	for(i=1;i<=n;i++)scanf("%lld",&a[i]);

	build(1,1,n);

	scanf("%d",&m);

	while(m--){

		scanf("%d%d%d",&s,&x,&y);

		if(s-3){

			scanf("%lld",&k);

			if(s-1)add(x,y,k,1);

			else multy(x,y,k,1);

		}else printf("%lld\n",query(x,y,1)%mod);

	}

	return 0;

}

巴特西

P2023 [AHOI2009]维护序列题解（线段树）

题目链接

解题思路

AC代码

最新文章

热门文章

巴特西

P2023 [AHOI2009]维护序列 题解（线段树）

题目链接

解题思路

AC代码

最新文章

热门文章

P2023 [AHOI2009]维护序列题解（线段树）