题解 CF1942F【Farmer John's Favorite Function】

· · 题解

萌萌尺子，上大分。

首先，观察这个式子，发现 a_i 经过多次根号无法对靠后的 f_i 造成 >1 的贡献。

考虑以 K=10 为块长分块，单点修则在块内暴力，外层用线段树维护。

每个块内维护 f_{l-1}=0 时 f_r 的值 val，f_{l-1} 的最小值 need 使 f_r 增加 1。

线段树上也同理维护 val，need，合并子节点时：

细节：保证最后一个块长度为 K。

复杂度：O(nK\log n)。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=2e5+5,inf=4e18;
ll n,q,K=10,rev[N],a[N],pos[N],L[N],R[N],len;
ll msqrt(ll x){
    for(ll i=sqrt(x)+3ll;;i--)
        if(i*i<=x) return i;
}
struct node{ll val,ned;}tree[N];
#define lc k<<1
#define rc k<<1|1
#define ls lc,l,mid
#define rs rc,mid+1,r
void pushup(int k){
    if(tree[lc].val>=tree[rc].ned){
        tree[k].val=tree[rc].val+1;
        tree[k].ned=inf;
    }
    else{
        tree[k].val=tree[rc].val;
        if(tree[lc].val+1==tree[rc].ned)
            tree[k].ned=tree[lc].ned;
        else
            tree[k].ned=inf;
    }
}
void build(int k){
    ll l=L[rev[k]],r=R[rev[k]]; tree[k].val=0;
    for(ll i=l;i<=r;i++) tree[k].val=msqrt(tree[k].val+a[i]);
    tree[k].ned=tree[k].val+1;
    for(ll i=r;i>=l;i--){
        if(inf/tree[k].ned<=tree[k].ned){
            tree[k].ned=inf;
            return ;
        }
        tree[k].ned=tree[k].ned*tree[k].ned-a[i];
    }
}
void pre(int k,int l,int r){
    if(l==r){
        rev[k]=l;
        build(k);
        return ;
    }
    int mid=l+r>>1;
    pre(ls);pre(rs);
    pushup(k);
}
void change(int k,int l,int r,int x){
    if(l==r){
        build(k);
        return ;
    }
    int mid=l+r>>1;
    if(x<=mid) change(ls,x);
    else change(rs,x);
    pushup(k);
}
int main(){
    scanf("%lld%lld",&n,&q);
    for(ll i=1;i<=n;i++) scanf("%lld",&a[i]);
    len=(n-1)/K+1;
    for(ll i=1;i<=n;i++) pos[i]=len-(n-i)/K;
    for(ll i=1;i<=n;i++) R[pos[i]]=i;
    for(ll i=n;i;i--) L[pos[i]]=i;
    pre(1,1,len);
    ll x,y;
    while(q--){
        scanf("%lld%lld",&x,&y);a[x]=y;
        change(1,1,len,pos[x]);
        printf("%lld\n",tree[1].val);
    }
    return 0;
}