首页 > 代码库 > [AHOI2009]维护序列

[AHOI2009]维护序列

2024-11-19 01:14:02   203人阅读

题目：BZOJ1798、洛谷P2023。

题目大意：有长为N的数列，设为a1,a2,…,aN 。有如下三种操作形式： (1)把数列中的一段数全部乘一个值; (2)把数列中的一段数全部加一个值; (3)询问数列中的一段数的和，由于答案可能很大，你只需输出这个数模P的值。

解题思路：此题很容易想到线段树来维护。对于加和乘的操作，打标记即可。注意开long long和勤奋取模！

C++ Code：

 

#include<cstdio>using namespace std;#define LL long longint n,p;struct node{	LL s,add,mul;}d[400052];int a[100051];void bt(int l,int r,int o){	if(l==r){		d[o].s=a[l];		d[o].add=0;		d[o].mul=1;		return;	}	int mid=l+r>>1;	bt(l,mid,o<<1);	bt(mid+1,r,o<<1|1);	d[o].s=(d[o<<1].s+d[o<<1|1].s)%p;	d[o].add=0;	d[o].mul=1;}inline void pushdown(int o,int l,int r){	d[o<<1].mul*=d[o].mul;	d[o<<1|1].mul*=d[o].mul;	d[o<<1].mul%=p;	d[o<<1|1].mul%=p;	d[o<<1].add*=d[o].mul;	d[o<<1].add+=d[o].add;	d[o<<1|1].add*=d[o].mul;	d[o<<1|1].add+=d[o].add;	d[o<<1].add%=p;	d[o<<1|1].add%=p;	int mid=(l+r)>>1;	d[o<<1].s=(d[o<<1].s*d[o].mul+d[o].add*(mid-l+1))%p;	d[o<<1|1].s=(d[o<<1|1].s*d[o].mul+d[o].add*(r-mid))%p;	d[o].mul=1;	d[o].add=0;}void cheng(int l,int r,int o,int L,int R,int c){	if(L<=l&&r<=R){		d[o].add*=c;		d[o].mul*=c;		d[o].s*=c;		d[o].s%=p;		d[o].add%=p;		d[o].mul%=p;		return;	}	pushdown(o,l,r);	int mid=l+r>>1;	if(L<=mid)cheng(l,mid,o<<1,L,R,c);	if(mid<R)cheng(mid+1,r,o<<1|1,L,R,c);	d[o].s=(d[o<<1].s+d[o<<1|1].s)%p;}void jia(int l,int r,int o,int L,int R,int c){	if(L<=l&&r<=R){		d[o].add+=c;		d[o].add%=p;		d[o].s+=c*(r-l+1);		d[o].s%=p;		return;	}	pushdown(o,l,r);	int mid=l+r>>1;	if(L<=mid)jia(l,mid,o<<1,L,R,c);	if(mid<R)jia(mid+1,r,o<<1|1,L,R,c);	d[o].s=(d[o<<1].s+d[o<<1|1].s)%p;}LL query(int l,int r,int o,int L,int R){	if(L<=l&&r<=R)	return d[o].s%p;	pushdown(o,l,r);	LL ans=0;	int mid=l+r>>1;	if(L<=mid)ans=query(l,mid,o<<1,L,R)%p;	if(mid<R)ans+=query(mid+1,r,o<<1|1,L,R)%p;	return ans%p;}int main(){	scanf("%d%d",&n,&p);	for(int i=1;i<=n;++i)scanf("%d",&a[i]);	bt(1,n,1);	int m;	scanf("%d",&m);	while(m--){		int k,l,r;		scanf("%d%d%d",&k,&l,&r);		if(k==1){			int x;			scanf("%d",&x);			cheng(1,n,1,l,r,x);		}else		if(k==2){			int x;			scanf("%d",&x);			jia(1,n,1,l,r,x);		}else		printf("%d\n",(int)query(1,n,1,l,r));	}	return 0;}

 

[AHOI2009]维护序列


联系
我们