洛谷 P3373 【模板】线段树 2（线段树区间乘、加 区间查找）

时间：2022-04-30 14:43:11

题目描述

如题，已知一个数列，你需要进行下面三种操作：

1.将某区间每一个数乘上x

2.将某区间每一个数加上x

3.求出某区间每一个数的和

输入格式

第一行包含三个整数N、M、P，分别表示该数列数字的个数、操作的总个数和模数。

第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。

接下来M行每行包含3或4个整数，表示一个操作，具体如下：

操作1： 格式：1 x y k 含义：将区间[x,y]内每个数乘上k

操作2： 格式：2 x y k 含义：将区间[x,y]内每个数加上k

操作3： 格式：3 x y 含义：输出区间[x,y]内每个数的和对P取模所得的结果

输出格式

输出包含若干行整数，即为所有操作3的结果。

输入输出样例

输入 #1 
5 5 38
1 5 4 2 3
2 1 4 1
3 2 5
1 2 4 2
2 3 5 5
3 1 4
输出 #1 
17
2

说明/提示

时空限制：1000ms,128M

数据规模：

对于30%的数据：N<=8，M<=10

对于70%的数据：N<=1000，M<=10000

对于100%的数据：N<=100000，M<=100000

（数据已经过加强^_^）

样例说明：

洛谷 P3373 【模板】线段树 2（线段树区间乘、加 区间查找）

故输出应为17、2（40 mod 38=2）

///
///                            _ooOoo_
///                           o8888888o
///                           88" . "88
///                           (| -_- |)
///                           O\  =  /O
///                        ____/`---'\____
///                      .'  \\|     |//  `.
///                     /  \\|||  :  |||//  \
///                    /  _||||| -:- |||||-  \
///                    |   | \\\  -  /// |   |
///                    | \_|  ''\---/''  |   |
///                    \  .-\__  `-`  ___/-. /
///                  ___`. .'  /--.--\  `. . __
///               ."" '<  `.___\_<|>_/___.'  >'"".
///              | | :  `- \`.;`\ _ /`;.`/ - ` : | |
///              \  \ `-.   \_ __\ /__ _/   .-` /  /
///         ======`-.____`-.___\_____/___.-`____.-'======
///                            `=---='
///        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
///                      Buddha Bless, No Bug !
///
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>
#include <vector>
using namespace std;
#define MAXN 100010
#define ll long long
#define in(a) a=read()
inline long long read()///读入数据
{
    long long x=0,f=1;
    char ch=getchar();
    for(; !isdigit(ch); ch=getchar())
        if(ch=='-')
            f=-1;
    for(; isdigit(ch); ch=getchar())
        x=x*10+ch-'0';
    return x*f;
}

ll n, m, p, a[MAXN];

struct node
{
    ll l, r, sum, mlz, plz;
} tree[4*MAXN];

inline void build(long long i,long long l,long long r)///建树
{
    tree[i].l=l;
    tree[i].r=r;
    tree[i].mlz=1;
    tree[i].plz = 0;
    if(l==r)
    {
        tree[i].sum=a[l]%p;
        return ;
    }
    long long mid=(l+r)>>1;
    build(i<<1,l,mid);///往左儿子那边的区间建树
    build(i<<1|1,mid+1,r);///往右儿子那边的区间建树
    tree[i].sum=(tree[i<<1].sum+tree[i<<1|1].sum)%p;///父节点的和等于左儿子的和加右儿子的和
    return ;
}

inline void pushdown(long long i)
{
    long long k1=tree[i].mlz,k2=tree[i].plz;
    tree[i<<1].sum=(tree[i<<1].sum*k1+k2*(tree[i<<1].r-tree[i<<1].l+1))%p;///（左儿子的值）等于（左儿子的值）*（父节点的mlz）+（父节点的plz）*（左儿子所控制的区间）
    tree[i<<1|1].sum=(tree[i<<1|1].sum*k1+k2*(tree[i<<1|1].r-tree[i<<1|1].l+1))%p;///（右儿子的值）等于（右儿子的值）*（父节点的mlz）+（父节点的plz）*（右儿子所控制的区间）
    tree[i<<1].mlz=(tree[i<<1].mlz*k1)%p;///把父节点的mlz传给左儿子
    tree[i<<1|1].mlz=(tree[i<<1|1].mlz*k1)%p;///把父节点的mlz传给右儿子
    tree[i<<1].plz=(tree[i<<1].plz*k1+k2)%p;///（左儿子的plz）等于（左儿子plz）*（父节点mlz）+（父节点plz），即为看这个点加了多少东西
    tree[i<<1|1].plz=(tree[i<<1|1].plz*k1+k2)%p;///（右儿子的plz）等于（右儿子plz）*（父节点mlz）+（父节点plz），即为看这个点加了多少东西
    tree[i].plz=0;
    tree[i].mlz=1;
    return ;
}

inline void mul(long long i,long long l,long long r,long long k)
{
    if(tree[i].l>=l && tree[i].r<=r)///如果所查找的区间在目的区间内
    {
        tree[i].sum=(tree[i].sum*k)%p;///返回这个值
        tree[i].mlz=(tree[i].mlz*k)%p;///mlz的懒惰标记
        tree[i].plz=(tree[i].plz*k)%p;///plz*k表示这个区间加了那么多东西（包括了之前加的部分）
        return ;
    }
    pushdown(i);
    if(tree[i<<1].r>=l)  mul(i<<1,l,r,k);///如果要查找的区间在左儿子部分，就搜索左儿子
    if(tree[i<<1|1].l<=r)  mul(i<<1|1,l,r,k);///如果要查找的区间在右儿子部分，就搜索右儿子
    tree[i].sum=(tree[i<<1].sum+tree[i<<1|1].sum)%p;///父节点sum等于两个儿子的sum
    return ;
}

inline void add(long long i,long long l,long long r,long long k)
{
    if(tree[i].l>=l && tree[i].r<=r)///如果所查找的区间在目的区间内
    {
        tree[i].sum+=((tree[i].r-tree[i].l+1)*k)%p;///（该区间的和）等于（该区间的和）+（该区间所控制的元素个数）*K
        tree[i].plz=(tree[i].plz+k)%p;///标记这个区间每个元素已经加了k
        return ;
    }
    pushdown(i);
    if(tree[i<<1].r>=l)  add(i<<1,l,r,k);///如果要查找的区间在左儿子部分，就搜索左儿子
    if(tree[i<<1|1].l<=r)  add(i<<1|1,l,r,k);///如果要查找的区间在右儿子部分，就搜索右儿子
    tree[i].sum=(tree[i<<1].sum+tree[i<<1|1].sum)%p;///父节点sum等于两个儿子的sum
    return ;
}

inline ll search(long long i,long long l,long long r)
{
    if(tree[i].r<l || tree[i].l>r) return 0;///如果这个区间不在要找的区间范围内
    if(tree[i].l>=l && tree[i].r<=r)///如果所查找的区间在目的区间内
    {
        return tree[i].sum;///直接返回这个区间的和
    }
    pushdown(i);
    long long sum=0;
    if(tree[i<<1].r>=l)  sum += search(i<<1,l,r);///如果要查找的区间在左儿子部分，就搜索左儿子
    if(tree[i<<1|1].l<=r)  sum += search(i<<1|1,l,r);///如果要查找的区间在右儿子部分，就搜索右儿子
    return sum %= p;
}

int main()
{
    in(n);
    in(m);
    in(p);
    for(int i = 1; i <= n; i++)
        in(a[i]);
    build(1,1,n);///建树

    for(int i = 1; i <= m; i++)
    {
        ll fl;
        in(fl);
        if(fl==1)
        {
            ll x, y, k;
            in(x);
            in(y);
            in(k);
            k%=p;
            mul(1, x, y, k);///乘
        }
        if(fl==2)
        {
            ll x, y, k;
            in(x);
            in(y);
            in(k);
            k%=p;
            add(1, x, y, k);///加
        }
        if(fl==3)
        {
            ll x, y;
            in(x);
            in(y);
            printf("%lld\n", search(1,x,y));///区间查找
        }
    }
    return 0;
}

 

标签：

相关文章