Zackzhi
Zackzhi
2021-01-17 08:24

线段树(锣鼓线段树模2)

  • c++

//错解+正解

#include<iostream>
#include<cstdio>

using namespace std;

#define ll long long
#define maxn 100010

int n,m,p;
int a[maxn];

struct Segment_tree
{
    ll sum,add,mul;
    int l,r;
}s[maxn<<2];

void pushup(int k)
{
    s[k].sum=(s[k<<1].sum+s[k<<1|1].sum)%p;
    return;
}

void build(int k,int l,int r)
{
    s[k].l=l;
    s[k].r=r;
    s[k].mul=1;
    
    if(l==r)
    {
        s[k].sum=a[l]%p;
        return;
    }
    int mid=(l+r)>>1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
    pushup(k);    
    return ;
}

void pushdown(int k)
{
    s[k<<1].sum=(s[k<<1].sum*s[k].mul+(s[k<<1].r-s[k<<1].l+1)*s[k].add)%p;
    s[k<<1|1].sum=(s[k<<1|1].sum*s[k].sum+(s[k<<1|1].r-s[k<<1|1].l+1)*s[k].add)%p;
    
    s[k<<1].mul=(s[k<<1].mul*s[k].mul)%p;
    s[k<<1|1].mul=(s[k<<1|1].mul*s[k].mul)%p;
    
    s[k<<1].add=(s[k<<1].add*s[k].mul+s[k].add)%p;
    s[k<<1|1].add=(s[k<<1|1].add*s[k].mul+s[k].add)%p;
    
    s[k].mul=1;
    s[k].add=0;
    return;
}

void areaAdd(int k,int x,int y,int v)
{
    if(s[k].l>=x&&s[k].r<=y)
    {
        s[k].add=(s[k].add+v)%p;
        s[k].sum=(s[k].sum+v*(s[k].r-s[k].l+1))%p;
        return;
    }
    pushdown(k);
    int mid=(s[k].l+s[k].r)>>1;
    if(x<=mid) areaAdd(k<<1,x,mid,v);
    if(y>mid) areaAdd(k<<1|1,mid+1,y,v);
    pushup(k);
    return ;
}

void areaMul(int k,int x,int y,int v)
{
    if(s[k].l>=x&&s[k].r<=y)
    {
        s[k].mul=(s[k].mul*v)%p;
        s[k].add=(s[k].add*v)%p;
        s[k].sum=(s[k].sum*v)%p;
        return ;
    }
    pushdown(k);
    int mid=(s[k].l+s[k].r)>>1;
    if(x<=mid) areaMul(k<<1,x,mid,v);
    if(y>mid) areaMul(k<<1|1,mid+1,y,v);
    pushup(k);
    return;
}

ll query(int k,int x,int y)
{
    if(s[k].l>=x&&s[k].r<=y)
    {
        return s[k].sum;
    }
    pushdown(k);
    ll ans=0;
    int mid=(s[k].l+s[k].r)>>1;
    if(x<=mid) ans=(ans+query(k<<1,x,mid))%p;
    if(y>mid) ans=(ans+query(k<<1|1,mid+1,y))%p;
    return ans;
}
int main()
{
    scanf("%d%d%d",&n,&m,&p);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    
    build(1,1,n);
    
    for(int i=1;i<=m;i++)
    {
        int op,x,y;
        scanf("%d%d%d",&op,&x,&y);
        if(op==1)
        {
            int v;
            scanf("%d",&v);
            areaMul(1,x,y,v);
            continue;
        }
        if(op==2)
        {
            int v;
            scanf("%d",&v);
            areaAdd(1,x,y,v);
            continue;
        }
        if(op==3)
        {
            printf("%lld\n",query(1,x,y));
            continue;
        }
    }
    
    return 0;
 } 

 

/*正解

#include <bits/stdc++.h>

#define MAXN 100010
#define ll long long

using namespace std;

int n, m, mod;
int a[MAXN];

struct Segment_Tree {
    ll sum, add, mul;
    int l, r;
}s[MAXN * 4];

void update(int pos) {
    s[pos].sum = (s[pos << 1].sum + s[pos << 1 | 1].sum) % mod;
    return;
}

void pushdown(int pos) { //pushdown的维护
    s[pos << 1].sum = (s[pos << 1].sum * s[pos].mul + s[pos].add * (s[pos << 1].r - s[pos << 1].l + 1)) % mod;
    s[pos << 1 | 1].sum = (s[pos << 1 | 1].sum * s[pos].mul + s[pos].add * (s[pos << 1 | 1].r - s[pos << 1 | 1].l + 1)) % mod;
    
    s[pos << 1].mul = (s[pos << 1].mul * s[pos].mul) % mod;
    s[pos << 1 | 1].mul = (s[pos << 1 | 1].mul * s[pos].mul) % mod;
    
    s[pos << 1].add = (s[pos << 1].add * s[pos].mul + s[pos].add) % mod;
    s[pos << 1 | 1].add = (s[pos << 1 | 1].add * s[pos].mul + s[pos].add) % mod;
        
    s[pos].add = 0;
    s[pos].mul = 1;
    return; 
}

void build_tree(int pos, int l, int r) { //建树
    s[pos].l = l;
    s[pos].r = r;
    s[pos].mul = 1;
    
    if (l == r) {
        s[pos].sum = a[l] % mod;
        return;
    }
    
    int mid = (l + r) >> 1;
    build_tree(pos << 1, l, mid);
    build_tree(pos << 1 | 1, mid + 1, r);
    update(pos);
    return;
}

void ChangeMul(int pos, int x, int y, int k) { //区间乘法
    if (x <= s[pos].l && s[pos].r <= y) {
        s[pos].add = (s[pos].add * k) % mod;
        s[pos].mul = (s[pos].mul * k) % mod;
        s[pos].sum = (s[pos].sum * k) % mod;
        return;
    }
    
    pushdown(pos);
    int mid = (s[pos].l + s[pos].r) >> 1;
    if (x <= mid) ChangeMul(pos << 1, x, y, k);
    if (y > mid) ChangeMul(pos << 1 | 1, x, y, k);
    update(pos);
    return;
}

void ChangeAdd(int pos, int x, int y, int k) { //区间加法
    if (x <= s[pos].l && s[pos].r <= y) {
        s[pos].add = (s[pos].add + k) % mod;
        s[pos].sum = (s[pos].sum + k * (s[pos].r - s[pos].l + 1)) % mod;
        return;
    }
    
    pushdown(pos);
    int mid = (s[pos].l + s[pos].r) >> 1;
    if (x <= mid) ChangeAdd(pos << 1, x, y, k);
    if (y > mid) ChangeAdd(pos << 1 | 1, x, y, k);
    update(pos);
    return;
}

ll AskRange(int pos, int x, int y) { //区间询问
    if (x <= s[pos].l && s[pos].r <= y) {
        return s[pos].sum;
    }
    
    pushdown(pos);
    ll val = 0;
    int mid = (s[pos].l + s[pos].r) >> 1;
    if (x <= mid) val = (val + AskRange(pos << 1, x, y)) % mod;
    if (y > mid) val = (val + AskRange(pos << 1 | 1, x, y)) % mod;
    return val;
}

int main() {
    scanf("%d%d%d", &n, &m, &mod);
    
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    
    build_tree(1, 1, n);
    
    for (int i = 1; i <= m; i++) {
        int opt, x, y;
        scanf("%d%d%d", &opt, &x, &y);
        if (opt == 1) {
            int k;
            scanf("%d", &k);
            ChangeMul(1, x, y, k);
        }
        if (opt == 2) {
            int k;
            scanf("%d", &k);
            ChangeAdd(1, x, y, k);
        }
        if (opt == 3) {
            printf("%lld\n", AskRange(1, x, y));
        }
    }
    
    return 0;
}

*/

  • 点赞
  • 回答
  • 收藏
  • 复制链接分享

1条回答