欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

2018HDU多校2-1007-Naive Operations(hdu 6315)-线段树

程序员文章站 2022-03-13 19:28:05
...

2018HDU多校2-1007-Naive Operations(hdu 6315)-线段树

题意:

有两个数列,a和b,a初始全为0,b初始为给定值,对于a有两种操作,区间加1,区间求[ai/bi]的和

思路:

本题难点在于如何在log时间下实现区间修改,若用常规考虑,区间修改时遍历所以叶子结点,则需要n的时间,一定超时
对于线段树结点,记录最小值和最小值来源,初始将各叶子结点的最小值赋成b[i]的值,每次区间加1时,将对应最小值-1,利用懒惰标记思想,仅当某结点的最小值为0时,才向下搜索更新叶子结点
因为,只有当某区间最小值为0时,才表面该区间中有值+1,其余情况无需向下搜索
启示:线段树只能维护区间和,区间最值,若出现除此之外的操作,考虑通过组合或变形的方式实现

代码:

#include <iostream>
#include <string>
using namespace std;
#define lch rt<<1
#define rch (rt<<1)|1
typedef long long ll;
int b[100050];
struct node
{
    ll ans;
    int minn;
    int pos;
}Btree[5*100050];
int mark[4*100050];
void push_up(int rt)
{
    Btree[rt].ans=Btree[lch].ans+Btree[rch].ans;
    if(Btree[lch].minn>Btree[rch].minn)
    {
        Btree[rt].minn=Btree[rch].minn;
        Btree[rt].pos=1;
    }
    else if(Btree[lch].minn<Btree[rch].minn)
    {
        Btree[rt].minn=Btree[lch].minn;
        Btree[rt].pos=2;
    }
    else
    {
        Btree[rt].minn=Btree[lch].minn;
        Btree[rt].pos=3;
    }
}
void build(int l,int r,int rt)
{
   if(l>r) return ;
   if(l==r)
   {
       mark[rt]=0;
       Btree[rt].ans=0;
       Btree[rt].pos=0;
       Btree[rt].minn=b[l];
       return;
   }
   int mid=(l+r)>>1;
   mark[rt]=0;
   build(l,mid,lch);
   build(mid+1,r,rch);
   push_up(rt);
}
void push_down(int rt)
{
    if(mark[rt]!=0)
    {
        mark[lch]+=mark[rt];
        mark[rch]+=mark[rt];
        Btree[lch].minn-=mark[rt];
        Btree[rch].minn-=mark[rt];
        mark[rt]=0;
    }
}
void update(int L,int R,int l,int r,int rt)
{
    if(r<L || l>R) return;
    if(l>r) return;
    if(L<=l && r<=R)
    {
        Btree[rt].minn-=1;
        mark[rt]+=1;
        if(l==r)
        {
            mark[rt]=0;
            Btree[rt].ans+=Btree[rt].minn==0?1:0;
            Btree[rt].minn=Btree[rt].minn==0?b[l]:(Btree[rt].minn);
        }
        return ;
    }
    push_down(rt);
    int mid=(l+r)>>1;
    if(L<=mid) update(L,R,l,mid,lch);
    if(mid<R) update(L,R,mid+1,r,rch);
    push_up(rt);
}
void updateone(int l,int r,int rt)
{
    if(l>r) return ;
    if(l==r)
    {
        Btree[rt].ans+=Btree[rt].minn==0?1:0;
        Btree[rt].minn=Btree[rt].minn==0?b[l]:(Btree[rt].minn);
        return ;
    }
    push_down(rt);
    int mid=(l+r)>>1;
    if(Btree[rt].minn==0 && Btree[rt].pos>1 )
        updateone(l,mid,lch);
    if(Btree[rt].minn==0 && Btree[rt].pos%2)
        updateone(mid+1,r,rch);
    push_up(rt);
}
ll query(int L,int R,int l,int r,int rt)
{
    if(r<L || l>R) return 0;
    if(l>r) return 0;
    if(L<=l && r<=R)
        return Btree[rt].ans;
    push_down(rt);
    int mid=(l+r)>>1;
    ll res=0;
    if(L<=mid) res+=query(L,R,l,mid,lch);
    if(mid<R) res+=query(L,R,mid+1,r,rch);
    return res;
}
int main()
{
    std::ios::sync_with_stdio(false);
    int n,q;
    while(cin>>n>>q)
    {
        for(int i=1;i<=n;i++)
            cin>>b[i];
        build(1,n,1);
        for(int i=1;i<=q;i++)
        {
            string k;
            int l,r;
            cin>>k>>l>>r;
            if(k=="add")
            {
                update(l,r,1,n,1);
                updateone(1,n,1);
            }
            if(k=="query")
            {
                cout<<query(l,r,1,n,1)<<endl;
            }
        }
    }
    return 0;
}
相关标签: ACM