求助:测了样例可以过 提交十个点全部WA了

回复帖子

@小渣青999 2020-02-14 19:56 回复
#include<iostream>
#include<cstdio>
using namespace std;
struct tree
{
    int l,r;
    long long pre,add,mul;
}t[400010];
int a[400010];
int q;
void build(int p,int l,int r)
{
    t[p].l=l;
    t[p].r=r;
    if(l==r) 
    {
        t[p].pre=a[l];
        t[p].pre%=q;
        return ;
    }
    int mid=l+r>>1;
    build(2*p,l,mid);
    build(2*p+1,mid+1,r);
    t[p].pre=t[p*2].pre+t[2*p+1].pre;
    t[p].pre%=q;
}

void spread(int p)
{
     if(t[p].add!=0)
     {
        t[2*p].pre+=t[p].add*(t[2*p].r-t[2*p].l+1);
        t[2*p+1].pre+=t[p].add*(t[2*p+1].r-t[2*p+1].l+1);
        t[2*p].pre%=q;
        t[2*p+1].pre%=q;
        t[2*p].add+=t[p].add;
        t[2*p+1].add+=t[p].add;
        t[p].add=0;
     }
     if(t[p].mul!=0)
     {
        t[2*p].pre*=t[p].mul;
        t[2*p+1].pre*=t[p].mul;
        t[2*p].pre%=q;
        t[2*p+1].pre%=q;
        t[2*p].mul+=t[p].mul;
        t[2*p+1].mul+=t[p].mul;
        t[p].mul=0;
     }
}

void chadd(int p,int x,int y,int z)
{
    if(x<=t[p].l&&t[p].r<=y) 
    {
        t[p].pre+=(long long) z*(t[p].r-t[p].l+1);
        t[p].pre%=q;
        t[p].add+=z;
        return ;
    }
    spread(p);
    int mid=t[p].l+t[p].r>>1;
    if(x<=mid) chadd(2*p,x,y,z);
    if(y>mid) chadd(2*p+1,x,y,z);
    t[p].pre=t[2*p].pre+t[2*p+1].pre;
    t[p].pre%=q;
}
void chmul(int p,int x,int y,int z)
{
    if(x<=t[p].l&&t[p].r<=y) 
    {
        t[p].pre*=z;
        t[p].pre%=q;
        t[p].mul+=z;
        return ;
    }
    spread(p);
    int mid=t[p].l+t[p].r>>1;
    if(x<=mid) chmul(2*p,x,y,z);
    if(y>mid) chmul(2*p+1,x,y,z);
    t[p].pre=t[2*p].pre+t[2*p+1].pre;
    t[p].pre%=q;
}
long long ask(int p,int x,int y)
{
    if(x<=t[p].l&&t[p].r<=y) return t[p].pre;
    spread(p);
    int mid=t[p].l+t[p].r>>1;
    long long ans=0;
    if(x<=mid) ans+=ask(2*p,x,y);
    if(y>mid)  ans+=ask(2*p+1,x,y);
    ans%=q;
    return ans;

}
int main()
{
    int n,m;
    scanf("%d%d%d",&n,&m,&q);
    int i,k,j;
    int x,d,b,c;
    for(i=1;i<=n;i++) scanf("%d",&a[i]);
    build(1,1,n);
    for(i=1;i<=m;i++)
    {
        scanf("%d",&x);
        if(x==1)
        {
            scanf("%d%d%d",&d,&b,&c);
            chmul(1,d,b,c);
        }
        else if(x==2)
        {
            scanf("%d%d%d",&d,&b,&c);
            chadd(1,d,b,c);
        }
        else
        {
            scanf("%d%d",&c,&b);
            printf("%lld\n",ask(1,c,b));
        }
    }
    return 0;
}

求助 测了样例可以过 提交十个点全部WA了 大佬帮帮找找问题在哪 多谢多谢了

@小渣青999 2020-02-14 22:04 回复 举报

@SSerxhs

#include<iostream>
#include<cstdio>
using namespace std;
struct tree
{
    int l,r;
    long long pre,add,mul;
}t[400010];
int a[400010];
int q;
void build(int p,int l,int r)
{
    t[p].l=l;
    t[p].r=r;
    if(l==r) 
    {
        t[p].pre=a[l];
        t[p].pre%=q;
        return ;
    }
    int mid=l+r>>1;
    build(2*p,l,mid);
    build(2*p+1,mid+1,r);
    t[p].pre=t[p*2].pre+t[2*p+1].pre;
    t[p].pre%=q;
    t[p].mul=1;
    t[p].add=0;
}

void spread(int p)
{
     if(t[p].add!=0)
     {
        t[2*p].pre+=t[p].add*(t[2*p].r-t[2*p].l+1);
        t[2*p+1].pre+=t[p].add*(t[2*p+1].r-t[2*p+1].l+1);
        t[2*p].add+=t[p].add;
        t[2*p+1].add+=t[p].add;
        t[p].add=0;
     }
     if(t[p].mul!=1)
     {
        t[2*p].pre*=t[p].mul;
        t[2*p+1].pre*=t[p].mul;
        t[2*p].mul*=t[p].mul;
        t[2*p+1].mul*=t[p].mul;
        t[p].mul=1;
     }
    t[2*p].pre%=q;
    t[2*p+1].pre%=q;
}

void chadd(int p,int x,int y,int z)
{
    if(x<=t[p].l&&t[p].r<=y) 
    {
        t[p].pre+=(long long) z*(t[p].r-t[p].l+1);
        t[p].pre%=q;
        t[p].add+=z;
        t[p].add%=q;
        return ;
    }
    spread(p);
    int mid=t[p].l+t[p].r>>1;
    if(x<=mid) chadd(2*p,x,y,z);
    if(y>mid) chadd(2*p+1,x,y,z);
    t[p].pre=t[2*p].pre+t[2*p+1].pre;
    t[p].pre%=q;
}
void chmul(int p,int x,int y,int z)
{
    if(x<=t[p].l&&t[p].r<=y) 
    {
        t[p].pre*=z;
        t[p].pre%=q;
        t[p].mul*=z;
        t[p].mul%=q;
        return ;
    }
    spread(p);
    int mid=t[p].l+t[p].r>>1;
    if(x<=mid) chmul(2*p,x,y,z);
    if(y>mid) chmul(2*p+1,x,y,z);
    t[p].pre=t[2*p].pre+t[2*p+1].pre;
    t[p].pre%=q;
}
long long ask(int p,int x,int y)
{
    if(x<=t[p].l&&t[p].r<=y) return t[p].pre;
    spread(p);
    int mid=t[p].l+t[p].r>>1;
    long long ans=0;
    if(x<=mid) ans+=ask(2*p,x,y);
    if(y>mid)  ans+=ask(2*p+1,x,y);
    ans%=q;
    return ans;

}
int main()
{
    int n,m;
    scanf("%d%d%d",&n,&m,&q);
    int i,k,j;
    int x,d,b,c;
    for(i=1;i<=n;i++) scanf("%d",&a[i]);
    build(1,1,n);
    for(i=1;i<=m;i++)
    {
        scanf("%d",&x);
        if(x==1)
        {
            scanf("%d%d%d",&d,&b,&c);
            chmul(1,d,b,c);
        }
        else if(x==2)
        {
            scanf("%d%d%d",&d,&b,&c);
            chadd(1,d,b,c);
        }
        else
        {
            scanf("%d%d",&c,&b);
            printf("%lld\n",ask(1,c,b));
        }
    }
    return 0;
}

请教一下 我修改了mul的部分 结果还是错误的 请问哪里还有问题

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。