Sequence operation

区间和并

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxn = 100005;

int N, M, a[maxn];

#define lson(x) ((x)<<1)
#define rson(x) (((x)<<1)|1)
struct Node {
  int l, r, filp, set;                      //左区间、右区间、取反 、记录输入的节点，-1已更新，1或0是向下更新的数值
  int lc[2], rc[2], sc[2];                  //0与1的前缀，0与1的后缀、0与1的区间最长
  int cnt[2];                               //0与1的总和

  int length() {                            //返回区间长度
    return r - l + 1;
  }
  void maintain(int d) {                    //统一更改标记
    set = d;
    filp = 0;
    for (int i = 0; i < 2; i++)
      lc[i] = rc[i] = sc[i] = cnt[i] = (i == d ? r - l + 1 : 0);      //维护四个
  }
  void splay() {
    if (set != -1)                         //未更新
      set ^= 1;                            //取反
    else                                   //已更新
      filp ^= 1;
                                           //四个全部交换
    swap(lc[0], lc[1]);
    swap(rc[0], rc[1]);
    swap(sc[0], sc[1]);
    swap(cnt[0], cnt[1]);
  }
}nd[maxn << 2];

void pushup(int u) {                      //上传
  for (int i = 0; i < 2; i++) {           //更新4个
    nd[u].cnt[i] = nd[lson(u)].cnt[i] + nd[rson(u)].cnt[i];
    nd[u].lc[i] = nd[lson(u)].lc[i] + (nd[lson(u)].lc[i] == nd[lson(u)].length() ?        nd[rson(u)].lc[i] : 0);     //如果左儿子的0或者以与区间长度相同，加上右儿子的
    nd[u].rc[i] = nd[rson(u)].rc[i] + (nd[rson(u)].rc[i] == nd[rson(u)].length() ? nd[lson(u)].rc[i] : 0);
    nd[u].sc[i] = max(max(nd[lson(u)].sc[i], nd[rson(u)].sc[i]), nd[lson(u)].rc[i] + nd[rson(u)].lc[i]);             //max（左儿子最长，右儿子最长，左儿子后缀与右儿子前缀）
  }
}

void pushdown (int u) {                //下传
  if (nd[u].filp) {                    //如果有取反标记
    nd[lson(u)].splay();
    nd[rson(u)].splay();
    nd[u].filp = 0;
  } else if (nd[u].set != -1) {        //统一标记向下更新
    nd[lson(u)].maintain(nd[u].set);
    nd[rson(u)].maintain(nd[u].set);
    nd[u].set = -1;
  }
}

void build(int u, int l, int r) {
  nd[u].l = l, nd[u].r = r;          //区间
  nd[u].filp = 0, nd[u].set = -1;    //取反标记、更新标记

  if (l == r) {
    nd[u].maintain(a[l]);
    return;
  }

  int mid = (l + r) / 2;
  build(lson(u), l, mid);
  build(rson(u), mid + 1, r);
  pushup(u);
}

void modify (int u, int l, int r, int v) {                             //统一更改函数
  if (l <= nd[u].l && nd[u].r <= r) {                                  //全覆盖
    nd[u].maintain(v);
    return;
  }

  pushdown(u);
  int mid = (nd[u].l + nd[u].r) / 2;
  if (l <= mid)
    modify(lson(u), l, r, v);
  if (r > mid)
    modify(rson(u), l, r, v);
  pushup(u);
}

void modify (int u, int l, int r) {                                   //取反函数
  if (l <= nd[u].l && nd[u].r <= r) {
    nd[u].splay();
    return;
  }

  pushdown(u);
  int mid = (nd[u].l + nd[u].r) / 2;
  if (l <= mid)
    modify(lson(u), l, r);
  if (r > mid)
    modify(rson(u), l, r);
  pushup(u);
}

int query_cnt(int u, int l, int r) {                                 //输出函数
  if (l <= nd[u].l && nd[u].r <= r)                                  //全覆盖
    return nd[u].cnt[1];                                             //向上传递

  pushdown(u);
  int mid = (nd[u].l + nd[u].r) / 2, ret = 0;
  if (l <= mid)
    ret += query_cnt(lson(u), l, r);                                 //累加
  if (r > mid)
    ret += query_cnt(rson(u), l, r);
  pushup(u);
  return ret;

}

int query_len(int u, int l, int r) {                               //输出1的最长长度
  if (l <= nd[u].l && nd[u].r <= r)
    return nd[u].sc[1];

  pushdown(u);
  int mid = (nd[u].l + nd[u].r) / 2, ret;
  if (r <= mid)                                                    //如果右区间小于等于中间值，只递归左儿子
    ret = query_len(lson(u), l, r);
  else if (l > mid)
    ret = query_len(rson(u), l, r);
  else {
    int ll = query_len(lson(u), l, r);
    int rr = query_len(rson(u), l, r);

    int A = min(nd[lson(u)].rc[1], mid - l + 1);
    int B = min(nd[rson(u)].lc[1], r - mid);
    ret = max(max(ll, rr), A + B);                                //左儿子最长1、右儿子最长1、左儿子后缀加右儿子前缀
  }
  pushup(u);
  return ret;
}

int main () {
  int cas;
  scanf("%d", &cas);               //测试次数
  while (cas--) {
    scanf("%d%d", &N, &M);         //测试数列长度、操作次数
    for (int i = 0; i < N; i++)
      scanf("%d", &a[i]);         //读取输入的数列
    build(1, 0, N - 1);           //建树

    int op, l, r;
    while (M--) {
      scanf("%d%d%d", &op, &l, &r);                              //操作
      if (op == 0)
        modify(1, l, r, 0);
      else if (op == 1)
        modify(1, l, r, 1);
      else if (op == 2)
        modify(1, l, r);
      else if (op == 3)
        printf("%d\n", query_cnt(1, l, r));
      else
        printf("%d\n", query_len(1, l, r));
    }
  }
  return 0;
}

笔记：取反标记的节点如果set标记非-1直接取反，否则将取反标记异或，查询区间和比较简单，寻找区间直接累计cnt，查询最长1的区间就麻烦一点，需要左右儿子的最长与左儿子后缀与右儿子前缀的和进行比较，取最大值