题目大意：给出一个序列，和三种操作：1、将[a,b]中的数一齐加上一个数；2、将[a,b]中的数一齐乘上一个数；3、输出[a,b]中数的和模p的结果。
很显然需要用线段树维护。
以下是我的代码，如果有测试数据的话请不吝共享：
#include<stdio.h>
#define maxn 100007
#define L(x) (x<<1)
#define R(x) ((x<<1)+1)
typedef long long int64;
struct
{
long a,b;
int64 add,mul,sum;
bool cover;
}seg[maxn*3];
long n,p,m,r[maxn];
// Var
void build(long node,long x,long y)
{
long mid=(x+y)>>1;
seg[node].a=x;seg[node].b=y;
seg[node].add=0;seg[node].mul=1;
seg[node].cover=false;
if(x==y)
seg[node].sum=r[x]%p;
else if(x<y)
{
build(L(node),x,mid);
build(R(node),mid+1,y);
seg[node].sum=(seg[L(node)].sum+seg[R(node)].sum)%p;
}
}
void update(long node)
{
if(seg[node].cover)
{
seg[L(node)].sum=(seg[L(node)].sum*seg[node].mul%p+seg[node].add*(seg[L(node)].b-seg[L(node)].a+1)%p)%p;
seg[R(node)].sum=(seg[R(node)].sum*seg[node].mul%p+seg[node].add*(seg[R(node)].b-seg[R(node)].a+1)%p)%p;
seg[L(node)].mul*=seg[node].mul;seg[L(node)].mul%=p;
seg[R(node)].mul*=seg[node].mul;seg[R(node)].mul%=p;
seg[L(node)].add*=seg[node].mul;seg[L(node)].add%=p;
seg[R(node)].add*=seg[node].mul;seg[R(node)].add%=p;
seg[L(node)].add+=seg[node].add;seg[L(node)].add%=p;
seg[R(node)].add+=seg[node].add;seg[R(node)].add%=p;
seg[L(node)].cover=seg[R(node)].cover=true;
seg[node].add=0;seg[node].mul=1;
seg[node].cover=false;
}
}
void handle_1(long node,long x,long y,long mulc)
{
long a=seg[node].a,b=seg[node].b,mid=(a+b)>>1;
if(x<=a&&b<=y)
{
seg[node].mul*=mulc;seg[node].mul%=p;
seg[node].add*=mulc;seg[node].add%=p;
seg[node].sum=seg[node].sum*mulc%p;
seg[node].cover=true;
}
else
{
update(node);
if(mid>=x)
handle_1(L(node),x,y,mulc);
if(mid+1<=y)
handle_1(R(node),x,y,mulc);
seg[node].sum=(seg[L(node)].sum+seg[R(node)].sum)%p;
}
}
void handle_2(long node,long x,long y,long addc)
{
long a=seg[node].a,b=seg[node].b,mid=(a+b)>>1;
if(x<=a&&b<=y)
{
seg[node].add+=addc;seg[node].add%=p;
seg[node].sum=(seg[node].sum+addc*(seg[node].b-seg[node].a+1)%p)%p;
seg[node].cover=true;
}
else
{
update(node);
if(mid>=x)
handle_2(L(node),x,y,addc);
if(mid+1<=y)
handle_2(R(node),x,y,addc);
seg[node].sum=(seg[L(node)].sum+seg[R(node)].sum)%p;
}
}
int64 handle_3(long node,long x,long y)
{
long a=seg[node].a,b=seg[node].b,mid=(a+b)>>1;
int64 re=0;
if(x<=a&&b<=y)
re=seg[node].sum;
else
{
update(node);
if(mid>=x)
re=(re+handle_3(L(node),x,y))%p;
if(mid+1<=y)
re=(re+handle_3(R(node),x,y))%p;
seg[node].sum=(seg[L(node)].sum+seg[R(node)].sum)%p;
}
return re%p;// 为了安全多做一次mod运算
}
int main()
{
//*
freopen("seq.in","r",stdin);
freopen("seq.out","w",stdout);
//*/
scanf("%ld%ld",&n,&p);
for(long i=1;i<=n;i++) scanf("%ld",&r[i]);
build(1,1,n);
scanf("%ld",&m);
while(m--)
{
long cmd,t,g,c;
scanf("%ld",&cmd);
switch(cmd)
{
case 1:
scanf("%ld%ld%ld",&t,&g,&c);
c%=p;
handle_1(1,t,g,c);
break;
case 2:
scanf("%ld%ld%ld",&t,&g,&c);
c%=p;
handle_2(1,t,g,c);
break;
case 3:
scanf("%ld%ld",&t,&g);
printf("%I64d\n",handle_3(1,t,g));
}
}
return 0;
}
程序已AC。
posted on 2010-02-28 10:30
lee1r 阅读(558)
评论(2) 编辑 收藏 引用 所属分类:
题目分类：数据结构