P10638 BZOJ4355 Play with sequence 题解

hzoi_Shadow · 2025-05-05 15:15:23 · 题解

题目传送门

前置知识

区间最值操作 & 区间历史最值

解法

将操作 1 也化成操作 2 的形式，有 a_{i} \gets \max(a_{i}-\infty,c)。

现在就转化成了区间加和区间最值，考虑使用吉司机线段树，由势能分析可知时间复杂度为 O(m \log^{2} n)。标记下传时注意遵循一定的顺序，这里的代码中规定加法标记优先级高于覆盖标记。

因保证操作过程中 a_{i} \ge 0，所以只需要记录最小值出现次数即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define ull unsigned long long
#define sort stable_sort 
#define endl '\n'
const ll inf=0x3f3f3f3f3f;
ll a[300010];
struct SMT
{
    struct SegmentTree
    {
        ll mn,se,cnt,cov,add;
    }tree[1200010];
    #define lson(rt) (rt<<1)
    #define rson(rt) (rt<<1|1)
    void pushup(ll rt)
    {
        tree[rt].mn=min(tree[lson(rt)].mn,tree[rson(rt)].mn);
        if(tree[lson(rt)].mn<tree[rson(rt)].mn)
        {
            tree[rt].se=min(tree[lson(rt)].se,tree[rson(rt)].mn);
            tree[rt].cnt=tree[lson(rt)].cnt;
        }
        if(tree[lson(rt)].mn==tree[rson(rt)].mn)
        {
            tree[rt].se=min(tree[lson(rt)].se,tree[rson(rt)].se);
            tree[rt].cnt=tree[lson(rt)].cnt+tree[rson(rt)].cnt;
        }
        if(tree[lson(rt)].mn>tree[rson(rt)].mn)
        {
            tree[rt].se=min(tree[lson(rt)].mn,tree[rson(rt)].se);
            tree[rt].cnt=tree[rson(rt)].cnt;
        }
    }
    void build(ll rt,ll l,ll r)
    {
        tree[rt].cov=-1;
        if(l==r)
        {
            tree[rt].mn=a[l];  tree[rt].se=inf;
            tree[rt].cnt=1;
            return;
        }
        ll mid=(l+r)/2;
        build(lson(rt),l,mid);  build(rson(rt),mid+1,r);
        pushup(rt);
    }
    void pushlazy(ll rt,ll add,ll cov)
    {
        tree[rt].mn+=add;
        if(tree[rt].se!=inf)  tree[rt].se+=add;
        tree[rt].add+=add;
        if(tree[rt].cov!=-1)  tree[rt].cov+=add;
        if(cov==-1||tree[rt].mn>=cov)  return;
        tree[rt].mn=tree[rt].cov=cov;
    }
    void pushdown(ll rt)
    {   
        pushlazy(lson(rt),tree[rt].add,tree[rt].cov);
        pushlazy(rson(rt),tree[rt].add,tree[rt].cov);
        tree[rt].add=0;  tree[rt].cov=-1;
    }
    void update1(ll rt,ll l,ll r,ll x,ll y,ll val)
    {
        if(x<=l&&r<=y)
        {
            pushlazy(rt,val,-1);
            return;
        }
        pushdown(rt);
        ll mid=(l+r)/2;
        if(x<=mid)  update1(lson(rt),l,mid,x,y,val);
        if(y>mid)  update1(rson(rt),mid+1,r,x,y,val);
        pushup(rt);
    }
    void update2(ll rt,ll l,ll r,ll x,ll y,ll val)
    {
        if(tree[rt].mn>=val)  return;
        if(x<=l&&r<=y&&tree[rt].se>val)
        {
            pushlazy(rt,0,val);
            return;
        }
        pushdown(rt);
        ll mid=(l+r)/2;
        if(x<=mid)  update2(lson(rt),l,mid,x,y,val);
        if(y>mid)  update2(rson(rt),mid+1,r,x,y,val);
        pushup(rt);
    }
    ll query(ll rt,ll l,ll r,ll x,ll y)
    {
        if(x<=l&&r<=y)  return (tree[rt].mn==0)*tree[rt].cnt;
        pushdown(rt);
        ll mid=(l+r)/2,ans=0;
        if(x<=mid)  ans+=query(lson(rt),l,mid,x,y);
        if(y>mid)  ans+=query(rson(rt),mid+1,r,x,y);
        return ans;
    }
}T;
int main()
{
// #define Isaac
#ifdef Isaac
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
#endif  
    ll n,m,pd,l,r,x,i;
    cin>>n>>m;
    for(i=1;i<=n;i++)  cin>>a[i];
    T.build(1,1,n);
    for(i=1;i<=m;i++)
    {
        cin>>pd>>l>>r;
        if(pd==1)
        {
            cin>>x;
            T.update1(1,1,n,l,r,-inf);
            T.update2(1,1,n,l,r,x);
        }
        if(pd==2)
        {   
            cin>>x;
            T.update1(1,1,n,l,r,x);
            T.update2(1,1,n,l,r,0);
        }
        if(pd==3)  cout<<T.query(1,1,n,l,r)<<endl;
    }
    return 0;
}