2018HDU多校2-1007-Naive Operations(hdu 6315)-线段树
程序员文章站
2022-03-13 19:28:05
...
题意:
有两个数列,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;
}
上一篇: UVa272 - TEX Quotes
下一篇: 爆笑二货,超有吸引力
推荐阅读
-
HDU6315 Naive Operations(线段树 复杂度分析)
-
HDU6315 Naive Operations(多校第二场1007)(线段树)
-
HDU6315 Naive Operations(线段树 复杂度分析)
-
HDU 6338 2018HDU多校赛 第四场 Depth-First Search(组合数学+平衡树/pbds)
-
HDU 6356 Glad You Came 线段树或反向RMQ 2018杭电多校第五场
-
HDU6406 Taotao Picks Apples(2018HDU多校联赛第八场,线段树)
-
HDU 6393 2018HDU多校赛 第七场 Traffic Network in Numazu(树链剖分 + 树状数组)
-
HDU6356 Glad You Came(2018HDU多校联赛第五场,线段树)
-
2018HDU多校8-1010-Taotao Picks Apples(hdu 6406)-线段树+预处理
-
HDU6315 Naive Operations(多校第二场1007)(线段树)