【模板】线段树 2

题目描述

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

将某区间每一个数乘上 $x$；
将某区间每一个数加上 $x$；
求出某区间每一个数的和。

输入格式

第一行包含三个整数 $n,q,m$，分别表示该数列数字的个数、操作的总个数和模数。

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

接下来 $q$ 行每行包含若干个整数，表示一个操作，具体如下：

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

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

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

输出格式

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

样例 #1

样例输入 #1

样例输出 #1

17
2

提示

【数据范围】

对于 $30\%$ 的数据：$n \le 8$，$q \le 10$。
对于 $70\%$ 的数据：$n \le 10^3 $，$q \le 10^4$。
对于 $100\%$ 的数据：$1 \le n \le 10^5$，$1 \le q \le 10^5$。

除样例外，$m = 571373$。

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

故输出应为 $17$、$2$（$40 \bmod 38 = 2$）。

以上是题面

首先给出ACcode和清晰题解者将获得免费的三个样例（我给）。

主要在区间乘法的地方不知道怎么做。大家可以看看我P3372线段数1的代码：

#include<iostream>
#include<cmath>
#define int long long
using namespace std;
int n,m;
int mov,x,y,k;
struct node{
    int left;
    int right;
    int sum;
    int l,r;
    int lazy;
}tree[400005];
int num[100005];
inline int read(){
    int ret=1,k=0;
    char c=getchar();
    while(c<'0' or c>'9'){if(c=='-'){ret = -1;}c=getchar();}
    while(c>='0' and c<='9'){k=k*10+c-'0';c=getchar();}
    return ret*k;
}
inline void write(int n){
    if(n>9){
        write(n/10);
    }
    putchar(n%10+'0');
}
int build(int pos,int l,int r){
    if(l==r){
        tree[pos].l=l;
        tree[pos].r=r;
        tree[pos].sum=num[(l+r)/2];
        return num[(l+r)/2];
    }
    int a=build(pos*2,l,(l+r)/2);
    int b=build(pos*2+1,(l+r)/2+1,r);
    tree[pos].left=pos*2;
    tree[pos].right=pos*2+1;
    tree[pos].sum=a+b;
    tree[pos].l=l;
    tree[pos].r=r;
    return a+b;
}

void push_down(int x)
{
    if(tree[x].lazy == 0) return;
    int le = tree[x].left, ri = tree[x].right, lz = tree[x].lazy;
    tree[le].lazy += lz, tree[ri].lazy += lz;
    tree[le].sum += lz * (tree[le].r - tree[le].l + 1);
    tree[ri].sum += lz * (tree[ri].r - tree[ri].l + 1);
    tree[x].lazy = 0;
} 

void add(int pos){
    if(tree[pos].l > y || tree[pos].r < x) return; 
    if((x<=tree[pos].l and y>=tree[pos].r)){
        tree[pos].lazy+=k;
        tree[pos].sum+=(tree[pos].r-tree[pos].l + 1)*k;
        return;
    }
//    if(tree[pos].lazy>0){
//        tree[tree[pos].left].lazy+=tree[pos].lazy,tree[tree[pos].left].sum+=tree[tree[pos].left].lazy*(tree[tree[pos].left].r-tree[tree[pos].left].l + 1);
//        tree[tree[pos].right].lazy+=tree[pos].lazy,tree[tree[pos].right].sum+=tree[tree[pos].right].lazy*(tree[tree[pos].right].r-tree[tree[pos].right].l + 1);
//        tree[pos].lazy=0;
//    }
    push_down(pos);
    add(tree[pos].left);//递归下降
    add(tree[pos].right);//递归下降
    tree[pos].sum = tree[tree[pos].left].sum + tree[tree[pos].right].sum;
}
int ask(int pos){
    if(tree[pos].l > y || tree[pos].r < x) return 0; 
    if((x<=tree[pos].l and y>=tree[pos].r)){
        return tree[pos].sum;
    }
//    if(tree[pos].lazy>0){
//        tree[tree[pos].left].lazy+=tree[pos].lazy,tree[tree[pos].left].sum+=tree[tree[pos].left].lazy*(tree[tree[pos].left].r-tree[tree[pos].left].l + 1);
//        tree[tree[pos].right].lazy+=tree[pos].lazy,tree[tree[pos].right].sum+=tree[tree[pos].right].lazy*(tree[tree[pos].right].r-tree[tree[pos].right].l + 1);
//        tree[pos].lazy=0;
//    }
    push_down(pos);
    int ret=0;
    ret+=ask(tree[pos].left);//递归下降
    ret+=ask(tree[pos].right);//递归下降
    return ret;
}
signed main(){
    n=read();
    m=read();
    for(int i = 1;i <= n;i++){
        num[i]=read();
    }
    build(1,1,n);

    while(m--){
        mov=read();
        if(mov==1){
            x=read(),y=read(),k=read();
            add(1);
        }else{
            x=read(),y=read();
            write(ask(1));
            putchar('\n');
        }
    }
    return 0;
}

以上我没有抄题解。我自己写的。

这是P3372的代码。求P3373思路和ACcode!!!

铜龟的博客

博客

悬赏