欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

codeforces438 D. The Child and Sequence

程序员文章站 2022-06-22 17:42:33
2020威海区域赛G. Caesar Cipher就用到了此思想(今天碰到模板题了还是再写一遍吧D. The Child and Sequence区间取模操作模板题有一个公式 x%pp)x\%p<\frac{x}{2}(x>p)x%p<2x​(x>p) 由此对于每一个数最多模log次,如果我们保留修改每个数的值最多修改mlog(ai)mlog(a_i)mlog(ai​)次,记录区间最值并判断是否递归(剪纸)。时间复杂度nlognlogainlognl...

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

D. The Child and Sequence

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

#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

相关标签: 线段树