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

#include <iostream>
#include <vector>
using namespace std;
using ll=long long;
//定义余数
const int P=998244353;
//新建存储节点
struct Node{
    int l=0,r=0;
    ll sum=0;
    ll add_tag=0;
    ll mul_tag=1;
    Node()=default;
    void setLR(int toL,int toR){
        l=toL;
        r=toR;
    }
};
//新建存储树的节点
vector<Node> tree;
//创建数据数组
vector<int> arr;
//定义更新函数
void push_up(int node){
    tree[node].sum=tree[2*node].sum+tree[2*node+1].sum;
}
//构造线段树
void buildTree(int node){
    int l=tree[node].l;
    int r=tree[node].r;
    if(l==r){
        tree[node].sum=arr[l];
        return;
    }
    int mid=(r+l)/2;
    tree[2*node].setLR(l, mid);
    buildTree(2*node);
    tree[2*node+1].setLR(mid+1, r);
    buildTree(2*node+1);
    push_up(node);
}
void push_down_update(int father,int child){
    int len=tree[child].r-tree[child].l+1;
    tree[child].sum=(tree[child].sum*tree[father].mul_tag+tree[father].add_tag*len)%P;
    tree[child].mul_tag=(tree[child].mul_tag*tree[father].mul_tag)%P;
    tree[child].add_tag=(tree[child].add_tag*tree[father].mul_tag+tree[father].add_tag)%P;
}
//定义下推操作
void push_down(int node){
    if (tree[node].mul_tag != 1 || tree[node].add_tag != 0) {
        int left=2*node;
        int right=2*node+1;
        push_down_update(node, left);
        push_down_update(node, right);
        tree[node].mul_tag = 1;
        tree[node].add_tag = 0;
    }
}
//区间修改操作
void update(int node,int x,int toL,int toR,int op){
    int l=tree[node].l;
    int r=tree[node].r;
    if(toL<=l && r<=toR){
        if(op==1){//op=1加法
            tree[node].add_tag=(tree[node].add_tag+x)%P;
            tree[node].sum=(tree[node].sum+x*(r-l+1))%P;
            return;
        }else if(op==2){//乘法
            tree[node].add_tag=(tree[node].add_tag*x)%P;
            tree[node].mul_tag=(tree[node].mul_tag*x)%P;
            tree[node].sum=(tree[node].sum*x)%P;
            return;
        }
    }else{
        //下推
        push_down(node);
        //区间【1,8],mid=4,左区间【1，4】、右区间【5，8】
    //查询【2，6】
        if(tree[2*node].r>=toL){
            update(2*node, x, toL, toR, op);
        }
        if(tree[2*node+1].l<=toR){
            update(2*node+1, x, toL, toR, op);
        }
        push_up(node);
    }
}
//查询操作
int query(int node,int x){
    int l=tree[node].l;
    int r=tree[node].r;
    int total=0;
    if(l<=x && x<=r){
        if(l==r){
            total=tree[node].sum;
            return total;
        }else{
            //下推
            push_down(node);
            if(x<=tree[2*node].r)
            total=query(2*node, x);
            else if(x>=tree[2*node+1].l)
            total=query(2*node+1, x);
        }
    }
    return total;
}
int main() {
    int n,q;
    cin>>n>>q;
    arr.resize(n+1, 0);
    for(int i=1;i<=n;i++){
        cin>>arr[i];
    }
    tree.resize(4*n+5);
    tree[1].setLR(1, n);
    buildTree(1);
    while(q--){
        int op,ql,qr,x;
        cin>>op;
        if(op==1 || op==2){
            cin>>ql>>qr>>x;
            update(1, x, ql,qr, op);
        }else{
            cin>>x;
            int out=query(1, x);
            if(out<0){
                out=(out%P+P)%P;
            }
            cout<<out<<endl;
        }
    }
    return 0;
}
// 64 位输出请用 printf("%lld")