众所周知,splay序列树是一个非常nb的维护区间的大杀器。
关于splay维护区间的操作,蒟蒻在线求教qwq
求区间和
void update(int x){
sz[x]=sz[lc]+sz[rc]+1;
sum[x]=sum[lc]+sum[rc]+val[x];
lmax[x]=max(lmax[lc],sum[lc]+val[x]+max(lmax[rc],0));
rmax[x]=max(rmax[rc],sum[rc]+val[x]+max(rmax[lc],0));
mmax[x]=max(max(mmax[lc],mmax[rc]),val[x]+max(lmax[rc],0)+max(rmax[lc],0));
return ;
}
Q1 : 那么怎么根据这个写出求 一个01串中 l−r 的区间最长连续的1串
Q2 : 那么怎么根据这个写出求 一个序列中 l−r 的区间最长上升子序列