题解：P12263 『STA - R9』回听

· · 题解

考虑对于一个 b_i，它右侧的数与它交换会减少，所以它由它左侧的 a_j 贡献 a_j，右侧的 a_j 最多贡献 a_j-(j-i)=a_j-j+i。即 b_i=\max(0,\min_{k=1}^ia_k,\min_{k=i+1}^na_k-k+i)。所以 b_i 单调不减。若继续观察 b_i 的增速可以发现，b_{i+1} 若选择与 b_i 相同的 a_k 则 b_{i+1}=b_i+1，所以相邻的 b_i 最多相差 1。所以所求不同 b_i 的种数即为 b_n-b_1+1。代入上式得到 b_1=\max(0,\min_{k=1}^na_k-k+1),b_n=\min a_k，用两个线段树分别维护这两个值即可。

const ll N=5e5+10;
ll n,q,a[N],sgtr1[N*4],sgtr2[N*4],tg1[N*4],tg2[N*4];

ll ls(ll p){
    return p*2; 
} 

ll rs(ll p){
    return p*2+1; 
}

void pushup(ll p){
    sgtr1[p]=min(sgtr1[ls(p)],sgtr1[rs(p)]);
    sgtr2[p]=min(sgtr2[ls(p)],sgtr2[rs(p)]);
}

void pushdown(ll p){
    if(tg1[p]){
        sgtr1[ls(p)]+=tg1[p];
        sgtr1[rs(p)]+=tg1[p];
        tg1[ls(p)]+=tg1[p];
        tg1[rs(p)]+=tg1[p];
        tg1[p]=0;
    }

    if(tg2[p]){
        sgtr2[ls(p)]+=tg2[p];
        sgtr2[rs(p)]+=tg2[p];
        tg2[ls(p)]+=tg2[p];
        tg2[rs(p)]+=tg2[p];
        tg2[p]=0;
    }
}

void build(ll p,ll l,ll r){
    if(l==r){
        sgtr1[p]=a[l]-l+1;
        sgtr2[p]=a[l];
        return;
    }

    ll mid=(l+r)/2;
    build(ls(p),l,mid);
    build(rs(p),mid+1,r);
    pushup(p);
}

void upd(ll p,ll l,ll r,ll ql,ll qr,ll v){
    if(l>qr or r<ql) return;

    if(ql<=l and r<=qr) {
        sgtr1[p]+=v;
        sgtr2[p]+=v;
        tg1[p]+=v;
        tg2[p]+=v;
        return;
    }

    pushdown(p);
    ll mid=(l+r)/2;
    upd(ls(p),l,mid,ql,qr,v);
    upd(rs(p),mid+1,r,ql,qr,v);
    pushup(p);
}

int main(){
    sync_off;
    cin>>n>>q;

    rep(i,1,n) cin>>a[i];

    build(1,1,n);

    count(q){
        ll l,r,v;
        cin>>l>>r>>v;
        upd(1,1,n,l,r,v);
        cout<<max(0ll,sgtr2[1])-max(0ll,sgtr1[1])+1<<'\n';
    }
}