SAST_2020_team_B
Powered by Vijos
/ SAST_2020_team_B / 题库 / 小敏种树苗(Round 1) /

题解

2 条题解

  • 1
    @ 2021-01-28 16:55:43 
    #include<cstdio>
#include<iostream>
#define lson p<<1 
#define rson p<<1|1
using namespace std;
typedef long long ll;
 
const int MAXN=100005; 
 
struct Node{
    int l,r,lm,rm,ans;
    ll lv,rv;
    #define l(x) tre[x].l
    #define r(x) tre[x].r
    #define lm(x) tre[x].lm
    #define rm(x) tre[x].rm
    #define ans(x) tre[x].ans
    #define lv(x) tre[x].lv
    #define rv(x) tre[x].rv
}tre[MAXN<<2];

int n,q,a[MAXN];
ll lz[MAXN<<2];

int cal(int num)
{
    return (num+1)>>1;
}

void pushup(int p)
{
    if(rv(lson)!=lv(rson))
    {
        ans(p)=ans(lson)+ans(rson);
        ans(p)-=cal(rm(lson))+cal(lm(rson));
        ans(p)+=cal(rm(lson)+lm(rson)+1);
        if(lm(lson)==r(lson)-l(lson))
            lm(p)=lm(lson)+lm(rson)+1;
        else lm(p)=lm(lson);
        if(rm(rson)==r(rson)-l(rson))
            rm(p)=rm(rson)+rm(lson)+1;
        else rm(p)=rm(rson);
    }
    else
    {
        ans(p)=ans(lson)+ans(rson);
        lm(p)=lm(lson);
        rm(p)=rm(rson);
    }
    lv(p)=lv(lson);
    rv(p)=rv(rson);
}

void pushdown(int p)
{
    lv(lson)+=lz[p];
    rv(lson)+=lz[p];
    lv(rson)+=lz[p];
    rv(rson)+=lz[p];
    lz[lson]+=lz[p];
    lz[rson]+=lz[p];
    lz[p]=0;
}

void build_tree(int l,int r,int p)
{
    l(p)=l,r(p)=r;
    if(l==r)
    {
        lv(p)=rv(p)=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build_tree(l,mid,lson);
    build_tree(mid+1,r,rson);
    pushup(p);
}

void updat(int l,int r,ll k,int p)
{
    if(l(p)>r||r(p)<l)return;
    if(l(p)>=l&&r(p)<=r)
    {
        lz[p]+=k;
        lv(p)+=k;
        rv(p)+=k;
        return;
    }
    pushdown(p);
    updat(l,r,k,lson);
    updat(l,r,k,rson);
    pushup(p); 
}

Node query(int l,int r,int p)
{   
    if(l(p)>=l&&r(p)<=r)return tre[p];
    int mid=(l(p)+r(p))>>1;
    pushdown(p);
    if(r<=mid)return query(l,r,lson); 
    if(l>mid)return query(l,r,rson);
    Node lf=query(l,r,lson),ri=query(l,r,rson),un;
    if(lf.rv!=ri.lv)
    {
        un.ans=lf.ans+ri.ans;
        un.ans-=cal(lf.rm)+cal(ri.lm);
        un.ans+=cal(lf.rm+ri.lm+1);
        if(lf.lm==lf.r-lf.l)
            un.lm=lf.lm+ri.lm+1;
        else un.lm=lf.lm;
        if(ri.rm==ri.r-ri.l)
            un.rm=ri.rm+lf.rm+1;
        else un.rm=ri.rm;
    }
    else
    {
        un.ans=lf.ans+ri.ans;
        un.lm=lf.lm;
        un.rm=ri.rm;
    }
    un.lv=lf.lv;
    un.rv=ri.rv;
    un.l=lf.l;
    un.r=ri.r;
    return un;
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d",&a[i]);
    build_tree(1,n,1);
    scanf("%d",&q);
    for(int i=1;i<=q;++i)
    {
        int tp,s,t,h;
        scanf("%d",&tp);
        if(tp==1)
        {
            scanf("%d%d%d",&s,&t,&h);
            updat(s,t,h,1); 
        }
        else 
        {
            scanf("%d%d",&s,&t);
            Node fans=query(s,t,1);
            printf("%d\n",fans.ans);    
        }
    }
    
    return 0;
}
  • 0
    @ 2021-01-30 13:36:28

    理解题意

    这道题的模型是“ 给一段数列，询问最少去掉多少个数（形成断点）使剩下来连续的数相等”。
    比如“1 2 2 2 3 4 4”，去掉一些数后变为“1（）22（）44”，当然也可以变为“（）222（）44”。

    寻找规律

    设一段连续不相等的数有x个，如“1 2 3 2 1”，x=5。我们发现直接隔一个断掉一个就是答案。所以x/2就是最少断点数。 一段数列一定是由数个连续不相等的数和连续相等的数组成的。由于连续相等的数不需要断点，所以 答案就是将每一段连续不相等的数除以二相加（即x1/2+x2/2+……+xn/2）;

    解题

    但是题目中还加上了区间修改的操作，所以可以用线段树来维护。

    码风

    下面所给的代码，左右节点标号分别用lson、rson进行了宏定义，
    节点内储存的数据key全部用了 #define key(x) tre[x].key 这样的形式进行了宏定义

    存储

    假设我们已经知道线段树两个节点的答案，合并两个节点时只需要考虑两个节点相邻的两个数是否相等，如果相等，则两个节点答案互不影响，直接相加；如果不相等，就要重新计算一下合并后新出现的一段连续不相等数的断点数。所以每个节点需要存储最左、最右数（用于合并节点时比较）、答案、最左连续不相等数的个数、最右连续不相等数的个数（用于合并时重新计算）。

    合并

    合并时只需要判断左右节点相邻数是否相等。
    相等答案直接相加，左右最大连续数直接继承。

        ans(p)=ans(lson)+ans(rson);
    lm(p)=lm(lson);
    rm(p)=rm(rson);

    不相等时复杂一些，答案需要重新计算一下相邻部分连续不相等数。

        ans(p)=ans(lson)+ans(rson);
    ans(p)-=cal(rm(lson))+cal(lm(rson));//去掉原本连续不相等数的答案 
    ans(p)+=cal(rm(lson)+lm(rson));//加上重新计算出的答案 
    if(lm(lson)==r(lson)-l(lson)+1)//左节点全部连续不相等 
        lm(p)=lm(lson)+lm(rson);
    else lm(p)=lm(lson);
    if(rm(rson)==r(rson)-l(rson)+1)//右节点全部连续不相等 
        rm(p)=rm(rson)+rm(lson);
    else rm(p)=rm(rson);

    询问

    对于每次询问，递归下去直到找到完全包含的节点，并 将节点返回，将返回的节点依次合并（方法见“合并”一栏）。

    下面是完整代码

    #include<cstdio>
#include<iostream>
#define lson p<<1 
#define rson p<<1|1
using namespace std;
typedef long long ll;
 
const int MAXN=100005; 
 
struct Node{
    int l,r,lm,rm,ans;
    ll lv,rv;
    #define l(x) tre[x].l
    #define r(x) tre[x].r
    #define lm(x) tre[x].lm
    #define rm(x) tre[x].rm
    #define ans(x) tre[x].ans
    #define lv(x) tre[x].lv
    #define rv(x) tre[x].rv
}tre[MAXN<<2];

int n,q,a[MAXN];
ll lz[MAXN<<2];

int cal(int num)
{
    return num>>1;
}

void pushup(int p)
{
    if(rv(lson)!=lv(rson))//两个节点相邻数不相等 
    {
        ans(p)=ans(lson)+ans(rson);
        ans(p)-=cal(rm(lson))+cal(lm(rson));//去掉原本连续不相等数的答案 
        ans(p)+=cal(rm(lson)+lm(rson));//加上重新计算出的答案 
        if(lm(lson)==r(lson)-l(lson)+1)//左节点全部连续不相等 
            lm(p)=lm(lson)+lm(rson);
        else lm(p)=lm(lson);
        if(rm(rson)==r(rson)-l(rson)+1)//右节点全部连续不相等 
            rm(p)=rm(rson)+rm(lson);
        else rm(p)=rm(rson);
    }
    else
    {
        ans(p)=ans(lson)+ans(rson);
        lm(p)=lm(lson);
        rm(p)=rm(rson);
    }
    lv(p)=lv(lson);
    rv(p)=rv(rson);
}

void pushdown(int p)
{
    lv(lson)+=lz[p];
    rv(lson)+=lz[p];
    lv(rson)+=lz[p];
    rv(rson)+=lz[p];
    lz[lson]+=lz[p];
    lz[rson]+=lz[p];
    lz[p]=0;
}

void build_tree(int l,int r,int p)
{
    l(p)=l,r(p)=r;
    if(l==r)
    {
        lm(p)=rm(p)=1;
        lv(p)=rv(p)=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build_tree(l,mid,lson);
    build_tree(mid+1,r,rson);
    pushup(p);
}

void updat(int l,int r,ll k,int p)
{
    if(l(p)>r||r(p)<l)return;
    if(l(p)>=l&&r(p)<=r)
    {
        lz[p]+=k;
        lv(p)+=k;
        rv(p)+=k;
        return;
    }
    pushdown(p);
    updat(l,r,k,lson);
    updat(l,r,k,rson);
    pushup(p); 
}

Node query(int l,int r,int p)
{   
    if(l(p)>=l&&r(p)<=r)return tre[p];
    int mid=(l(p)+r(p))>>1;
    pushdown(p);
    if(r<=mid)return query(l,r,lson); 
    if(l>mid)return query(l,r,rson);
    Node lf=query(l,r,lson),ri=query(l,r,rson),un;
    if(lf.rv!=ri.lv)
    {
        un.ans=lf.ans+ri.ans;
        un.ans-=cal(lf.rm)+cal(ri.lm);
        un.ans+=cal(lf.rm+ri.lm);
        if(lf.lm==lf.r-lf.l+1)
            un.lm=lf.lm+ri.lm;
        else un.lm=lf.lm;
        if(ri.rm==ri.r-ri.l+1)
            un.rm=ri.rm+lf.rm;
        else un.rm=ri.rm;
    }
    else
    {
        un.ans=lf.ans+ri.ans;
        un.lm=lf.lm;
        un.rm=ri.rm;
    }
    un.lv=lf.lv;
    un.rv=ri.rv;
    un.l=lf.l;
    un.r=ri.r;
    return un;
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d",&a[i]);
    build_tree(1,n,1);
    scanf("%d",&q);
    for(int i=1;i<=q;++i)
    {
        int tp,s,t,h;
        scanf("%d",&tp);
        if(tp==1)
        {
            scanf("%d%d%d",&s,&t,&h);
            updat(s,t,h,1); 
        }
        else 
        {
            scanf("%d%d",&s,&t);
            Node fans=query(s,t,1);
            printf("%d\n",fans.ans);    
        }
    }
    
    return 0;
}
  • 1

小敏种树苗(Round 1)

信息

ID
1008
难度
9
分类
线段树 点击显示
标签
(无)
递交数
4
已通过
2
通过率
50%
被复制
1
上传者
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  1. © 2005 - 2023 Vijos.org
  2. uibuild-2f1065f
  3. 沪ICP备14040537号-1