本文共 3494 字，大约阅读时间需要 11 分钟。
正在入门线段树，做了几道题，都是比较侧重去考虑父节点与其子节点之间的关系，而本题不但要考虑父节点与子节点的关系，还要考虑相同父节点的子节点之间的关系。
本文是参考下面博客写的： https://blog.csdn.net/libin56842/article/details/14105071首先，我们要明确，父节点所维护的区间=左子节点维护的区间+右子节点维护的区间。其次，我们采用 由下到上、由深到浅 的思路去思考问题。
1**.从叶子节点开始考虑**，叶子节点所维护的区间是一个点，所以它维护的区间最大的连续区间长度要么为1，要么为0（被破坏了）； 2.接着考虑叶子节点的父节点，该父节点所维护的区间长度为2，所以它维护的区间最大的连续区间长度要么是整个区间，要么为左端点或右端点； 3.再继续考虑叶子节点的父节点的父节点，这时父节点所维护的区间长度为4，所以它所维护的区间最大连续区间长度要么是整个区间，要么是从左端点开始向右延伸的一段区间，或者是从右节点开始向左延伸的一段区间，亦或是中间那段区间，而中间这段区间的长度则是由其左子节点的右端点向左延伸的一段子区间+其右子节点的左端点向右延伸的一段子区间； 4.重复3。 归纳总结一下，可以得出结论：每个节点所维护的区间的最大连续区间长度就落在3当中黑体字的4种情况（1.2也可以归为3的情况），考虑到当最大长度为整个区间时，这时候相当于从左端点开始延伸至右端点，或者从右端点开始延伸至左端点，因此可以作进一步的归纳：每个节点所维护的区间中的最大连续区间长度，要么是从左端点向右延伸至某一位置，要么是从右端点向左延伸至某一位置，要么是中间某段连续的区间。 于是，我们树的节点除了维护l,r区间左右端点之外，还应该维护三个值： 1.从左端点向右延伸至某一位置，所形成的区间的长度l_to_r_max； 2.从右端点向左延伸至某一位置，所形成的区间的长度r_to_l_max； 3.该节点所维护的区间的最大连续区间的长度max_len。 那么push_up函数就可以写出来了： tr[root].l_to_r_max=tr[root<<1].l_to_r_max; tr[root].r_to_l_max=tr[root<<1|1].r_to_l_max; tr[root].max_len=max(max(tr[root<<1].max_len,tr[root<<1|1].max_len),tr[root<<1].l_to_r_max+tr[root<<1|1].r_to_l_max); 如果左子节点整个区间都是连续的话，还需： tr[root].l_to_r_max+=tr[root<<1|1].l_to_r_max. 如果右子节点整个区间都是连续的话，还需： tr[root].r_to_l_max+=tr[root<<1|1].r_to_l_max. 注意，我们不用另外去设置一个变量去维护中间某段连续区间的最大长度，因为这种情况已经包含在里面了（可自行理解一下）。 push_up函数已经写完，update函数也就不难了。那么接下来query函数应该如何写呢？ 假设当前访问到的节点为rt，所要求的节点为p，则有以下三种情况： 1.当前节点为叶子节点，或者最大连续区间长度为0，或者整个区间都连续，直接返回max_len； 2.设mid=(tr[rt].l+tr[rt].r)/2，若mid>=p，说明p落在rt的左子树内，查看左子树，此外，tr[rt<<1].r-tr[rt<<1].r_to_l_max+1代表左子树右边连续区间的左边界值，如果t在左子树的右区间内，则要看右子树的左区间有多长并返回，如果不在左子树的右边界区间内，则只需要看左子树。 3.若mid<p，同2. 代码如下：#include#include #include #include #include #include using namespace std;const int maxn=5e4+5;struct Node{ int l,r; int l_to_r_max,r_to_l_max; int max_len;}tr[maxn<<2];void push_up(int rt){ tr[rt].max_len=max(tr[rt<<1].max_len,max(tr[rt<<1|1].max_len,tr[rt<<1].r_to_l_max+tr[rt<<1|1].l_to_r_max)); tr[rt].l_to_r_max=tr[rt<<1].l_to_r_max; tr[rt].r_to_l_max=tr[rt<<1|1].r_to_l_max; if(tr[rt<<1].l_to_r_max==tr[rt<<1].r-tr[rt<<1].l+1) tr[rt].l_to_r_max+=tr[rt<<1|1].l_to_r_max; if(tr[rt<<1|1].r_to_l_max==tr[rt<<1|1].r-tr[rt<<1|1].l+1) tr[rt].r_to_l_max+=tr[rt<<1].r_to_l_max;}void build(int rt,int l,int r){ tr[rt].l=l; tr[rt].r=r; tr[rt].l_to_r_max=tr[rt].r_to_l_max=tr[rt].max_len=r-l+1; if(tr[rt].l==tr[rt].r) return; build(rt<<1,l,(l+r)>>1); build(rt<<1|1,((l+r)>>1)+1,r);}void update(int rt,int p,bool flag){ if(tr[rt].l==p&&tr[rt].r==p) { if(flag) tr[rt].l_to_r_max=tr[rt].r_to_l_max=tr[rt].max_len=0; else tr[rt].l_to_r_max=tr[rt].r_to_l_max=tr[rt].max_len=1; return; } int mid=(tr[rt].l+tr[rt].r)>>1; if(mid>=p) update(rt<<1,p,flag); else update(rt<<1|1,p,flag); push_up(rt);}int query(int rt,int p){ if(tr[rt].l==tr[rt].r||tr[rt].max_len==tr[rt].r-tr[rt].l+1||tr[rt].max_len==0) { return tr[rt].max_len; } int mid=(tr[rt].r+tr[rt].l)>>1; if(mid>=p) { if(tr[rt<<1].r-tr[rt<<1].r_to_l_max+1<=p) return query(rt<<1,p)+query(rt<<1|1,mid+1); return query(rt<<1,p); } else { if(tr[rt<<1|1].l+tr[rt<<1|1].l_to_r_max-1>=p) return query(rt<<1|1,p)+query(rt<<1,mid); return query(rt<<1|1,p); }}int main(){ int n,m; scanf("%d%d",&n,&m); build(1,1,n); stack st; while(m--) { char s[2]; scanf("%s",s); if(s[0]=='D') { int a; scanf("%d",&a); update(1,a,1); st.push(a); } else if(s[0]=='Q') { int a; scanf("%d",&a); printf("%d\n",query(1,a)); } else { if(!st.empty()) { update(1,st.top(),0); st.pop(); } } } return 0;}
很好的一道题，要理解好。