求救大佬,刚学线段树,样例都出错
查看原帖
求救大佬,刚学线段树,样例都出错
196522
HuaJi_360楼主2020/8/14 12:50

rt,本人的代码手打的,样例过不了,看看题解也没查出不同,救救孩子QWQ

#include<bits/stdc++.h>
#define reg register ll
#define ll long long
using namespace std;
struct node{
    ll l,r,data,mul,add;
}tr[400005];
ll n,m,p,a[100005];
void build(ll l,ll r,ll id){
    tr[id].l=l;
    tr[id].r=r;
    tr[id].mul=1;
    if(l==r){
        tr[id].data=a[l]%p;
        return;
    }
    ll mid=(l+r)>>1;
    build(l,mid,id<<1);
    build(mid+1,r,id<<1|1);
    tr[id].data=(tr[id<<1].data+tr[id<<1|1].data)%p;
}
void push_down(ll id){
    ll mid=(tr[id].l+tr[id].r)>>1;
    tr[id<<1].data=(tr[id<<1].data*tr[id].mul+tr[id].add*(mid-tr[id].l+1))%p;
    tr[id<<1|1].data=(tr[id<<1|1].data*tr[id].mul+tr[id].add*(tr[id].r-mid))%p;

    tr[id<<1].mul=(tr[id<<1].mul*tr[id].mul)%p;
    tr[id<<1|1].mul=(tr[id<<1|1].mul*tr[id].mul)%p;

    tr[id<<1].add=(tr[id<<1].add*tr[id].mul+tr[id].add)%p;
    tr[id<<1|1].add=(tr[id<<1|1].add*tr[id].mul+tr[id].add)%p;

    tr[id].add=0;tr[id].mul=1;
}
void upd_add(ll id,ll l,ll r,ll k){
    if(tr[id].r<l||tr[id].l>r){return;}
    if(tr[id].r<=r&&tr[id].l>=l){
        tr[id].data=(tr[id].data+k*(tr[id].r-tr[id].l))%p;
        tr[id].add=(tr[id].add+k)%p;
        return;
    }
    push_down(id);
    upd_add(id<<1,l,r,k);
    upd_add(id<<1|1,l,r,k);
    tr[id].data=(tr[id<<1].data+tr[id<<1|1].data)%p;
}
void upd_mul(ll id,ll l,ll r,ll k){
    if(tr[id].r<l||tr[id].l>r){return;}
    if(tr[id].r<=r&&tr[id].l>=l){
        tr[id].data=(tr[id].data*k)%p;
        tr[id].mul=(tr[id].mul*k)%p;
        tr[id].add=(tr[id].add*k)%p;
        return;
    }
    push_down(id);
    upd_mul(id<<1,l,r,k);
    upd_mul(id<<1|1,l,r,k);
    tr[id].data=(tr[id<<1].data+tr[id<<1|1].data)%p;
}
ll query(ll id,ll l,ll r){
    if(tr[id].r<l||tr[id].l>r){return 0;}
    if(tr[id].r<=r&&tr[id].l>=l){
        return tr[id].data;
    }
    push_down(id);
    ll tot=0;
    tot=(tot+query(id<<1,l,r))%p;
    tot=(tot+query(id<<1|1,l,r))%p;
    return tot;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m>>p;
    for(reg i=1;i<=n;i++){
        cin>>a[i];
    }
    build(1,n,1);
    for(reg i=1;i<=m;i++){
        int type,l,r;
        cin>>type>>l>>r;
        if(type==1){
            int k;
            cin>>k;
            upd_mul(1,l,r,k);
        }else if(type==2){
            int k;
            cin>>k;
            upd_add(1,l,r,k);
        }else{
            cout<<query(1,l,r)%p<<endl;
        }
    }
    return 0;
}

2020/8/14 12:50
加载中...