2018.07.23 codeforces 438 D. The Child and Sequence (선분 수)

전송 문 라인 트 리 유지 보수 구간 모델 링, 단점 수정, 구간 구 화.이 문 제 는 낡은 방식 입 니 다. 한 숫자 에 있어 서 매번 모델 을 뽑 을 때마다 적어도 절반 은 줄 여야 합 니 다. 그러면 매번 한 점 씩 수정 하 는 것 이 시간 복잡 도 에 기여 하 는 것 은 하나의 log l o g 이기 때문에 유지 구간 의 최대 치 를 자 르 고 매번 한 점 씩 폭력 으로 모델 을 뽑 습 니 다. 그러면 시간 복잡 도 는 O (nlogn) O (n l o g n) 입 니 다.코드 는 다음 과 같 습 니 다:

#include
#define lc (p<<1)
#define rc (p<<1|1)
#define mid (T[p].l+T[p].r>>1)
#define N 100005
#define ll long long
using namespace std;
inline ll read(){
    ll ans=0;
    char ch=getchar();
    while(!isdigit(ch))ch=getchar();
    while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
    return ans;
}
inline void write(ll x){
    if(x>9)write(x/10);
    putchar((x%10)^48);
}
ll n,m,a[N];
struct Node{ll l,r,sum,maxn;}T[N<<2];
inline ll max(ll a,ll b){return a>b?a:b;}
inline void pushup(ll p){T[p].sum=T[lc].sum+T[rc].sum,T[p].maxn=max(T[lc].maxn,T[rc].maxn);}
inline void build(ll p,ll l,ll r){
    T[p].l=l,T[p].r=r;
    if(l==r){T[p].sum=T[p].maxn=a[l];return;}
    build(lc,l,mid),build(rc,mid+1,r),pushup(p);
}
inline void update(ll p,ll k,ll v){
    if(T[p].l==T[p].r){T[p].maxn=T[p].sum=v;return;}
    if(k<=mid)update(lc,k,v);
    else update(rc,k,v);
    pushup(p);
}
inline void modify(ll p,ll ql,ll qr,ll v){
    if(ql>T[p].r||qr<T[p].l||v>T[p].maxn)return;
    if(T[p].l==T[p].r){T[p].sum=T[p].maxn=T[p].sum%v;return;}
    if(qr<=mid)modify(lc,ql,qr,v);
    else if(ql>mid)modify(rc,ql,qr,v);
    else modify(lc,ql,mid,v),modify(rc,mid+1,qr,v);
    pushup(p);
}
inline ll query(ll p,ll ql,ll qr){
    if(ql>T[p].r||qr<T[p].l)return 0;
    if(ql<=T[p].l&&T[p].r<=qr)return T[p].sum;
    if(qr<=mid)return query(lc,ql,qr);
    if(ql>mid)return query(rc,ql,qr);
    return query(lc,ql,mid)+query(rc,mid+1,qr);
}
int main(){
    n=read(),m=read();
    for(ll i=1;i<=n;++i)a[i]=read();
    build(1,1,n);
    while(m--){
        ll op=read(),a=read(),b=read();
        switch(op){
            case 1:{write(query(1,a,b)),puts("");break;}
            case 2:{ll v=read();modify(1,a,b,v);break;}
            default:{update(1,a,b);break;}
        }
    }
    return 0;
}