CF438D

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

思路

区间和和单点修改较为容易，难点在于区间取模这一操作。

一开始sb，区间取模直接把区间和给取模了，这样显然是错的。

然后开始考虑如何执行区间取模的操作。

想起了之间写过的区间开方，这一题是否也可以暴力修改？

考虑数 $x$ 取模后的大小，设 $x$ 对 $y$ 取模后为 $z$ 。

若 $y>x$ 则 $x=z$ 。

若 $y\le x$ ，感觉这个 $z$ 是小于等于 $\dfrac{x}{2}$ 的。

思考这个结论如何证明。

反证法，假设 $z$ 大于 $\dfrac{x}{2}$ ，那么有 $y>z>\dfrac{x}{2}$ 。而 $x=yt+z$ ，其中 $t\ge 1$（否则 $y>x$ ），这样的话 $yt+z>\dfrac{x}{2}t+\dfrac{x}{2}\ge x$ ，矛盾，结论不成立。

所以 $z\le \dfrac{x}{2}$ 。

于是一个数 $x$ 最多取模 $\log x$ 次，这样的话暴力修改的复杂度就有了保证。

于是用线段树维护区间最大值与区间和，暴力取模，单点修改，如此即可通过本题。

代码

#include<bits/stdc++.h>
#define ll long long 
#define N 100010

using namespace std;

inline ll read() {
    ll w=1,x=0;
    char ch=0;
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return w*x;
}

int n,m;

class SegmentTree{
  private:
    ll sum[N<<2],maxn[N<<2];
    #define s(x) sum[x]
    #define m(x) maxn[x]
    #define ls (p<<1)
    #define rs (ls|1)
    #define mid (l+r>>1)
    void update(int p) {
        s(p)=s(ls)+s(rs);
        m(p)=max(m(ls),m(rs));
    }
  public:
    void build(int p,int l,int r) {
        if(l==r) {
            s(p)=m(p)=read();
            return ;
        }
        build(ls,l,mid),build(rs,mid+1,r);
        update(p);
    }
    void Modify(int p,int l,int r,int L,int R,ll x) {
        if(l>R||r<L||m(p)<x) return ;
        if(l==r) {
            s(p)%=x,m(p)%=x;
            return ;
        }
        Modify(ls,l,mid,L,R,x),Modify(rs,mid+1,r,L,R,x);
        update(p);
    }
    void Modify(int p,int l,int r,int x,ll y) {
        if(l>x||r<x) return ;
        if(l==r) {
            s(p)=m(p)=y;
            return ;
        }
        Modify(ls,l,mid,x,y),Modify(rs,mid+1,r,x,y);
        update(p);
    }
    ll ask(int p,int l,int r,int L,int R) {
        if(l>R||r<L) return 0;
        if(l>=L&&r<=R) return s(p);
        return ask(ls,l,mid,L,R)+ask(rs,mid+1,r,L,R);
    }
}SMT;

int main() {
    n=read(),m=read();
    SMT.build(1,1,n);

    for(int i=1;i<=m;i++) {
        int op,l,r,k;
        ll x;
        op=read();
        if(op==1) {
            l=read(),r=read();
            printf("%lld\n",SMT.ask(1,1,n,l,r));
        }
        else if(op==2) {
            l=read(),r=read(),x=read();
            SMT.Modify(1,1,n,l,r,x);
        }
        else {
            k=read(),x=read();
            SMT.Modify(1,1,n,k,x);
        }
    }    
    system("pause");
    return 0;
}