CF438D

Aryper · 2021-11-16 20:33:30 · 个人记录

The Child and Sequence

完了，没看出来是原题。

实际上这里的取模操作是有限的，只要区间的最大值比当前的模数小我们就可以不用管直接输出，反之暴力修改。

因为可以想一想，在 x>p 的情况下，这个 x\bmod p<\dfrac{x}{2}。

证明是这样的，假设 p>\dfrac{x}{2}，则 x\bmod p=x-p<\dfrac{x}{2}；假设 p\le \dfrac{x}{2}，则 p\bmod x<p\le \dfrac{x}{2}。

于是至多只要 \log x 次取模就能使 x<p。

然后单点修改并不影响复杂度，因为一次单点改仍然是增加 \log x，而单点修改至多只有 m 次。

所以最后的复杂度是可过的，应该是 O((n+m)\log x)。

代码：

#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;

const ll N=1e5;

ll n,m,op,x,y,k;

ll a[N+5];

struct jwztxdy{
    ll l,r,ma,dat;
    #define l(x) tree[x].l
    #define r(x) tree[x].r
    #define ma(x) tree[x].ma
    #define dat(x) tree[x].dat
}tree[N*4+5];

void build(ll p,ll l,ll r) {
    l(p)=l;r(p)=r;
    if(l==r) {dat(p)=a[l];ma(p)=a[l];return;}
    ll mid=(l+r)>>1;
    build(p<<1,l,mid);build(p<<1|1,mid+1,r);
    dat(p)=dat(p<<1)+dat(p<<1|1);
    ma(p)=max(ma(p<<1),ma(p<<1|1));
}

void modify2(ll p,ll l,ll r,ll mo) {
    if(l(p)==r(p)) {
        dat(p)%=mo;ma(p)=dat(p);return;
    }
    if(l(p)>=l&&r(p)<=r) {
        if(ma(p)<mo) return;
    }
    ll mid=(l(p)+r(p))>>1;
    if(l<=mid) modify2(p<<1,l,r,mo);
    if(r>mid) modify2(p<<1|1,l,r,mo);
    dat(p)=dat(p<<1)+dat(p<<1|1);
    ma(p)=max(ma(p<<1),ma(p<<1|1));
}

void modify3(ll p,ll x,ll y) {
    if(l(p)==r(p)) {dat(p)=y;ma(p)=y;return;}
    ll mid=(l(p)+r(p))>>1;
    if(x<=mid) modify3(p<<1,x,y);
    if(x>mid) modify3(p<<1|1,x,y);
    dat(p)=dat(p<<1)+dat(p<<1|1);
    ma(p)=max(ma(p<<1),ma(p<<1|1));
}

ll query(ll p,ll l,ll r) {
    if(l(p)>=l&&r(p)<=r) return dat(p);
    ll mid=(l(p)+r(p))>>1,res=0;
    if(l<=mid) res+=query(p<<1,l,r);
    if(r>mid) res+=query(p<<1|1,l,r);
    return res;
}

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

void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {
        do{buf[++len]=x%10+48;x/=10;}while(x);
    }
    else {
        putchar('-');
        do{buf[++len]=-(x%10)+48;x/=10;}while(x);
    }
    while(len>=0) putchar(buf[len--]);
}

void writeln(ll x) {
    write(x);putchar('\n');
}

int main() {

    n=read();m=read();

    for(ll i=1;i<=n;i++) a[i]=read();

    build(1,1,n);

    for(ll i=1;i<=m;i++) {
        op=read();x=read();y=read();
        if(op==1) {
            writeln(query(1,x,y));
        }
        if(op==2) {
            k=read();modify2(1,x,y,k);
        }
        if(op==3) {
            modify3(1,x,y);
        }
    }

    return 0;
}