题解：P10638 BZOJ4355 Play with sequence

wangtairan114 · 2025-03-13 15:54:23 · 题解

题目传送门

题意

维护一个数据结构，支持区间赋值，区间加法和区间取最值。

思路

原题中，区间修改为 \max(a_i+c,0) 感觉很假，考虑拆成区间加 c 后与 0 取 \max。

区间操作显然用线段树维护，维护区间最值需要用到吉司机线段树。吉司机的详细时间复杂度证明见吉老师的集训队论文，这里只给出感性理解和实现方法。

在吉司机线段树中，对于区间取 \max 我们维护区间最小值和严格次小值。递归过程中，当修改值位于最小值和次小值之间时，我们对当前区间进行修改，否则继续递归。

第一眼感觉这种做法是 O(n) 的，因为每次暴力修改最劣可能改变 n 个位置。但是我们发现，每一次取 \max 操作都会减少不同最小值的数量，减少的最小值数量与我们暴力修改次数相关。同时，我们发现通过其他操作增加最小值数量需要花费一定的次数。因此，均摊后我们时间复杂度显然小于 O(nq)。

具体地，通过吉司机线段树我们可以做到 O(q\log^2 n) 的时间复杂度，具体参考论文因为我不会势能分析。

代码

#include <bits/stdc++.h>
//by wangtairan114
using namespace std;
#define INF 0x3f3f3f3f3f3f3f3fll
#define IINF 0x3f3f3f3f
#define DINF 10000000
#define ll long long
#define sc scanf
#define pr printf
#define v1 first
#define v2 second
#define lowbit(x) ((x)&(-x))
const int N=300005;
#define lson k*2,l,mid
#define rson k*2+1,mid+1,r
#define mid ((l+r)>>1)
struct node{
    ll mn;//最小值
    ll smn;//次小值
    ll cntmn;//最小值个数
}p[N<<2];
ll a[N];
ll tgst[N<<2],tgad[N<<2],tgmx[N<<2];
node merge(node x,node y){
    node ans;
    if(x.mn>y.mn)swap(x,y);//比较最小值
    ans.mn=x.mn;
    ans.cntmn=x.cntmn;
    if(x.mn==y.mn){
        ans.cntmn+=y.cntmn;//如果最小值相同将个数累加
        ans.smn=min(x.smn,y.smn);//更新次小值
    }
    else ans.smn=min(x.smn,y.mn);
    return ans;
}
void push_up(int k){p[k]=merge(p[k*2],p[k*2+1]);}
void push_st(int k,int l,int r,ll va){
    p[k].mn=va;
    p[k].smn=INF;
    p[k].cntmn=r-l+1;
    tgst[k]=va;
    tgad[k]=0;
    tgmx[k]=-INF;
}
void push_ad(int k,int l,int r,ll va){
    p[k].mn+=va;
    if(p[k].smn!=INF)p[k].smn+=va;
    tgad[k]+=va;
    if(tgmx[k]!=-INF)tgmx[k]+=va;
}
void push_mx(int k,int l,int r,ll va){
    if(p[k].mn>=va)return;
    p[k].mn=va;
    tgmx[k]=va;
}
void push_down(int k,int l,int r){//下传懒标记
    if(tgst[k]!=-INF){push_st(lson,tgst[k]);push_st(rson,tgst[k]);}//先赋值
    if(tgad[k]){push_ad(lson,tgad[k]);push_ad(rson,tgad[k]);}//下传加法标记
    if(tgmx[k]!=-INF){push_mx(lson,tgmx[k]);push_mx(rson,tgmx[k]);}//下传max标记
    tgst[k]=-INF;
    tgad[k]=0;
    tgmx[k]=-INF;
}
void build(int k,int l,int r){
    tgmx[k]=-INF;
    tgst[k]=-INF;
    tgad[k]=0;
    if(l==r){
        p[k].mn=a[l];
        p[k].smn=INF;//不存在次小值时赋值为inf
        p[k].cntmn=1;
        return;
    }
    build(lson);
    build(rson);
    push_up(k);
}
void modify_st(int k,int l,int r,const int lbor,const int rbor,ll va){//区间赋值
    if(lbor<=l&&r<=rbor){push_st(k,l,r,va);return;}
    push_down(k,l,r);
    if(mid>=lbor)modify_st(lson,lbor,rbor,va);
    if(mid<rbor)modify_st(rson,lbor,rbor,va);
    push_up(k);
}
void modify_ad(int k,int l,int r,const int lbor,const int rbor,ll va){//区间加
    if(lbor<=l&&r<=rbor){push_ad(k,l,r,va);return;}
    push_down(k,l,r);
    if(mid>=lbor)modify_ad(lson,lbor,rbor,va);
    if(mid<rbor)modify_ad(rson,lbor,rbor,va);
    push_up(k);
}
void modify_mx(int k,int l,int r,const int lbor,const int rbor,ll va){//区间取max
    if(p[k].mn>=va)return;//如果当前区间最小值大于修改的值，直接返回
    if(lbor<=l&&r<=rbor&&p[k].smn>va){push_mx(k,l,r,va);return;}//如果区间合法且小于次小值，进行修改
    push_down(k,l,r);//否则继续下传
    if(mid>=lbor)modify_mx(lson,lbor,rbor,va);
    if(mid<rbor)modify_mx(rson,lbor,rbor,va);
    push_up(k);
}
ll query(int k,int l,int r,const int lbor,const int rbor){
    if(lbor<=l&&r<=rbor){
        if(p[k].mn==0)return p[k].cntmn;
        return 0;
    }
    push_down(k,l,r);
    ll ans=0;
    if(mid>=lbor)ans+=query(lson,lbor,rbor);
    if(mid<rbor)ans+=query(rson,lbor,rbor);
    return ans;
}
int n,q;

int main(){
    sc("%d%d",&n,&q);
    for(int i=1; i <= n; i++)
        sc("%lld",&a[i]);
    build(1,1,n);
    while(q--){
        int op;
        sc("%d",&op);
        if(op==1){
            int l,r;
            ll va;
            sc("%d%d%lld",&l,&r,&va);
            modify_st(1,1,n,l,r,va);
        }
        else if(op==2){
            int l,r;
            ll va;
            sc("%d%d%lld",&l,&r,&va);
            modify_ad(1,1,n,l,r,va);
            modify_mx(1,1,n,l,r,0);
        }
        else {
            int l,r;
            sc("%d%d",&l,&r);
            pr("%lld\n",query(1,1,n,l,r));
        }
    }
    return 0;
}

代码实现过程中，注意标记下传过程中要先下传加再下传最值，因为求完最值后的加法操作要基于原先的最值标记进行修改。