lxzy_ @ 2020-10-25 00:53:28
想问一下各位大佬这样子写行吗:
inline int Change(int k,int pos)
{
Segment_Tree t;
t.sum=s[k<<1].sum+s[k<<1|1].sum;
t.left=Max(s[k<<1].left,s[k<<1].sum+s[k<<1|1].left);
t.right=Max(s[k<<1|1].right,s[k<<1|1].sum+s[k<<1].right);
t.cal=Max(s[k<<1].sum,Max(s[k<<1|1].sum,s[k<<1].right+s[k<<1|1].left));
if(pos==0) s[k]=t;
else return t.cal;
}
inline void Update(int k,int l,int r,int p,int v)
{
if(l==r){
if(l!=p) return ;
s[k].sum=v;
s[k].cal=v;
s[k].left=v;
s[k].right=v;
return ;
}
int mid=(l+r)>>1;
Update(k<<1,l,mid,p,v);
Update(k<<1|1,mid+1,r,p,v);
Change(k,0);
}
inline int Query(int k,int l,int r,int x,int y)
{
if(x>r||y<l) return 0;
if(x<=l&&r<=y) return s[k].cal;
int mid=(l+r)>>1;
return Change(k,1);
}
by lxzy_ @ 2020-10-25 00:54:09
就是把修改中的合并区间和查询中的合并答案写到一个Changeh函数里面了
by pocafup @ 2020-10-25 05:43:12
这个查询我真没看懂/fad
而且如果不是完整区间你不push先儿子怎么会有标记啊
by lxzy_ @ 2020-10-25 09:37:04
@pocafup 啊这不是单点修改吗,不用标记下传吧?
by pocafup @ 2020-10-25 10:46:28
@Longest_Journey 没认真看,update的问题是我疏忽了,但你查询是严格O(1)珂海星(
by lxzy_ @ 2020-10-25 12:30:23
@pocafup 啊这,貌似是的(
by lxzy_ @ 2020-10-25 12:30:40
谢谢大佬orz