codeforces438 D. The Child and Sequence

2020威海区域赛G. Caesar Cipher就用到了此思想（
今天碰到模板题了还是再写一遍吧

D. The Child and Sequence

区间取模操作模板题
有一个公式 $x\%p<\frac{x}{2}(x>p)$ 由此对于每一个数最多模log次，如果我们保留修改每个数的值最多修改$mlog(a_i)$次，记录区间最值并判断是否递归（剪纸）。
时间复杂度$nlognlog{a}_i$

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#include<set>
#include<map>
#include<cmath>
#include<stack>
#include<queue>
#include<random>
#include<bitset>
#include<string>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<unordered_set>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int mod=998244353;
const int N=100010;
struct node
{
    int l,r;
    ll sum,mx;
}tree[N<<2];
int n,m;
ll a[N];
void pushup(int u)
{
    tree[u].mx=max(tree[u<<1].mx,tree[u<<1|1].mx);
    tree[u].sum=tree[u<<1].sum+tree[u<<1|1].sum;
}
void build(int u,int l,int r)
{
    tree[u]={l,r};
    if(l==r) 
    {
        tree[u].sum=tree[u].mx=a[l];
        return;
    }
    int mid=l+r>>1;
    build(u<<1,l,mid);build(u<<1|1,mid+1,r);
    pushup(u);
}
void modify1(int u,int l,int r,ll mod)
{
    if(tree[u].mx<mod) return;
    if(tree[u].l==tree[u].r) 
    {
        tree[u].sum%=mod;
        tree[u].mx%=mod;
        return;
    }
    int mid=tree[u].l+tree[u].r>>1;
    if(l<=mid) modify1(u<<1,l,r,mod);
    if(r>mid) modify1(u<<1|1,l,r,mod);
    pushup(u);
}
void modify2(int u,int pos,ll v)
{
    if(tree[u].l==tree[u].r) 
    {
        tree[u].mx=tree[u].sum=v;
        return;
    }
    int mid=tree[u].l+tree[u].r>>1;
    if(pos<=mid) modify2(u<<1,pos,v);
    else modify2(u<<1|1,pos,v);
    pushup(u);
}
ll query(int u,int l,int r)
{
    if(tree[u].l>=l&&tree[u].r<=r) return tree[u].sum;
    
    ll v=0;
    int mid=tree[u].l+tree[u].r>>1;
    if(l<=mid) v+=query(u<<1,l,r);
    if(r>mid) v+=query(u<<1|1,l,r);
    return v;
}
int main()
{
    //IO;
    int T=1;
    //cin>>T;
    while(T--)
    {
        cin>>n>>m;
        for(int i=1;i<=n;i++) cin>>a[i];
        build(1,1,n);
        while(m--)
        {
            int op,l,r;
            cin>>op>>l>>r;
            if(op==1)
                cout<<query(1,l,r)<<'\n';
            else if(op==2)
            {
                ll x;
                cin>>x;
                modify1(1,l,r,x);
            }
            else
                modify2(1,l,r);
        }
    }
    return 0;
}

区间开根号，区间取模，都是不满足区间性质但是由于总操作次数比较少可以暴力修改。

本文地址：https://blog.csdn.net/Fighting_Peter/article/details/110290530