厦门大学程序设计大赛月赛 D.小C的棋王之路

题目大意:给定一个有 个元素序列,有四种操作和一种询问.

• 1 L R K 让区间 的元素加上 .
• 2 L R K 让区间 的元素乘上 .
• 3 L R K 让区间 的元素变为 .
• 4 L R K 在末尾位置添加一个元素值为 .
• 5 L R 询问区间 元素的值的和.

分析: 赛中分析，前四个操作都是线段树的操作，后面看到操作四，以为不能写线段树，直接码分块，后面T了三十发直接自闭.

赛后分析：显然我们可以直接建n+m大小的线段树，然后直接操作.(惊了
推标记直接用两个mul 和add 维护乘法和加法,这种操作就是码板子.

#include<bits/stdc++.h>
#define ls cur<<1
#define rs cur<<1|1

using namespace std;

const int maxn=2e5+10;

typedef long long ll;
ll  mod; 


struct node1{
    int l;
    int r;
    ll sum1,mul,lazy;
}t[maxn<<2];

ll a[maxn];

void pushup( int cur ) //ok
{
    t[cur].sum1=( t[ls].sum1+t[rs].sum1 )%mod;
}


void cal( int cur,ll x,ll y )
{
    ll len=1ll*( t[cur].r-t[cur].l+1 );
    t[cur].sum1=( x*t[cur].sum1%mod+(y*len)%mod )%mod;
    t[cur].mul=(t[cur].mul*x)%mod;
    t[cur].lazy=( t[cur].lazy*x%mod+y )%mod;
}

void pushdown( int cur ) //ok
{
    if( t[cur].mul!=1ll || t[cur].lazy )
    {
        cal( ls,t[cur].mul,t[cur].lazy );
        cal( rs,t[cur].mul,t[cur].lazy );
        t[cur].mul=1ll;
        t[cur].lazy=0;
    }
}



void build( int cur ,int l,int r )
{
    t[cur].l=l;t[cur].r=r;
    t[cur].mul=1ll;
    t[cur].lazy=t[cur].sum1=0ll;
    if( l == r )
    {
        t[cur].sum1=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
    pushup( cur );
}

void update( int cur,int L,int R ,ll x,ll y )
{
    int l=t[cur].l,r=t[cur].r;
    if( L<=l && r<=R )
    {
        cal(cur,x,y);
        return;
    }
    pushdown( cur );
    int mid=(l+r)>>1;
    if( L<=mid ) update(ls,L,R,x,y);
    if( R>mid ) update(rs,L,R,x,y);
    pushup( cur );
}


ll get_Sum( int cur,int L,int R )
{
    int l=t[cur].l,r=t[cur].r;
    if( L<=l && r<=R )    return t[cur].sum1;
    ll ans=0;
    pushdown( cur );
    int mid=(l+r)>>1;
    if( L<=mid ) ans+=get_Sum(ls,L,R);
    ans%=mod;
    if( R>mid ) ans+=get_Sum(rs,L,R);
    ans%=mod;
    return ans;
}

int main()
{
    int n,m;
    scanf("%d%d%lld",&n,&m,&mod);
    for( int i=1;i<=n;i++ ) scanf("%lld",&a[i]);
    build(1,1,n+m);
    int now=n;
    while( m-- )
    {
        int op,l,r,c;
        scanf("%d",&op);
        if( op <=3 )
        {
            scanf("%d%d%d",&l,&r,&c);
            if( op==1 ) update(1,l,r,1,c);
            if( op==2 ) update(1,l,r,c,0);
            if( op==3 ) update(1,l,r,0,c);
        }
        else if( op==4 )
        {
            scanf("%d",&c);
            now++;
            update(1,now,now,0,c);
        }
        else
        {
            scanf("%d%d",&l,&r);
            printf("%lld\n",get_Sum(1,l,r));
        }
    }
}