Sequence operation
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 6503 Accepted Submission(s): 1937
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]
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.
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
Author
lxhgww&&shǎ崽
Source
HDOJ Monthly Contest – 2010.05.01
这题要维护的东西很多, 区间左边连续1的个数,区间右边连续1的个数, 区间最长连续1的长度,区间1的个数,区间左边连续0个数,区间右边连续0个数,区间最长连续0长度,区间0的个数,还有延迟标记
对于延迟标记:如果原来没标记,那么把现在的标记覆盖上去
如果现在的标记是0或1 (把区间变成0或1),无论之前是什么,直接覆盖上去
如果现在的标记是2(翻转), 之前是2,那么2次翻转等于没翻,标记清掉,之前是0, 那么先把区间变成0,再翻转,相当于把区间变成1,也就是标记1
之间是1,那么先把区间变成1,再翻转,相当于把区间变成0,也就是标记0,有了这些就好写了
之间是1,那么先把区间变成1,再翻转,相当于把区间变成0,也就是标记0,有了这些就好写了
/*************************************************************************
> File Name: hdu3397.cpp
> Author: ALex
> Mail: 405045132@qq.com
> Created Time: 2015年01月11日 星期日 12时51分06秒
************************************************************************/
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int sta[N];
struct node
{
int l, r;
int cnt0, cnt1;
int l1, r1, l0, r0;
int len1, len0;
int add;
}tree[N << 2];
void pushup (int p)
{
tree[p].l1 = tree[p << 1].l1;
tree[p].r1 = tree[p << 1 | 1].r1;
tree[p].cnt1 = tree[p << 1].cnt1 + tree[p << 1 | 1].cnt1;
if (tree[p << 1].l1 == tree[p << 1].r - tree[p << 1].l + 1)
{
tree[p].l1 += tree[p << 1 | 1].l1;
}
if (tree[p << 1 | 1].r1 == tree[p << 1 | 1].r - tree[p << 1 | 1].l + 1)
{
tree[p].r1 += tree[p << 1].r1;
}
tree[p].len1 = max( max(tree[p << 1].len1, tree[p << 1 | 1].len1), tree[p << 1].r1 + tree[p << 1 | 1].l1 );
tree[p].l0 = tree[p << 1].l0;
tree[p].r0 = tree[p << 1 | 1].r0;
tree[p].cnt0 = tree[p << 1].cnt0 + tree[p << 1 | 1].cnt0;
if (tree[p << 1].l0 == tree[p << 1].r - tree[p << 1].l + 1)
{
tree[p].l0 += tree[p << 1 | 1].l0;
}
if (tree[p << 1 | 1].r0 == tree[p << 1 | 1].r - tree[p << 1 | 1].l + 1)
{
tree[p].r0 += tree[p << 1].r0;
}
tree[p].len0 = max ( max(tree[p << 1].len0, tree[p << 1 | 1].len0), tree[p << 1].r0 + tree[p << 1 | 1].l0 );
}
void pushdown (int p)
{
if (tree[p].add != -1)
{
if (tree[p].add == 0) //把区间变成0
{
tree[p << 1].len1 = tree[p << 1].l1 = tree[p << 1].r1 = tree[p << 1].cnt1 = 0;
tree[p << 1].len0 = tree[p << 1].l0 = tree[p << 1].r0 = tree[p << 1].cnt0 = tree[p << 1].r - tree[p << 1].l + 1;
tree[p << 1 | 1].len1 = tree[p << 1 | 1].l1 = tree[p << 1 | 1].r1 = tree[p << 1 | 1].cnt1 = 0;
tree[p << 1 | 1].len0 = tree[p << 1 | 1].l0 = tree[p << 1 | 1].r0 = tree[p << 1 | 1].cnt0 = tree[p << 1 | 1].r - tree[p << 1 | 1].l + 1;
tree[p << 1].add = 0;
tree[p << 1 | 1].add = 0;
}
else if (tree[p].add == 1) //把区间变成1
{
tree[p << 1].len1 = tree[p << 1].l1 = tree[p << 1].r1 = tree[p << 1].cnt1 = tree[p << 1].r - tree[p << 1].l + 1;
tree[p << 1].len0 = tree[p << 1].l0 = tree[p << 1].r0 = tree[p << 1].cnt0 = 0;
tree[p << 1 | 1].len1 = tree[p << 1 | 1].l1 = tree[p << 1 | 1].r1 = tree[p << 1 | 1].cnt1 = tree[p << 1 | 1].r - tree[p << 1 | 1].l + 1;
tree[p << 1 | 1].len0 = tree[p << 1 | 1].l0 = tree[p << 1 | 1].r0 = tree[p << 1 | 1].cnt0 = 0;
tree[p << 1].add = 1;
tree[p << 1 | 1].add = 1;
}
else
{
swap (tree[p << 1].len1, tree[p << 1].len0);
swap (tree[p << 1].l1, tree[p << 1].l0);
swap (tree[p << 1].r1, tree[p << 1].r0);
swap (tree[p << 1].cnt1, tree[p << 1].cnt0);
swap (tree[p << 1 | 1].len1, tree[p << 1 | 1].len0);
swap (tree[p << 1 | 1].l1, tree[p << 1 | 1].l0);
swap (tree[p << 1 | 1].r1, tree[p << 1 | 1].r0);
swap (tree[p << 1 | 1].cnt1, tree[p << 1 | 1].cnt0);
if (tree[p << 1].add == -1)
{
tree[p << 1].add = 2;
}
else if (tree[p << 1].add == 2)
{
tree[p << 1].add = -1;
}
else if (tree[p << 1].add == 0)
{
tree[p << 1].add = 1;
}
else
{
tree[p << 1].add = 0;
}
if (tree[p << 1 | 1].add == -1)
{
tree[p << 1 | 1].add = 2;
}
else if (tree[p << 1 | 1].add == 2)
{
tree[p << 1 | 1].add = -1;
}
else if (tree[p << 1 | 1].add == 0)
{
tree[p << 1 | 1].add = 1;
}
else
{
tree[p << 1 | 1].add = 0;
}
}
tree[p].add = -1;
}
}
void build (int p, int l, int r)
{
tree[p].l = l;
tree[p].r = r;
tree[p].add = -1;
if (l == r)
{
if (sta[l])
{
tree[p].l1 = tree[p].r1 = tree[p].len1 = 1;
tree[p].l0 = tree[p].r0 = tree[p].len0 = 0;
tree[p].cnt0 = 0;
tree[p].cnt1 = 1;
}
else
{
tree[p].l1 = tree[p].r1 = tree[p].len1 = 0;
tree[p].l0 = tree[p].r0 = tree[p].len0 = 1;
tree[p].cnt0 = 1;
tree[p].cnt1 = 0;
}
return;
}
int mid = (l + r) >> 1;
build (p << 1, l, mid);
build (p << 1 | 1, mid + 1,r);
pushup (p);
}
void update (int p, int l, int r, int x)
{
if (l == tree[p].l && tree[p].r == r)
{
if (x == 0)
{
tree[p].l0 = tree[p].r0 = tree[p].len0 = tree[p].cnt0 = tree[p].r - tree[p].l + 1;
tree[p].l1 = tree[p].r1 = tree[p].len1 = tree[p].cnt1 = 0;
tree[p].add = 0;
}
else if (x == 1)
{
tree[p].l0 = tree[p].r0 = tree[p].len0 = tree[p].cnt0 = 0;
tree[p].l1 = tree[p].r1 = tree[p].len1 = tree[p].cnt1 = tree[p].r - tree[p].l + 1;
tree[p].add = 1;
}
else
{
swap (tree[p].l1, tree[p].l0);
swap (tree[p].r1, tree[p].r0);
swap (tree[p].len1, tree[p].len0);
swap (tree[p].cnt1, tree[p].cnt0);
if (tree[p].add == -1)
{
tree[p].add = 2;
}
else if (tree[p].add == 2)
{
tree[p].add = -1;
}
else if (tree[p].add == 1)
{
tree[p].add = 0;
}
else
{
tree[p].add = 1;
}
}
return;
}
pushdown (p);
int mid = (tree[p].l + tree[p].r) >> 1;
if (r <= mid)
{
update (p << 1, l, r, x);
}
else if (l > mid)
{
update (p << 1 | 1, l, r, x);
}
else
{
update (p << 1, l, mid, x);
update (p << 1 | 1, mid + 1, r, x);
}
pushup (p);
// printf("区间[%d, %d] 左边1 %d, 右边1 %d, 左边0 %d, 右边0 %d, 1个数 %d, 0个数 %d\n", tree[p].l, tree[p].r, tree[p].l1, tree[p].r1, tree[p].l0, tree[p].r0, tree[p].cnt1, tree[p].cnt0);
}
int query (int p, int l, int r, int x)
{
if (tree[p].l == l && tree[p].r == r)
{
if (x == 3)
{
return tree[p].cnt1;
}
else
{
return tree[p].len1;
}
}
pushdown (p);
int mid = (tree[p].l + tree[p].r) >> 1;
if (r <= mid)
{
return query (p << 1, l, r, x);
}
else if (l > mid)
{
return query (p << 1 | 1, l, r, x);
}
else
{
if (x == 3)
{
return query (p << 1, l, mid, x) + query (p << 1 | 1, mid + 1, r, x);
}
else
{
int ret = 0;
if (l >= mid - tree[p << 1].r1 + 1 && r <= mid + tree[p << 1 | 1].l1)
{
ret = r - l + 1;
}
else if (l < mid - tree[p << 1].r1 + 1 && r <= mid + tree[p << 1 | 1].l1)
{
int s = mid - tree[p << 1].r1 + 1;
ret = max (r - s + 1, query (p << 1, l, mid, x));
}
else if (l >= mid - tree[p << 1].r1 + 1 && r > mid + tree[p << 1 | 1].l1)
{
int e = mid + tree[p << 1 | 1].l1;
ret = max (e - l + 1, query (p << 1 | 1, mid + 1, r, x));
}
else
{
ret = max(tree[p << 1 | 1].l1 + tree[p << 1].r1, max(query (p << 1, l, mid, x), query (p << 1 | 1, mid + 1, r, x)));
}
return ret;
}
}
}
int main()
{
int t;
int x, l, r;
scanf("%d", &t);
while (t--)
{
int n, m;
scanf("%d%d", &n, &m);
for (int i = 0; i < n; ++i)
{
scanf("%d", &sta[i]);
}
build (1, 0, n - 1);
while (m--)
{
scanf("%d%d%d", &x, &l, &r);
if (x >= 0 && x <= 2)
{
update (1, l, r, x);
}
else
{
printf("%d\n", query (1, l, r, x));
}
}
}
return 0;
}