求助,悬关
查看原帖
求助,悬关
944873
dxy19213987956楼主2023/10/8 13:10

第一份代码30分,但是当我把pushdown传参由传区间长度改为区间端点再在pushdown内操作却可以AC,这是为什么

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
long long a[N*4];
int n,q,m;
int op,x,y;
long long k;
struct node
{
    long long v;
    long long mul;
    long long add;
};
node tree[N*4];
void build(int p,int l,int r)
{
    tree[p].mul=1;
    tree[p].add=0;
    if(l==r){
        tree[p].v=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    tree[p].v=(tree[p*2].v+tree[p*2+1].v)%m;
}
void pushdown(int p,int tot)
{
    tree[p*2].mul=tree[p].mul*tree[p*2].mul%m;
    tree[p*2+1].mul=tree[p].mul*tree[p*2+1].mul%m;
    tree[p*2].v=(tree[p*2].v*tree[p].mul+tree[p].add*(tot-tot/2))%m;
    tree[p*2+1].v=(tree[p*2+1].v*tree[p].mul+tree[p].add*tot/2)%m;
    tree[p*2].add=(tree[p*2].add*tree[p].mul+tree[p].add)%m;
    tree[p*2+1].add=(tree[p*2+1].add*tree[p].mul+tree[p].add)%m;
    tree[p].add=0;
    tree[p].mul=1;
}
void mul(int p,int l,int r,int x,int y,long long k)
{
    if(x<=l&&r<=y){
        tree[p].v=tree[p].v*k%m;
        tree[p].mul=tree[p].mul*k%m;
        tree[p].add=tree[p].add*k%m;
        return;
    }
    pushdown(p,r-l+1);
    int mid=(l+r)/2;
    if(x<=mid)mul(p*2,l,mid,x,y,k);
    if(y>mid)mul(p*2+1,mid+1,r,x,y,k);
    tree[p].v=(tree[p*2].v+tree[p*2+1].v)%m;
}
void add(int p,int l,int r,int x,int y,long long k)
{
    if(x<=l&&r<=y){
        tree[p].add=(tree[p].add+k)%m;
        tree[p].v=(tree[p].v+k*(r-l+1))%m;
        return;
    }
    pushdown(p,r-l+1);
    int mid=(l+r)/2;
    if(x<=mid)add(p*2,l,mid,x,y,k);
    if(y>mid)add(p*2+1,mid+1,r,x,y,k);
    tree[p].v=(tree[p*2].v+tree[p*2+1].v)%m;
}
long long query(int p,int l,int r,int x,int y)
{
    if(x<=l&&r<=y)return tree[p].v;
    int mid=(l+r)/2;
    long long ans=0;
    pushdown(p,r-l+1);
    if(x<=mid)ans+=query(p*2,l,mid,x,y);
    if(y>mid)ans+=query(p*2+1,mid+1,r,x,y);
    return ans%m;
}
int main()
{
    scanf("%d %d %d",&n,&q,&m);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    build(1,1,n);
    while(q--){
        scanf("%d",&op);
        if(op==1){
            scanf("%d %d %lld",&x,&y,&k);
            mul(1,1,n,x,y,k);
        }
        else if(op==2){
            scanf("%d %d %lld",&x,&y,&k);
            add(1,1,n,x,y,k);
        }
        else{
            scanf("%d %d",&x,&y);
            printf("%lld\n",query(1,1,n,x,y));
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const signed N=1e5+5;
long long a[N*4];
int n,q,m;
int op,x,y;
long long k;
struct node
{
    long long v;
    long long mul;
    long long add;
};
node tree[N*4];
void build(int p,int l,int r)
{
    tree[p].mul=1;
    tree[p].add=0;
    if(l==r){
        tree[p].v=a[l]%m;
        return;
    }
    int mid=(l+r)/2;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    tree[p].v=(tree[p*2].v+tree[p*2+1].v)%m;
}
void pushdown(int p,int l,int r)
{
    int mid=(l+r)/2;
    tree[p*2].v=(tree[p*2].v*tree[p].mul+tree[p].add*(mid-l+1))%m;
    tree[p*2+1].v=(tree[p*2+1].v*tree[p].mul+tree[p].add*(r-mid))%m;
    tree[p*2].mul=(tree[p].mul*tree[p*2].mul)%m;
    tree[p*2+1].mul=(tree[p].mul*tree[p*2+1].mul)%m;
    tree[p*2].add=(tree[p*2].add*tree[p].mul+tree[p].add)%m;
    tree[p*2+1].add=(tree[p*2+1].add*tree[p].mul+tree[p].add)%m;
    tree[p].add=0;
    tree[p].mul=1;
}
void mul(int p,int l,int r,int x,int y,long long k)
{
    if(x<=l&&r<=y){
        tree[p].v=(tree[p].v*k)%m;
        tree[p].mul=(tree[p].mul*k)%m;
        tree[p].add=(tree[p].add*k)%m;
        return;
    }
    pushdown(p,l,r);
    int mid=(l+r)/2;
    if(x<=mid)mul(p*2,l,mid,x,y,k);
    if(y>mid)mul(p*2+1,mid+1,r,x,y,k);
    tree[p].v=(tree[p*2].v+tree[p*2+1].v)%m;
}
void add(int p,int l,int r,int x,int y,long long k)
{
    if(x<=l&&r<=y){
        tree[p].add=(tree[p].add+k)%m;
        tree[p].v=(tree[p].v+k*(r-l+1))%m;
        return;
    }
    pushdown(p,l,r);
    int mid=(l+r)/2;
    if(x<=mid)add(p*2,l,mid,x,y,k);
    if(y>mid)add(p*2+1,mid+1,r,x,y,k);
    tree[p].v=(tree[p*2].v+tree[p*2+1].v)%m;
}
long long query(int p,int l,int r,int x,int y)
{
    if(x<=l&&r<=y)return tree[p].v;
    int mid=(l+r)/2;
    long long ans=0;
    pushdown(p,l,r);
    if(x<=mid)ans=(ans+query(p*2,l,mid,x,y))%m;
    if(y>mid)ans=(ans+query(p*2+1,mid+1,r,x,y))%m;
    return ans%m;
}
signed main()
{
    freopen("1.in","r",stdin);
    freopen("ans.out","w",stdout);
    scanf("%d %d %d",&n,&q,&m);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    build(1,1,n);
    while(q--){
        scanf("%d",&op);
        if(op==1){
            scanf("%d %d %lld",&x,&y,&k);
            mul(1,1,n,x,y,k);
        }
        else if(op==2){
            scanf("%d %d %lld",&x,&y,&k);
            add(1,1,n,x,y,k);
        }
        else{
            scanf("%d %d",&x,&y);
            printf("%lld\n",query(1,1,n,x,y));
        }
    }
    return 0;
}


2023/10/8 13:10
加载中...