首页 题解 CF

# CF438D The Child and Sequence

# 题面

给定数列，区间查询和，区间取模，单点修改。

(1≤n,m≤105)(1≤a[i]≤109)(1\leq n,m \leq 10^5) \ (1\leq a[i] \leq 10^9)

# 解法

看到这个数据范围和题目要求很明 ` 显是要用线段树做了，要是没有求见取模的操作，那么就是个线段树板子了。

那么咱们只需要考虑怎么搞操作二，对于取模运算有个很明显的就是当一个数没有模数大的话取模前后数字不变，所以我们就利用这一点以及线段树的性质进行操作。

当一段区间（也有可能是一个点）的最大值没有模数大的话直接跳过，不然就继续往下走，直到找到所有的满足条件的点，那么这样每次区间取模的复杂度就是 O(logn)O(logn) 的。

Code
#include<iostream>
#define int long long
using namespace std;
const int MAXN=1e6+10;
struct node{
    int add,max;
}v[MAXN];
int a[MAXN];
void update(int k){
    v[k].add=v[k<<1].add+v[k<<1|1].add;
    v[k].max=max(v[k<<1].max,v[k<<1|1].max);
}
void build(int l,int r,int k){
    if(l==r){
        v[k].add=a[l];
        v[k].max=a[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(l,mid,k<<1);
    build(mid+1,r,k<<1|1);
    update(k);
}
void change(int pos,int nowl,int nowr,int k,int val){
    if(nowl==nowr){
        v[k].add=val;
        v[k].max=val;
        return;
    }
    int mid=(nowl+nowr)>>1;
    if(pos<=mid){
        change(pos,nowl,mid,k<<1,val);
    }
    if(pos>mid){
        change(pos,mid+1,nowr,k<<1|1,val);
    }
    update(k);
    return ;
}
int get_max(int l,int r,int nowl,int nowr,int k){
    if(l<=nowl&&r>=nowr){
        return v[k].max;
    }
    int mid=(nowl+nowr)>>1;
    int maxx=0;
    if(l<=mid){
        maxx=max(maxx,get_max(l,r,nowl,mid,k<<1));
    }
    if(r>mid){
        maxx=max(maxx,get_max(l,r,mid+1,nowr,k<<1|1));
    }
    return maxx;
}
void modal(int pos,int nowl,int nowr,int k,int modd){
    if(nowl==nowr){
        v[k].add%=modd;
        v[k].max%=modd;
        return;
    }
    int mid=(nowl+nowr)>>1;
    if(pos<=mid){
        modal(pos,nowl,mid,k<<1,modd);
    }
    if(pos>mid){
        modal(pos,mid+1,nowr,k<<1|1,modd);
    }
    update(k);
}
void modall(int l,int r,int nowl,int nowr,int k,int modd){
    if(v[k].max<modd){
        return;
    }
    if(nowl==nowr){
        v[k].add%=modd;
        v[k].max%=modd;
        return;
    }
    int mid=(nowl+nowr)>>1;
    if(l<=mid){
        modall(l,r,nowl,mid,k<<1,modd);
    }
    if(r>mid){
        modall(l,r,mid+1,nowr,k<<1|1,modd);
    }
    update(k);
    return;
}
int out_add(int l,int r,int nowl,int nowr,int k){
    if(l<=nowl&&r>=nowr){
        return v[k].add;
    }
    int mid=(nowl+nowr)>>1;
    int ans=0;
    if(l<=mid){
        ans+=out_add(l,r,nowl,mid,k<<1);
    }
    if(r>mid){
        ans+=out_add(l,r,mid+1,nowr,k<<1|1);
    }
    return ans;
}
signed main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    build(1,n,1);
    for(int i=1;i<=m;i++){
        int opt;
        cin>>opt;
        if(opt==1){
            int l,r;
            cin>>l>>r;
            cout<<out_add(l,r,1,n,1)<<endl;
        }
        if(opt==2){
            int l,r,x;
            cin>>l>>r>>x;
            modall(l,r,1,n,1,x);
            /*int maxx=get_max(l,r,1,n,1);
            if(maxx>=x){
                for(int j=l;j<=r;j++){
                    modal(j,1,n,1,x);
                }
            }*/
        }
        if(opt==3){
            int k,x;
            cin>>k>>x;
            change(k,1,n,1,x);
        }
    }
}