P9989 题解

DaydreamWarrior · 2023-12-24 21:53:45 · 题解

更好的阅读体验，另外宣传下我的 blog 索引。

分析

操作过后的数一定至少变为原来的 \frac{1}{2}，所以问题变成了如何判断区间内是否会有数被修改。

可以维护 \text{lcm}，如果 v 不是 \text{lcm} 的倍数就说明存在数会被修改。

但是 \text{lcm} 可能会很大，但是如果 \text{lcm}>v 那么 v 一定不是 \text{lcm} 的倍数。

于是限制一个 \text{lcm} 的最大值，\text{lcm} \leq V 时维护具体的值，否则只维护是否 > V。

最多会被修改 n \log V 次，每次修改需要 O(\log n) 的时间去找到，因为辗转相除 \text{lcm} 单点修改的总复杂度为 O(\log V) ，总复杂度 O(n \log n \log V)。

代码

const int N = 200005,V = 1e18;
int a[N];
int n,m;

class segtree{
    private:
        int tr[N*4];
        unsigned s[N*4];

        void pushup(int u){
            if(tr[u<<1]>V||tr[u<<1|1]>V)
                tr[u] = V+1;
            else
                tr[u] = tr[u<<1]/gcd(tr[u<<1],tr[u<<1|1])*tr[u<<1|1];
            s[u] = s[u<<1]+s[u<<1|1];
        }
    public:
        void modify(int u,int l,int r,int L,int R,int v){
            if(tr[u]<=V&&v%tr[u]==0)
                return;
            if(l==r){
                s[u] = tr[u] = gcd(tr[u],v);
                return;
            }
            int mid = (l+r)>>1;
            if(L<=mid)
                modify(u<<1,l,mid,L,R,v);
            if(R>mid)
                modify(u<<1|1,mid+1,r,L,R,v);
            pushup(u);
        }

        unsigned query(int u,int l,int r,int L,int R){
            if(l>=L&&r<=R)
                return s[u];
            int mid = (l+r)>>1;
            if(L<=mid&&R>mid)
                return query(u<<1,l,mid,L,R)+query(u<<1|1,mid+1,r,L,R);
            if(L<=mid)
                return query(u<<1,l,mid,L,R);
            return query(u<<1|1,mid+1,r,L,R);
        }

        void build(int u,int l,int r){
            if(l==r){
                s[u] = tr[u] = a[l];
                return;
            }
            int mid = (l+r)>>1;
            build(u<<1,l,mid);
            build(u<<1|1,mid+1,r);
            pushup(u);
        }
}tr;

signed main(){
    n = in,m = in;
    for(int k=1;k<=n;k++)
        a[k] = in;
    tr.build(1,1,n);
    while(m--){
        int op = in,l = in,r = in;
        if(op==1)
            tr.modify(1,1,n,l,r,in);
        else
            out(tr.query(1,1,n,l,r),'\n');
    }
    return 0;
}