题解 | 区间加乘与单点求值 #

$[模板+线段树]$

给定长度为 $n$ 的 $a$ 数组，执行三种操作：

区间加数：将 $[l,r]$ 这个区间中的全部元素修改为其与一个数 $x$ 相加后的值，即 $\forall i \in [l,r],a_{i}\rightarrow a_{i} +x$
区间乘数：将 $[l,r]$ 这个区间中的全部元素修改为其与一个数 $x$ 相乘后的值，即 $\forall i \in [l,r],a_{i}\rightarrow a_{i} \times x$
单点求值：输出下标为 $x$ 的元素的值对 $998244353$ 取模后的结果，即 $a_{x} \rightarrow a_{x} \%998244353$

基础的版本是区间加数，使用的方法是用懒标记 $add$ 来 $push\_down(u)$ 传递，那么区间乘数也是需要一个懒标记 $mul$ 的。

需要思考的是两个懒标记该如何传递，先加后乘与先乘后加是不一样的

解决的方法是将先加后乘转化为先乘后加：先加上 $a$ 再乘以 $b$ 等于 $(x+a)\times b = b\times x + a \times b$ ，转化为先乘以 $b$ 再加上 $a\times b$

所以当执行操作 $2$ 时， $add$ 也需要乘以 $x$

部分 $modify\_mul()$ 代码：

void modify_mul(int u, int l, int r, int x){
    if(l <= tr[u].l && tr[u].r <= r){
        tr[u].sum = (tr[u].sum * x + mod) % mod;
        tr[u].mul = (tr[u].mul * x + mod) % mod;
        tr[u].add = (tr[u].add * x + mod) % mod;
        return;
    }

注意有这个

tr[u].add = (tr[u].add * x + mod) % mod;

而 $modify\_add()$ 代码：

void modify_add(int u, int l, int r, int x){
    if(l <= tr[u].l && tr[u].r <= r){
        tr[u].sum = (tr[u].sum + (tr[u].r - tr[u].l + 1) * x + mod) % mod;
        tr[u].add = (tr[u].add + x + mod) % mod;
        return ;
    }

是和 $mul$ 没有关系的

再 $push\_down()$ 中，所以得先更新懒标记 $mul$ ，然后更新懒标记 $add$ 。
在更新懒标记 $mul$ 时，左右两个子节点的懒标记 $add$ 同样需要乘以 $mul$
总代码：

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


const int N = 1e5 + 10;
const int mod = 998244353;

struct Node{
    int l, r;
    int sum, mul, add;
}tr[4 * N];

int n, q, a[N];


void push_up(int u){
    tr[u].sum = (tr[u << 1].sum + tr[u << 1 | 1].sum) % mod;
}

void push_down(int u){
    if(tr[u].mul != 1){
        int v = tr[u].mul;
        tr[u << 1].sum = (tr[u << 1].sum * v + mod) % mod;
        tr[u << 1].mul = (tr[u << 1].mul * v + mod) % mod;
        tr[u << 1].add = (tr[u << 1].add * v + mod) % mod;
        tr[u << 1 | 1].sum = (tr[u << 1 | 1].sum * v + mod) % mod;
        tr[u << 1 | 1].mul = (tr[u << 1 | 1].mul * v + mod) % mod;
        tr[u << 1 | 1].add = (tr[u << 1 | 1].add * v + mod) % mod;        
        tr[u].mul = 1;
    }
    if(tr[u].add){
        int v = tr[u].add;
        tr[u << 1].sum = (tr[u << 1].sum + (tr[u << 1].r - tr[u << 1].l + 1) * v + mod) % mod;
        tr[u << 1].add = (tr[u << 1].add + v + mod) % mod;
        tr[u << 1 | 1].sum = (tr[u << 1 | 1].sum + (tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1) * v  + mod) % mod;
        tr[u << 1 | 1].add = (tr[u << 1 | 1].add + v + mod) % mod;             
        tr[u].add = 0;
    }
}
void build(int u, int l, int r){
    if(l == r) tr[u] = {l, r, a[l], 1, 0};
    else{
        tr[u] = {l, r, 0, 1, 0};
        int mid = (l + r) >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        push_up(u);
    }
}

void modify_mul(int u, int l, int r, int x){
    if(l <= tr[u].l && tr[u].r <= r){
        tr[u].sum = (tr[u].sum * x + mod) % mod;
        tr[u].mul = (tr[u].mul * x + mod) % mod;
        tr[u].add = (tr[u].add * x + mod) % mod;
        return;
    }
    else{
        push_down(u);
        int mid = (tr[u].l + tr[u].r) >> 1;
        if(l <= mid) modify_mul(u << 1, l, r, x);
        if(r > mid) modify_mul(u << 1 | 1, l, r, x);
        push_up(u);
    }
}

void modify_add(int u, int l, int r, int x){
    if(l <= tr[u].l && tr[u].r <= r){
        tr[u].sum = (tr[u].sum + (tr[u].r - tr[u].l + 1) * x + mod) % mod;
        tr[u].add = (tr[u].add + x + mod) % mod;
        return ;
    }
    else{
        push_down(u);
        int mid = (tr[u].l + tr[u].r) >> 1;
        if(l <= mid) modify_add(u << 1, l, r, x);
        if(r > mid) modify_add(u << 1 | 1, l, r, x);
        push_up(u);
    }
}

int query(int u, int pos){
    if(tr[u].l == pos && pos == tr[u].r) return tr[u].sum;
    else{
        push_down(u);
        int mid = (tr[u].l + tr[u].r) >> 1;
        if(pos <= mid) return query(u << 1, pos);
        else return query(u << 1 | 1, pos);
    }
}

signed main(){
    HelloWorld;
    
    cin >> n >> q;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    build(1, 1, n);

    while(q --){
        int op; cin >> op;
        if(op == 1){
            int l, r, x; cin >> l >> r >> x;
            modify_add(1, l, r, x);
        }
        else if(op == 2){
            int l, r, x; cin >> l >> r >> x;
            modify_mul(1, l, r, x);
        }
        else{
            int x; cin >> x;
            cout << (query(1, x) + mod) % mod << endl;
        }
    }
    return 0;
}