线段树区间合并板子

胡乱分析

区间合并操作指的是在给定的区间内，计算出例如10111011中的最大1的个数

分组解析

build操作

build操作与之前的求值的build操作一样，初始化的时候ls,rs,ms都是r+1-l初始化区间都是1

void build(int p,int l,int r)
{
  t[p].l=l;t[p].r=r;
  t[p].ls=t[p].rs=t[p].ms=r+1-l;
  if(l==r)
  return;
  int mid=(t[p].l+t[p].r)>>1;
  build(p<<1,l,mid);
  build(p<<1|1,mid+1,r);
}

change操作

这个题是单点的更改，change操作与之前不同的地方在于push_up操作原先的push_up仅仅只是把值修改一下这里修改的是区间的长度，所以有所不同
首先更新ls ls=左的ls
rs=右的rs
ms=等于左的ms右的ms和中间右左左右的加和的最大值
其中如果ls溢出那么加上右的左
rs溢出同理

void change(int p,int x,int y) //change函数
{
  if(t[p].l==t[p].r&&t[p].l==x)
  {
    t[p].ls=t[p].rs=t[p].ms=y;
    return;
  }
  int mid=(t[p].l+t[p].r)>>1;
  if(x<=mid)
  change(p<<1,x,y);
  else
  change(p<<1|1,x,y);
  //push up原先的push up是更改左右孩子的值之类的这里要进行区间的合并更改
  t[p].ls=t[p<<1].ls; //当前的左等于左孩子的左
  t[p].rs=t[p<<1|1].rs;//当前的右等于右孩子的右
  t[p].ms=max(max(t[p<<1].ms,t[p<<1|1].ms),t[p<<1].rs+t[p<<1|1].ls);//当前的总和等于左，右，中的最大值
  if(t[p<<1].ls==t[p<<1].r+1-t[p<<1].l)//如果左溢出加上右的左
  t[p].ls+=t[p<<1|1].ls;
  if(t[p<<1|1].rs==t[p<<1|1].r+1-t[p<<1|1].l)//如果右溢出加上左的右
  t[p].rs+=t[p<<1].rs;
}

sum操作

这里的sum求的是包含这个点的最大的区间长度所以如果到点了或者满了或者没有那么就返回即可
然后分左右合并，如果满了就加上即可跟change的感觉差不多

int sum(int p,int x)
{
  if(t[p].l==t[p].r||t[p].ms==0||t[p].ms==t[p].r+1-t[p].l)
  return t[p].ms;
  int mid=(t[p].l+t[p].r)>>1;
  if(x<=mid)
  {
    if(x>=t[p<<1].r+1-t[p<<1].rs)//如果溢出加上右边
    return sum(p<<1,x)+sum(p<<1|1,mid+1);
    else
    return sum(p<<1,x);
  }
  else
  {
    if(x<=t[p<<1|1].l+t[p<<1|1].ls-1)//如果溢出加上左边
    return sum(p<<1|1,x)+sum(p<<1,mid);
    else
    return sum(p<<1|1,x);
  }
}

完整代码(hdu-1540)

#include <bits/stdc++.h>
using namespace std;
struct node
{
  int l,r,ls,rs,ms;
}t[200005];
stack<int> st;
void build(int p,int l,int r) //递归构造树
{
  t[p].l=l;t[p].r=r;
  t[p].ls=t[p].rs=t[p].ms=r+1-l;
  if(l==r)
  return;
  int mid=(t[p].l+t[p].r)>>1;
  build(p<<1,l,mid);
  build(p<<1|1,mid+1,r);
}
void change(int p,int x,int y) //change函数
{
  if(t[p].l==t[p].r&&t[p].l==x)
  {
    t[p].ls=t[p].rs=t[p].ms=y;
    return;
  }
  int mid=(t[p].l+t[p].r)>>1;
  if(x<=mid)
  change(p<<1,x,y);
  else
  change(p<<1|1,x,y);
  //push up原先的push up是更改左右孩子的值之类的这里要进行区间的合并更改
  t[p].ls=t[p<<1].ls; //当前的左等于左孩子的左
  t[p].rs=t[p<<1|1].rs;//当前的右等于右孩子的右
  t[p].ms=max(max(t[p<<1].ms,t[p<<1|1].ms),t[p<<1].rs+t[p<<1|1].ls);//当前的总和等于左，右，中的最大值
  if(t[p<<1].ls==t[p<<1].r+1-t[p<<1].l)//如果左溢出加上右的左
  t[p].ls+=t[p<<1|1].ls;
  if(t[p<<1|1].rs==t[p<<1|1].r+1-t[p<<1|1].l)//如果右溢出加上左的右
  t[p].rs+=t[p<<1].rs;
}
int sum(int p,int x)
{
  if(t[p].l==t[p].r||t[p].ms==0||t[p].ms==t[p].r+1-t[p].l)
  return t[p].ms;
  int mid=(t[p].l+t[p].r)>>1;
  if(x<=mid)
  {
    if(x>=t[p<<1].r+1-t[p<<1].rs)//如果溢出加上右边
    return sum(p<<1,x)+sum(p<<1|1,mid+1);
    else
    return sum(p<<1,x);
  }
  else
  {
    if(x<=t[p<<1|1].l+t[p<<1|1].ls-1)//如果溢出加上左边
    return sum(p<<1|1,x)+sum(p<<1,mid);
    else
    return sum(p<<1|1,x);
  }
}
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n,m;
  while(cin>>n>>m)
  {
    memset(t,0,sizeof(t));
    build(1,1,n);
    while(m--)
    {
      char c;
      int x;
      cin>>c;
      if(c=='D')
      {
        cin>>x;
        change(1,x,0);
        st.push(x);
      }
      else if(c=='R')
      {
        change(1,st.top(),1);
        st.pop();
      }
      else
      {
        cin>>x;
        cout<<sum(1,x)<<"\n";
      }
    }
  }
}