題目大意：給出一個序列，和三種操作：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 閱讀(573)
評論(2) 編輯 收藏 引用 所屬分類:
題目分類：數據結構