HDU 3397 Sequence operation

Problem Description

lxhgww got a sequence contains n characters which are all '0's or '1's.

We have five operations here:

Change operations:

0 a b change all characters into '0's in [a , b]

1 a b change all characters into '1's in [a , b]

2 a b change all '0's into '1's and change all '1's into '0's in [a, b]

Output operations:

3 a b output the number of '1's in [a, b]

4 a b output the length of the longest continuous '1' string in [a , b]

Input

T(T<=10) in the first line is the case number.

Each case has two integers in the first line: n and m (1 <= n , m <= 100000).

The next line contains n characters, '0' or '1' separated by spaces.

Then m lines are the operations:

op a b: 0 <= op <= 4 , 0 <= a <= b < n.

Output

For each output operation , output the result.

Sample Input

1
10 10
0 0 0 1 1 0 1 0 1 1
1 0 2
3 0 5
2 2 2
4 0 4
0 3 6
2 3 7
4 2 8
1 0 5
0 5 6
3 3 9      

Sample Output

5
2
6
5      

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn = 400005;
int n, m, T, l, r, x;

struct node
{
  int t1, t0, l, r, lr, rl, lf, rf, m0, m1;
  void add(int x)
  {
    m0 = m1 = t0 = t1 = 0;
    if (x) m1 = t1 = r - l + 1; else m0 = t0 = r - l + 1;
    lr = r; rl = l;
    lf = rf = x;
  }
  void change()
  {
    swap(t1, t0);
    swap(m0, m1);
    lf ^= 1;
    rf ^= 1;
  }
};

struct ST
{
  int y, sum[maxn];
  node f[maxn], ans;
  void merge(node &x, node &lx, node &rx)
  {
    x.t0 = lx.t0 + rx.t0;
    x.t1 = lx.t1 + rx.t1;
    x.lf = lx.lf;
    x.rf = rx.rf;
    if (lx.lr == lx.r&&lx.lf == rx.lf) x.lr = rx.lr; else x.lr = lx.lr;
    if (rx.rl == rx.l&&rx.rf == lx.rf) x.rl = lx.rl; else x.rl = rx.rl;
    x.m1 = max(lx.m1, rx.m1);
    if (lx.rf && rx.lf) x.m1 = max(x.m1, rx.lr - lx.rl + 1);
    x.m0 = max(lx.m0, rx.m0);
    if (!lx.rf && !rx.lf) x.m0 = max(x.m0, rx.lr - lx.rl + 1);
  }
  void build(int x, int l, int r)
  {
    f[x].l = l; f[x].r = r; sum[x] = -1;
    if (l == r)
    {
      scanf("%d", &y);
      f[x].add(y);
    }
    else
    {
      int mid = (l + r) >> 1;
      build(x + x, l, mid);
      build(x + x + 1, mid + 1, r);
      merge(f[x], f[x + x], f[x + x + 1]);
    }
  }
  void insert(int x, int l, int r, int ll, int rr, int v)
  {
    if (ll <= l && r <= rr)
    {
      if (sum[x] < 0 || v < 2) sum[x] = v;
      else if (sum[x] == 2) sum[x] = -1;
      else sum[x] ^= 1;
      if (v < 2) f[x].add(v);
      else f[x].change();
    }
    else
    {
      int mid = (l + r) >> 1;
      if (sum[x] >= 0)
      {
        insert(x + x, l, mid, l, r, sum[x]);
        insert(x + x + 1, mid + 1, r, l, r, sum[x]);
        sum[x] = -1;
      }
      if (ll <= mid) insert(x + x, l, mid, ll, rr, v);
      if (rr >mid) insert(x + x + 1, mid + 1, r, ll, rr, v);
      merge(f[x], f[x + x], f[x + x + 1]);
    }
  }
  void found(int x, int l, int r, int ll, int rr)
  {
    if (ll <= l && r <= rr) { 
      if (ans.l == 0) ans = f[x];
      else
      {
        node t = ans;
        merge(ans, t, f[x]);
      }
    }
    else
    {
      int mid = (l + r) >> 1;
      if (sum[x] >= 0)
      {
        insert(x + x, l, mid, l, r, sum[x]);
        insert(x + x + 1, mid + 1, r, l, r, sum[x]);
        sum[x] = -1;
      }
      if (ll <= mid) found(x + x, l, mid, ll, rr);
      if (rr >mid) found(x + x + 1, mid + 1, r, ll, rr);
      merge(f[x], f[x + x], f[x + x + 1]);
    }
  }
  int find(int l, int r, int x)
  {
    ans.l = 0;
    found(1, 1, n, l, r);
    if (x == 3) return ans.t1;
    else return ans.m1;
  }
}st;

int main()
{
  scanf("%d", &T);
  while (T--)
  {
    scanf("%d%d", &n, &m);
    st.build(1, 1, n);
    while (m--)
    {
      scanf("%d%d%d", &x, &l, &r);
      if (x <= 2) st.insert(1, 1, n, l + 1, r + 1, x);
      else printf("%d\n", st.find(l + 1, r + 1, x));
    }
  } 
  return 0;
}