萌新求助

回复帖子

@火之意志 2019-08-14 21:45 回复
#include <cstdio>
#define int long long
using namespace std;
struct node
{
    int l,r,w,f_add,f_mul;
}line_tree[400010];
int n,m,mod;
void down(int wz)
{
    line_tree[wz * 2].w = (line_tree[wz * 2].w * line_tree[wz].f_mul + line_tree[wz].f_add * (line_tree[wz * 2].r - line_tree[wz * 2].l + 1)) % mod;
    line_tree[wz * 2 + 1].w = (line_tree[wz * 2 + 1].w * line_tree[wz].f_mul + line_tree[wz].f_add * (line_tree[wz * 2 + 1].r - line_tree[wz * 2 + 1].l + 1)) % mod;
    line_tree[wz * 2].f_mul = line_tree[wz * 2].f_mul * line_tree[wz].f_mul % mod;
    line_tree[wz * 2 + 1].f_mul = line_tree[wz * 2 + 1].f_mul * line_tree[wz].f_mul % mod;
    line_tree[wz * 2].f_add = (line_tree[wz * 2].f_add * line_tree[wz].f_mul + line_tree[wz].f_add) % mod;
    line_tree[wz * 2 + 1].f_add = (line_tree[wz * 2 + 1].f_add * line_tree[wz].f_mul + line_tree[wz].f_add) % mod;
    line_tree[wz].f_add = 0;
    line_tree[wz].f_mul = 1;
    return;
}
void build(int wz,int l,int r)
{
    line_tree[wz].f_mul = 1;
    line_tree[wz].l = l,line_tree[wz].r = r;
    if (l == r)
    {
        scanf("%lld",&line_tree[wz].w);
        line_tree[wz].w %= mod;
        return;
    }
    int mid = (l + r) / 2;
    build(wz * 2,l,mid);
    build(wz * 2 + 1,mid + 1,r);
    line_tree[wz].w = (line_tree[wz * 2].w + line_tree[wz * 2 + 1].w) % mod;
    return;
}
int ans;
void sum(int wz,int x,int y)
{
    if (line_tree[wz].l >= x && line_tree[wz].r <= y)
    {
        ans += line_tree[wz].w;
        return;
    }
    down(wz);
    int mid = (line_tree[wz].l + line_tree[wz].r) / 2;
    if (x <= mid)
        sum(wz * 2,x,y);
    if (y > mid)
        sum(wz * 2 + 1,x,y);
    return;
}
void add_interval(int wz,int x,int y,int d)
{
    if (line_tree[wz].l >= x && line_tree[wz].r <= y)
    {
        line_tree[wz].w += d * (line_tree[wz].r - line_tree[wz].l + 1);
        line_tree[wz].f_add = (line_tree[wz].f_add + d) % mod;;
        line_tree[wz].w %= mod;
        return;
    }
    down(wz);
    int mid = (line_tree[wz].l + line_tree[wz].r) / 2;
    if (x <= mid)
        add_interval(wz * 2,x,y,d);
    if (y > mid)
        add_interval(wz * 2 + 1,x,y,d);
    line_tree[wz].w = (line_tree[wz * 2].w + line_tree[wz * 2 + 1].w) % mod;
    return;
}
void mul_interval(int wz,int x,int y,int d)
{
    if (line_tree[wz].l >= x && line_tree[wz].r <= y)
    {
        line_tree[wz].w =line_tree[wz].w * d % mod;
        line_tree[wz].f_mul = line_tree[wz].f_mul * d % mod;
        line_tree[wz].f_add = line_tree[wz].f_add * d % mod;
        return;
    }
    down(wz);
    int mid = (line_tree[wz].l + line_tree[wz].r) / 2;
    if (x <= mid)
        mul_interval(wz * 2,x,y,d);
    if (y > mid)
        mul_interval(wz * 2 + 1,x,y,d);
    line_tree[wz].w = (line_tree[wz * 2].w + line_tree[wz * 2 + 1].w) % mod;
    return;
}
signed main()
{
    freopen("a.in","r",stdin);
    scanf("%lld%lld%lld",&n,&m,&mod);
    build(1,1,n);
    for (int i = 1; i <= m; ++i)
    {
        int a;
        scanf("%lld",&a);
        if (a == 1)
        {
            int x,y,z;
            scanf("%lld%lld%lld",&x,&y,&z);
            mul_interval(1,x,y,z);
        }
        else if (a == 2)
        {
            int x,y,z;
            scanf("%lld%lld%lld",&x,&y,&z);
            add_interval(1,x,y,z);
        }
        else
        {
            int x,y;
            scanf("%lld%lld",&x,&y);
            ans = 0;
            sum(1,x,y);
            printf("%lld\n",ans % mod);
        }
    }
    return 0;
}

模板线段树2,哇了7个点

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



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