5.The Child and Sequence

5.The Child and Sequence

#include<cstdio>
#include<cstring>
#include<vector>
#define ll long long 
using namespace std;
 
const int maxl=1e6+5;
int n,q,cont;
struct node {
    int l,r,tag,max_;
    ll sum;
};
int a[maxl];
node tree[maxl<<2];
vector<long long> ans;
 
 
int max(int a,int b){
    return a>b?a:b;
}
void debug(){
    // for(int i=1;i<n;i++){
    //  printf("%d ",a[i]);
    // }
    // printf("\n");
}
void build(int k,int l,int r)
{
    tree[k].l=l;tree[k].r=r;
    if(l==r)
    {   
        tree[k].max_=a[l];
        tree[k].sum=a[l];
        return;
    }
    int mid=(tree[k].l+tree[k].r)>>1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
    tree[k].max_=max(tree[k<<1].max_,tree[k<<1|1].max_);
    tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum;
}
void pup(int k,int index,int x){
    if(index<tree[k].l||index>tree[k].r)return;
    if(tree[k].l==tree[k].r){
        a[tree[k].r]=x;
        tree[k].sum=x;
        tree[k].max_=x;
        return;
    }
    int mid=(tree[k].l+tree[k].r)>>1;
    pup(k<<1,index,x);
    pup(k<<1|1,index,x);
    tree[k].max_=max(tree[k<<1].max_,tree[k<<1|1].max_);
    tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum;
    
}
void add(int k,int l,int r,int x)
{
    if(tree[k].l==tree[k].r)
    {
        tree[k].max_=x;
        tree[k].sum=x;
        return;
    }
    int mid=(tree[k].l+tree[k].r)>>1;
    if(r<=mid)
        add(k<<1,l,r,x);
    else
        if(l>mid)
            add(k<<1|1,l,r,x);
        else
            add(k<<1,l,mid,x),add(k<<1|1,mid+1,r,x);
    tree[k].max_=max(tree[k<<1].max_,tree[k<<1|1].max_);
    tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum;
}
 
int query_max(int k,int l,int r)
{
    int max_,mid=(tree[k].l+tree[k].r)>>1;
    if(tree[k].l==l && tree[k].r==r)
        return tree[k].max_;
    if(r<=mid)
        return query_max(k<<1,l,r);
    else
        if(l>mid)
            return query_max(k<<1|1,l,r);
        else
            return max(query_max(k<<1,l,mid),query_max(k<<1|1,mid+1,r));
}
void tree_mod(int k,int l,int r,int x){
    /*if(l>tree[k].r||r<tree[k].l)return;
    if(tree[k].l==tree[k].r){
        a[tree[k].r]=tree[k].max_=tree[k].sum=tree[k].sum%x;
        return;
    }
    int mid=(tree[k].l+tree[k].r)>>1;
    tree_mod(k<<1,l,mid,x);
    tree_mod(k<<1|1,mid+1,r,x);
    tree[k].max_=max(tree[k<<1].max_,tree[k<<1|1].max_);
    tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum;*/
    if(tree[k].max_<x){
        return;
    }
    if(tree[k].l==tree[k].r)
    {
        tree[k].sum%=x;
        tree[k].max_=tree[k].sum;
        return;
    }
    int mid=(tree[k].l+tree[k].r)>>1;
    if(r<=mid)
        tree_mod(k<<1,l,r,x);
    else
        if(l>mid)
            tree_mod(k<<1|1,l,r,x);
        else
            tree_mod(k<<1,l,mid,x),tree_mod(k<<1|1,mid+1,r,x);
    tree[k].max_=max(tree[k<<1].max_,tree[k<<1|1].max_);
    tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum;
}
long long query_sum(int k,int l,int r)
{
    ll maxnum;
    if(tree[k].l==l && tree[k].r==r)
        return tree[k].sum;
    ll mid=(tree[k].l+tree[k].r)>>1;
    if(r<=mid)
        maxnum=query_sum(k<<1,l,r);
    else
    if(l>=mid+1)
        maxnum=query_sum(k<<1|1,l,r);
    else
        maxnum=(query_sum(k<<1,l,mid)+query_sum(k<<1|1,mid+1,r));
    return maxnum;
}
void prework()
{
    memset(a,0,sizeof(a));
    memset(tree,0,sizeof(tree));
    scanf("%d",&q);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    build(1,1,n);
    debug();
    
}
 
void mainwork()
{
    int tg,l,r,p,x;
    for(int i=1;i<=q;i++)
    {
        
        scanf("%d",&tg);
        if(tg==1){
            scanf("%d%d",&l,&r);
            printf("%lld\n",query_sum(1,l,r));
        //  ans.push_back(query_sum(1,l,r));
        }
        if(tg==2){
            scanf("%d%d%d",&l,&r,&x);
            debug();
            tree_mod(1,l,r,x);
            debug();
        }
        if(tg==3){
            scanf("%d%d",&p,&x);
            debug();
            pup(1,p,x);
            debug();
        }
    }
    // for(auto i:ans){
    //  printf("%lld\n",i);
    // }
}
 
int main()
{
    int t;
    scanf("%d",&n);
    
    //  ans.clear();
        prework();
        mainwork();
 
    
    return 0;
}