P6492 [COCI2010-2011#6] STEP(线段树)

P6492 [COCI2010-2011#6] STEP(线段树)

题目描述

给定一个长度为 n 的字符序列 a，初始时序列中全部都是字符 L。

有 q 次修改，每次给定一个 x，若 (a_x)为 L，则将 (a_x) 修改成 R，否则将 (a_x) 修改成 L。

对于一个只含字符 L，R 的字符串 s，若其中不存在连续的 L 和 R，则称 s 满足要求。

每次修改后，请输出当前序列 a 中最长的满足要求的连续子串的长度。

输入格式

第一行有两个整数，分别表示序列的长度 n 和修改操作的次数 q。

接下来 q 行，每行一个整数，表示本次修改的位置 x。

输出格式

对于每次修改操作，输出一行一个整数表示修改 a 中最长的满足要求的子串的长度。

分析

和维护最大子段和一样，线段树维护4个值：节点向左向右最远能拓展多少、节点的和、节点的答案，在pushup的时候更新即可。

const int N = 2e5+10;
int n,q,a[N];
struct seg{
  int l, r, lmx, rmx, sum, ans;
  inline int mid() {
    return (l+r) >> 1;
  }
}node[N<<2];

void up(int i) {
  node[i].sum = node[ls].sum + node[rs].sum;
  node[i].ans = max(node[ls].ans, node[rs].ans);
  node[i].lmx = node[ls].lmx;
  node[i].rmx = node[rs].rmx;
  if (a[node[ls].r] != a[node[rs].l]) {
    node[i].ans = max(node[i].ans, node[ls].rmx + node[rs].lmx);
    if (node[ls].lmx == node[ls].sum) {
      node[i].ans = max(node[i].ans, node[ls].lmx + node[rs].lmx);
      node[i].lmx = max(node[i].lmx, node[ls].lmx + node[rs].lmx);
    }
    if (node[rs].rmx == node[rs].sum) {
      node[i].ans = max(node[i].ans, node[ls].rmx + node[rs].rmx);
      node[i].rmx = max(node[i].rmx, node[rs].rmx + node[ls].rmx);
    }
  }
}

void build(int l, int r , int i) {
  node[i].l = l, node[i].r = r;
  if (l == r) {
    node[i].lmx = node[i].rmx = node[i].sum = 1;
    return;
  }
  int mid = (l+r) >> 1;
  build(l,mid,ls);
  build(mid+1,r,rs);
  up(i);
}

void modify(int p, int i) {
  if (node[i].l == p && p == node[i].r) {
    a[p] ^= 1;
    return;
  }
  int mid = node[i].mid();
  if (p <= mid) modify(p,ls);
  else modify(p,rs);
  up(i);
}

void run() {
  n = rd(), q = rd();
  build(1,n,1);
  rep(i,1,q) {
    int p = rd();
    modify(p,1);
    pnt(node[1].ans);
  }
}