1 条题解

  • 0
    @ 2024-10-25 15:36:23

    注意先下传乘法标记再下传加法标记

    注意运算过程中爆int

    AC code:

    #include<bits/stdc++.h>
    using namespace std;
    int n,q,mo;
    const int N=1e5+7;
    struct tree {
    	int l,r,mul,add,key;
    } t[N*4];
    int a[N];
    void update(const int p) {
    	t[p].key=1ll*(t[p*2].key+t[p*2+1].key)%mo;
    	return ;
    }
    void datedown(const int p) {
    	if(t[p].add!=0||t[p].add!=1){
        t[p*2].key=(1ll*t[p*2].key*t[p].mul%mo+1ll*t[p].add*(t[p*2].r-t[p*2].l+1)%mo)%mo;
    	t[p*2+1].key=(1ll*t[p*2+1].key*t[p].mul%mo+1ll*t[p].add*(t[p*2+1].r-t[p*2+1].l+1)%mo)%mo;
    
    	t[p*2].add=1ll*t[p*2].add*t[p].mul%mo;
    	t[p*2+1].add=1ll*t[p*2+1].add*t[p].mul%mo;
    
    	t[p*2].mul=1ll*t[p*2].mul*t[p].mul%mo;
    	t[p*2+1].mul=1ll*t[p*2+1].mul*t[p].mul%mo;
    
    	t[p].mul=1;
    
    	t[p*2].add+=1ll*t[p].add%mo;
    	t[p*2+1].add+=1ll*t[p].add%mo;
    
        t[p].add=0;}
        return ;
    }
    void build(int l,int r,int p) {
    	if(l==r) {
    		t[p].l=t[p].r=l;
    		t[p].key=a[l]%mo;
    		t[p].mul=1;
    		return ;
    	}
        t[p].l=l,t[p].r=r;
        t[p].mul=1;
        int mid=(l+r)/2;
    	build(l,mid,p*2),build(mid+1,r,p*2+1);
    	update(p);
    	return ;
    }
    void changea(int l,int r,int add,int p) {
    	if(r<t[p].l||t[p].r<l)return ;
    	if(l<=t[p].l&&t[p].r<=r) {
    		t[p].key=(t[p].key+1ll*add*(t[p].r-t[p].l+1)%mo)%mo;
    		t[p].add+=1ll*add%mo;
    		return ;
    	}
    	datedown(p);
    	int mid=(t[p].r+t[p].l)/2;
    	if(l<=mid)changea(l,r,add,p*2);
    	if(mid<r)changea(l,r,add,p*2+1);
    	update(p);
    	return ;
    }
    void changem(int l,int r,int mul,int p) {
    	if(r<t[p].l||t[p].r<l)return ;
    	if(l<=t[p].l&&t[p].r<=r) {
    		t[p].key=1ll*t[p].key*mul%mo;
    		t[p].add=1ll*t[p].add*mul%mo;
    		t[p].mul=1ll*t[p].mul*mul%mo;
    		return ;
    	}
    	datedown(p);
    	int mid=(t[p].r+t[p].l)/2;
    	if(l<=mid)changem(l,r,mul,p*2);
    	if(mid<r)changem(l,r,mul,p*2+1);
    	update(p);
    	return ;
    }
    int check(int l,int r,int p) {
    	if(r<t[p].l||t[p].r<l)return 0;
    	if(l<=t[p].l&&t[p].r<=r) {
    		return t[p].key%mo;
    	}
    	datedown(p);
    	return (1ll*check(l,r,p*2)%mo+1ll*check(l,r,p*2+1)%mo)%mo;
    }
    int main() {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    	cin>>n>>q>>mo;
    	for(int i=1; i<=n; i++)cin>>a[i];
    	build(1,n,1);
    	while(q--) {
    		int opt;
    		cin>>opt;
    		switch(opt) {
    			case 1: {
    				int L,R,mul;
    				cin>>L>>R>>mul;
    				changem(L,R,mul,1);
    				break;
    			}
    			case 2: {
    				int L,R,add;
    				cin>>L>>R>>add;
    				changea(L,R,add,1);
    				break;
    			}
    			default: {
    				int L,R,ans;
    				cin>>L>>R;
    				ans=1ll*check(L,R,1)%mo;
    				cout<<ans<<'\n';
    				break;
    			}
    		}
    	}
    	return 0;
    }
    
    
    • 1

    信息

    ID
    7403
    时间
    1000ms
    内存
    125MiB
    难度
    4
    标签
    递交数
    68
    已通过
    18
    上传者