WHOJ
Powered by Vijos
/ WHOJ / 题库 / 【模板】线段树 2 /

题解

2 条题解

  • 0
    |||
    100:0
  • 2
    @ 3 年前 
    #include <iostream>
#include <cstdio>
using namespace std;
int p;//题目中给的p
long long a[100007];//暂存数列的数组

struct node  //线段树结构体，v表示此时的答案，mul表示乘法意义上的lazytag，add是加法意义上的
{
    long long v, mul, add;
} st[400007];
//buildtree
void bt(int root, int l, int r)
{
    st[root].mul=1;//初始化lazytag
    st[root].add=0;
    if(l==r)
    {
        st[root].v=a[l];
    }
    else
    {
        int m=(l+r)/2;
        bt(root*2, l, m);
        bt(root*2+1, m+1, r);
        st[root].v=st[root*2].v+st[root*2+1].v;
    }
    st[root].v%=p;
    return ;
}
//核心代码，维护lazytag
void pushdown(int root, int l, int r)
{
    int m=(l+r)/2;
//根据我们规定的优先度，儿子的值=此刻儿子的值*爸爸的乘法lazytag+儿子的区间长度*爸爸的加法lazytag
    st[root*2].v=(st[root*2].v*st[root].mul+st[root].add*(m-l+1))%p;
    st[root*2+1].v=(st[root*2+1].v*st[root].mul+st[root].add*(r-m))%p;
//很好维护的lazytag
    st[root*2].mul=(st[root*2].mul*st[root].mul)%p;
    st[root*2+1].mul=(st[root*2+1].mul*st[root].mul)%p;
    st[root*2].add=(st[root*2].add*st[root].mul+st[root].add)%p;
    st[root*2+1].add=(st[root*2+1].add*st[root].mul+st[root].add)%p;
//把父节点的值初始化
    st[root].mul=1;
    st[root].add=0;
    return ;
}
//update1，乘法，stdl此刻区间的左边，stdr此刻区间的右边，l给出的左边，r给出的右边
void ud1(int root, int stdl, int stdr, int l, int r, long long k)
{
//假如本区间和给出的区间没有交集
    if(r<stdl || stdr<l)
    {
        return ;
    }
//假如给出的区间包含本区间
    if(l<=stdl && stdr<=r)
    {
        st[root].v=(st[root].v*k)%p;
        st[root].mul=(st[root].mul*k)%p;
        st[root].add=(st[root].add*k)%p;
        return ;
    }
//假如给出的区间和本区间有交集，但是也有不交叉的部分
//先传递lazytag
    pushdown(root, stdl, stdr);
    int m=(stdl+stdr)/2;
    ud1(root*2, stdl, m, l, r, k);
    ud1(root*2+1, m+1, stdr, l, r, k);
    st[root].v=(st[root*2].v+st[root*2+1].v)%p;
    return ;
}
//update2，加法，和乘法同理
void ud2(int root, int stdl, int stdr, int l, int r, long long k)
{
    if(r<stdl || stdr<l)
    {
        return ;
    }
    if(l<=stdl && stdr<=r)
    {
        st[root].add=(st[root].add+k)%p;
        st[root].v=(st[root].v+k*(stdr-stdl+1))%p;
        return ;
    }
    pushdown(root, stdl, stdr);
    int m=(stdl+stdr)/2;
    ud2(root*2, stdl, m, l, r, k);
    ud2(root*2+1, m+1, stdr, l, r, k);
    st[root].v=(st[root*2].v+st[root*2+1].v)%p;
    return ;
}
//访问，和update一样
long long query(int root, int stdl, int stdr, int l, int r)
{
    if(r<stdl || stdr<l)
    {
        return 0;
    }
    if(l<=stdl && stdr<=r)
    {
        return st[root].v;
    }
    pushdown(root, stdl, stdr);
    int m=(stdl+stdr)/2;
    return (query(root*2, stdl, m, l, r)+query(root*2+1, m+1, stdr, l, r))%p;
}
int n,m;
int main()
{
    scanf("%d%d%d", &n, &m, &p);//n个数字， m个操作， 模为p
    for(int i=1; i<=n; i++)
    {
        scanf("%lld", &a[i]);
    }
    bt(1, 1, n);//建树
    while(m--)
    {
        int op;
        scanf("%d", &op);
        int x, y;
        long long k;
        if(op==1)  //对区间[x,y]每个数 *k
        {
            scanf("%d%d%lld", &x, &y, &k);
            ud1(1, 1, n, x, y, k);
        }
        else if(op==2)    //对区间[x,y]每个数 +k
        {
            scanf("%d%d%lld", &x, &y, &k);
            ud2(1, 1, n, x, y, k);
        }
        else    //对区间[x,y]求和，注意对p取模
        {
            scanf("%d%d", &x, &y);
            printf("%lld\n", query(1, 1, n, x, y));
        }
    }
    return 0;
}
    Copy
  • 2
    @ 3 年前

    相比较于P3372P3372，此题多了个区间乘法。

    一个 tag 似乎应付不了了，那么来两个 tag 啊： addadd 和 mulmul 。

    前置知识：通过P1080【模板】线段树 1

    1. 区间加法

    还是一样。

    s[pos].add = (s[pos].add + k) % mod;
s[pos].sum = (s[pos].sum + k * (s[pos].r - s[pos].l + 1)) % mod;
    Copy

    2. 区间乘法

    这里就有点不一样了。

    先把 mulmul 和 sumsum 乘上 kk 。

    对于之前已经有的 addadd ，把它乘上 kk 即可。在这里，我们把乘之后的值直接更新addadd的值。

    你想， addadd 其实应该加到 sumsum 里面，所有乘上 kk 后，运用乘法分配律， (sum+add)∗k==sum∗k+add∗k(sum + add) * k == sum * k + add * k 。

    这样来实现 addadd 和 sumsum 有序进行。

    s[pos].add = (s[pos].add * k) % mod;
s[pos].mul = (s[pos].mul * k) % mod;
s[pos].sum = (s[pos].sum * k) % mod;
    Copy

    3. pushdown的维护

    现在要下传两个标记： addadd 和 mulmul 。

    sumsum ：因为 addadd 之前已经乘过，所以在子孩子乘过 mulmul 后直接加就行。

    mulmul ：直接乘。

    addadd ：因为 addadd 的值是要包括乘之后的值，所以子孩子要先乘上 mulmul 。

    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].mul = (s[pos << 1].mul * s[pos].mul) % mod;

s[pos << 1].add = (s[pos << 1].add * s[pos].mul + s[pos].add) % mod;
    Copy

    代码

    在此注释： <<<< 和 ∣| 是位运算，n<<1==n∗2，n<<1∣1==n∗2+1n << 1 == n * 2，n << 1 | 1 == n * 2 + 1（再具体的自己百度）。

    #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;
}
    Copy

    日拱一卒，功不唐捐

  • 1

【模板】线段树 2

信息

ID
1102
难度
8
分类
线段树 点击显示
标签
递交数
3
已通过
2
通过率
67%
上传者
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  1. © 2005 - 2023 Vijos.org
  2. uibuild-2f1065f
  3. 沪ICP备14040537号-1