picks loves segment tree I

题目背景

来源：

\(\text {2018 WC Segment Tree Beats}\)

原作者：

\(\text {C_SUNSHINE}\)

\(\text {jiry_2}\)

题目描述：

给定一个长度为\(n\)的数列\(A\)，接下来有\(m\)次操作：
区间\([l,r]\)中的所有数变成\(min(A_i,x)\)
询问区间\([l,r]\)中所有数的和
\(n,m \le 50000\)
我会分块！
\(n,m \le 500000\)
线段树？

输入输出格式

输入格式

第一行两个正整数表示\(N,M\)

第二行\(N\)个正整数，表示数列\(A_i\)

接下来\(M\)行每行包含\(3\)或\(4\)个整数，表示一个操作，具体如下：

操作1： 1 x y x 含义：将区间\([l,r]\)内每个数变成\(min(A_i,x)\)

操作2： 2 x y 含义：输出区间\([l,r]\)内每个数的和

输出格式

输出包含若干行整数，即为所有操作\(2\)的结果。

说明：

对于所有的数据，有\(N \le 500000,M \le 500000,a_i \le 2 \times 10^9\)

保证所有出现的数据在\(int64/long \ long\)范围内

本菜鸡说不清楚，直接当板子了，看网上的dalao们都写的Ⅴ，Ⅵ，Ⅶ，Ⅸ什么的，我太菜，从基础开始来吧。

Code:

#include <cstdio>

#define ll long long

#define ls id<<1

#define rs id<<1|1

const int N=5e5+10;

ll mx[N<<2],se[N<<2],sum[N<<2],tag[N<<2],a[N];

ll max(ll x,ll y){return x>y?x:y;}

int cnt[N<<2],n,m;

void updata(int id)

{

    if(mx[ls]>mx[rs])

    {

        mx[id]=mx[ls];

        cnt[id]=cnt[ls];

        se[id]=max(se[ls],mx[rs]);

    }

    else if(mx[ls]<mx[rs])

    {

        mx[id]=mx[rs];

        cnt[id]=cnt[rs];

        se[id]=max(mx[ls],se[rs]);

    }

    else

    {

        mx[id]=mx[ls];

        cnt[id]=cnt[ls]+cnt[rs];

        se[id]=max(se[ls],se[rs]);

    }

    sum[id]=sum[ls]+sum[rs];

}

void build(int id,int l,int r)

{

    if(l==r)

    {

        sum[id]=mx[id]=a[l];

        cnt[id]=1;

        se[id]=0;

        return;

    }

    int mid=l+r>>1;

    build(ls,l,mid),build(rs,mid+1,r);

    updata(id);

}

void pushdown(int id)

{

    if(tag[id])

    {

        if(mx[ls]>tag[id])

        {

            sum[ls]-=(mx[ls]-tag[id])*cnt[ls];

            tag[ls]=mx[ls]=tag[id];

        }

        if(mx[rs]>tag[id])

        {

            sum[rs]-=(mx[rs]-tag[id])*cnt[rs];

            tag[rs]=mx[rs]=tag[id];

        }

        tag[id]=0;

    }

}

void change(int id,int L,int R,int l,int r,ll x)

{

    if(mx[id]<=x) return;

    if(L==l&&R==r&&se[id]<x)

    {

        sum[id]-=(mx[id]-x)*cnt[id];

        tag[id]=mx[id]=x;

        return;

    }

    pushdown(id);

    int Mid=L+R>>1;

    if(r<=Mid) change(ls,L,Mid,l,r,x);

    else if(l>Mid) change(rs,Mid+1,R,l,r,x);

    else change(ls,L,Mid,l,Mid,x),change(rs,Mid+1,R,Mid+1,r,x);

    updata(id);

}

ll query(int id,int L,int R,int l,int r)

{

    if(l==L&&r==R) return sum[id];

    pushdown(id);

    int Mid=L+R>>1;

    if(r<=Mid) return query(ls,L,Mid,l,r);

    else if(l>Mid) return query(rs,Mid+1,R,l,r);

    else return query(ls,L,Mid,l,Mid)+query(rs,Mid+1,R,Mid+1,r);

}

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++) scanf("%lld",a+i);

    build(1,1,n);

    ll x;

    for(int op,l,r,i=1;i<=m;i++)

    {

        scanf("%d%d%d",&op,&l,&r);

        if(op==1)

        {

            scanf("%lld",&x);

            change(1,1,n,l,r,x);

        }

        else

            printf("%lld\n",query(1,1,n,l,r));

    }

    return 0;

}

2018.10.13

巴特西

picks loves segment tree I

picks loves segment tree I

题目背景

题目描述：

输入输出格式

输入格式

输出格式

说明：

最新文章

热门文章