[BZOJ4355]Play with sequence(线段树)

发布于 2018-04-17  38 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ4355]Play with sequence(线段树)

Description

维护一个长度为N的序列a,现在有三种操作:
1)给出参数U,V,C,将a[U],a[U+1],...,a[V-1],a[V]都赋值为C。
2)给出参数U,V,C,对于区间[U,V]里的每个数i,将a[i]赋值为max(a[i]+C,0)。
3)给出参数U,V,输出a[U],a[U+1],...,a[V-1],a[V]里值为0的数字个数。

Tag

线段树

解决思路

观察题目给出的数据范围,发现在任意时刻,任意序列中的最小值是非负的,也就是说0若存在一定是序列的最小值。所以题目中较好处理的是1,3两个操作,第一个可以直接标记覆盖,而第三个可以通过维护最小值和最小值出现的次数来实现。
那么关键是第二个操作如何处理。考虑把第二个操作分成两步,先区间加法,再区间取max。区间加法也比较好实现,用区间加标记就好。但要注意区间加标记与区间覆盖标记的操作顺序。当区间覆盖的时候,要清空区间加标记;而若区间加的时候,如果有区间覆盖标记,就直接加到区间覆盖标记上。
所以问题在于区间取max的操作。一个自然的想法就是维护区间最小值,若区间最小值都大于当前要取max的值,那么就不向下修改,否则递归左右分别处理。这样最坏可以达到\(O(nq)\)的复杂度。
吉老师线段树这里,我们得到一种更优的操作,那就是在维护区间最小和区间最小的个数的同时,再维护区间次小。当取max的值小于最小时,不操作;当大于区间最小而小于区间次小时,只修改区间最小;当大于区间次小时,递归处理。这样可以证明复杂度是\(O(nlogn)\)的。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))
#define lson (now<<1)
#define rson (lson|1)
#define RG register
#define IL inline

const int maxN=301000;
const int inf=2147483647;
const ll INF=1e15;

class SegmentData
{
public:
    ll mn,mns;//区间最小,次小、
    ll cnt;//区间最小的次数
    ll cover,add,delta;//区间覆盖标记,区间加标记,区间最小值的加标记
    ll size;
    SegmentData(){
        cover=delta=-INF;add=0;
        return;
    }
};

int n,m;
ll Arr[maxN];
SegmentData S[maxN<<2];

IL void PushDown(RG int now);//标记下方
IL void Update(RG int now);//从儿子更新
IL void Cover(RG int now,RG ll key);//区间覆盖标记
IL void Add(RG int now,RG ll key);//区间加标记
IL void Delta(RG int now,RG ll key);//区间最小值加标记
void Build(RG int now,RG int l,RG int r);//初始化
void Modify_cover(RG int now,RG int l,RG int r,RG int ql,RG int qr,RG ll key);//区间覆盖
void Modify_add(RG int now,RG int l,RG int r,RG int ql,RG int qr,RG ll key);//区间加
void Modify_mx(RG int now,RG int l,RG int r,RG int ql,RG int qr,RG ll key);//区间取max
ll Query(RG int now,RG int l,RG int r,RG int ql,RG int qr);//查询

int main()
{
    scanf("%d%d",&n,&m);
    for (RG int i=1;i<=n;i++) scanf("%lld",&Arr[i]);
    Build(1,1,n);
    while (m--)
    {
        RG int opt;scanf("%d",&opt);
        if (opt==1)
        {
            RG int l,r,c;scanf("%d%d%d",&l,&r,&c);
            Modify_cover(1,1,n,l,r,c);
        }
        if (opt==2)
        {
            RG int l,r,c;scanf("%d%d%d",&l,&r,&c);
            Modify_add(1,1,n,l,r,c);
            Modify_mx(1,1,n,l,r,0);
        }
        if (opt==3)
        {
            RG int l,r;scanf("%d%d",&l,&r);
            printf("%lld\n",Query(1,1,n,l,r));
        }
    }
    return 0;
}

IL void PushDown(RG int now)
{
    if (S[now].add)//区间加标记
    {
        Add(lson,S[now].add);Add(rson,S[now].add);
        S[now].add=0;
    }
    if (S[now].cover!=-INF)//区间覆盖
    {
        Cover(lson,S[now].cover);Cover(rson,S[now].cover);
        S[now].cover=-INF;
    }
    if (S[now].delta!=-INF)//区间最小值加
    {
        Delta(lson,S[now].delta);Delta(rson,S[now].delta);
        S[now].delta=-INF;
    }
    return;
}

IL void Update(RG int now)//自下而上更新
{
    S[now].mn=min(S[lson].mn,S[rson].mn);
    S[now].mns=min(S[lson].mns,S[rson].mns);
    if (S[now].mn!=S[lson].mn) S[now].mns=min(S[now].mns,S[lson].mn);
    if (S[now].mn!=S[rson].mn) S[now].mns=min(S[now].mns,S[rson].mn);
    S[now].cnt=0;
    if (S[now].mn==S[lson].mn) S[now].cnt+=S[lson].cnt;
    if (S[now].mn==S[rson].mn) S[now].cnt+=S[rson].cnt;
    return;
}

IL void Cover(RG int now,RG ll key)//覆盖标记直接覆盖,同时清空加标记和最小值加标记
{
    S[now].mn=key;S[now].mns=INF;S[now].add=0;S[now].delta=-INF;
    S[now].cover=key;S[now].cnt=S[now].size;
    return;
}

IL void Add(RG int now,RG ll key)
{
    S[now].mn+=key;
    if (S[now].mns!=inf) S[now].mns+=key;
    if (S[now].cover!=-INF) S[now].cover+=key;//当有覆盖标记时,直接加到覆盖标记上
    else S[now].add+=key;//否则加到区间加标记上
    if (S[now].delta!=-INF) S[now].delta+=key;//注意区间最小值加标记也要加
    return;
}

IL void Delta(RG int now,RG ll key)//区间最小值加标记
{
    if (S[now].mn<key)
    {
        S[now].mn=key;
        S[now].delta=max(S[now].delta,key);
    }
    return;
}

void Build(RG int now,RG int l,RG int r)
{
    S[now].size=r-l+1;
    if (l==r)
    {
        S[now].mn=Arr[l];S[now].mns=INF;
        S[now].cnt=1;
        return;
    }
    RG int mid=(l+r)>>1;
    Build(lson,l,mid);Build(rson,mid+1,r);
    Update(now);return;
}

void Modify_cover(RG int now,RG int l,RG int r,RG int ql,RG int qr,RG ll key)
{
    if ((l==ql)&&(r==qr)){
        Cover(now,key);return;
    }
    PushDown(now);
    RG int mid=(l+r)>>1;
    if (qr<=mid) Modify_cover(lson,l,mid,ql,qr,key);
    else if (ql>=mid+1) Modify_cover(rson,mid+1,r,ql,qr,key);
    else
    {
        Modify_cover(lson,l,mid,ql,mid,key);
        Modify_cover(rson,mid+1,r,mid+1,qr,key);
    }
    Update(now);return;
}

void Modify_add(RG int now,RG int l,RG int r,RG int ql,RG int qr,RG ll key)
{
    if ((l==ql)&&(r==qr)){
        Add(now,key);return;
    }
    PushDown(now);
    RG int mid=(l+r)>>1;
    if (qr<=mid) Modify_add(lson,l,mid,ql,qr,key);
    else if (ql>=mid+1) Modify_add(rson,mid+1,r,ql,qr,key);
    else
    {
        Modify_add(lson,l,mid,ql,mid,key);
        Modify_add(rson,mid+1,r,mid+1,qr,key);
    }
    Update(now);return;
}

void Modify_mx(RG int now,RG int l,RG int r,RG int ql,RG int qr,RG ll key)
{
    if ((l==ql)&&(r==qr))
    {
        if (S[now].mn>=key) return;//取max的值小于等于区间最小值,直接返回
        if (S[now].mns>key)//大于区间最小值但小于区间次小值,则只修改区间最小值后返回
        {
            S[now].delta=S[now].mn=key;
            return;
        }//若上面两条都不满足,则向下递归处理
        PushDown(now);
        int mid=(l+r)>>1;
        Modify_mx(lson,l,mid,ql,mid,key);
        Modify_mx(rson,mid+1,r,mid+1,qr,key);
        Update(now);return;
    }
    PushDown(now);
    RG int mid=(l+r)>>1;
    if (qr<=mid) Modify_mx(lson,l,mid,ql,qr,key);
    else if (ql>=mid+1) Modify_mx(rson,mid+1,r,ql,qr,key);
    else
    {
        Modify_mx(lson,l,mid,ql,mid,key);
        Modify_mx(rson,mid+1,r,mid+1,qr,key);
    }
    Update(now);return;
}

ll Query(RG int now,RG int l,RG int r,RG int ql,RG int qr)
{
    if ((l==ql)&&(r==qr)) return ((S[now].mn==0)?(S[now].cnt):(0));
    PushDown(now);
    RG int mid=(l+r)>>1;
    if (qr<=mid) return Query(lson,l,mid,ql,qr);
    else if (ql>=mid+1) return Query(rson,mid+1,r,ql,qr);
    else return Query(lson,l,mid,ql,mid)+Query(rson,mid+1,r,mid+1,qr);
}

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ4355]Play with sequence(线段树)


HNCJ OIer 一枚