Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 7822 Accepted Submission(s): 2347
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
【题解】
给你个01串。
有以下几种操作:
1.把[l.r]区间的所有数都置为0或1.
2.把[l,r]区间的所有数都置为其相反数.
3.求[l,r]区间内的1的个数.
4.求[l,r]区间内的最长的连续的'1'的个数.
求[l..r]区间内的1的个数，实际上就是对l..r这个区间求和.(只有0和1)
然后求l..r区间内的最长的连续的'1'的个数则需要一些技巧。
这样想。
一个区间l..r
把它分为左半部分l..m
和右半部分m+1..r
这个最长的所求序列。要么在左边。要么在右边。
要么有一部分在左边有一部分在右边。
于是我们设lx[rt]表示rt这个区间内的最长所求序列的长度；
则lx[rt] = max{lx[rt<<1],lx[rt<<1|1]};
然后对于横跨左右两边的情况。
我们需要记录lnum[rt],rnum[rt],表示这个区间最左边的数字和这个区间最右边的数字。
同时还要记录llx[rt],rlx[rt]，表示从区间的最左边的一个端点数起一共有多少个连续的1,以及从区间的最右边的一个端点数起一共有多少个连续的1.
如果rnum[rt<<1] == lnum[rt<<1|1] == 1;
则lx[rt]还有多一种更新即lx[rt] = max{lx[rt],rlx[rt<<1]+llx[rt<<1|1]};
但这还远远不够我们在进行取反操作之后重新更新这些值。
想想如果我们对一个区间取反了。要怎么重新确定llx[rt],rlx[rt],lx[rt]这些值？？？
0->1
1->0
启发我们可以多开一个域。记录有关0的连续序列的信息
即llx[0..1][rt],rlx[0..1][rt],lx[0..1][rt];
则我们取反之后swap(llx[1][rt],llx[0][rt])swap(rlx[1][rt] , rlx[0][rt])swap(lx[1][rt] , lx[0][rt]);
即有关0的连续的信息，有关1的连续的信息同时记录下来。
sum的话就直接等于len-sum了
具体的看代码；
处理区间的时候，左右端点都递增了1，这样就是1-n了不是0到n-1
【代码】
#include <cstdio>
#include <cstring>
#include <algorithm>
#define lson begin,m,rt<<1
#define rson m+1,end,rt<<1|1
using namespace std;
const int MAXN = 100100;
int n, m;
int llx[2][MAXN * 4], rlx[2][MAXN * 4], lx[2][MAXN * 4];
int sum[MAXN * 4], qufan[MAXN * 4], fugai[MAXN * 4],lnum[MAXN*4],rnum[MAXN*4];
void push_up(int rt, int len)
{
sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
for (int ii = 0; ii <= 1; ii++)//0和1的信息都要维护
{
bool flag = false;
if (rnum[rt << 1] == ii && lnum[rt << 1 | 1] == ii)
flag = true;
lx[ii][rt] = max(lx[ii][rt << 1], lx[ii][rt << 1 | 1]);
if (flag)
lx[ii][rt] = max(lx[ii][rt], rlx[ii][rt << 1] + llx[ii][rt << 1 | 1]);
llx[ii][rt] = llx[ii][rt << 1];
if (llx[ii][rt] == (len - (len >> 1)) && flag)//如果左区间都是一样的数字
llx[ii][rt] += llx[ii][rt << 1 | 1];//加上右区间的左半部分
rlx[ii][rt] = rlx[ii][rt << 1 | 1];
if (rlx[ii][rt] == len >> 1 && flag )
rlx[ii][rt] += rlx[ii][rt << 1];
}
lnum[rt] = lnum[rt << 1];
rnum[rt] = rnum[rt << 1 | 1];
}
void build(int begin, int end, int rt)
{
if (begin == end)
{
int x;
scanf("%d", &x);
for (int ii = 0; ii <= 1; ii++)
if (x == ii)
llx[ii][rt] = rlx[ii][rt] = lx[ii][rt] = 1;
else
llx[ii][rt] = rlx[ii][rt] = lx[ii][rt] = 0;
if (x == 0)
sum[rt] = 0, lnum[rt] = 0, rnum[rt] = 0;
else
sum[rt] = 1,lnum[rt] =1,rnum[rt] = 1;
return;
}
int m = (begin + end) >> 1;
build(lson);
build(rson);
push_up(rt,end-begin+1);
}
void input_data()
{
scanf("%d%d", &n, &m);
build(1, n, 1);
}
void init()//初始化
{
memset(fugai, 255, sizeof(fugai));
memset(qufan, 0, sizeof(qufan));
memset(llx, 0, sizeof(llx));
memset(sum, 0, sizeof(sum));
memset(rlx, 0, sizeof(rlx));
memset(lx, 0, sizeof(lx));
}
void tihuan(int rt, int len, int num)//把rt这个节点全部替换为num
{
sum[rt] = len*num;
lnum[rt] = rnum[rt] = num;
for (int ii = 0; ii <= 1; ii++)
if (num == ii)
llx[ii][rt] = rlx[ii][rt] = lx[ii][rt] = len;
else
llx[ii][rt] = rlx[ii][rt] = lx[ii][rt] = 0;
}
void change(int rt, int len) //把rt这个区间全部取反
{
swap(lx[0][rt], lx[1][rt]);
swap(llx[0][rt], llx[1][rt]);
swap(rlx[0][rt], rlx[1][rt]);
sum[rt] = len - sum[rt];
lnum[rt] = 1 - lnum[rt];
rnum[rt] = 1 - rnum[rt];
}
void pre_change(int rt,int len)//把rt区间取反
{
if (fugai[rt] != -1)
{
fugai[rt] = 1 - fugai[rt];
tihuan(rt, len, fugai[rt]);
}
else
{
qufan[rt] = 1 - qufan[rt];
change(rt, len);
}
}
void push_down(int rt, int len)
{
if (fugai[rt] != -1)
{
fugai[rt << 1] = fugai[rt << 1 | 1] = fugai[rt];
qufan[rt << 1] = qufan[rt << 1 | 1] = 0;
tihuan(rt << 1, len - (len >> 1), fugai[rt]);
tihuan(rt << 1 | 1, len >> 1, fugai[rt]);
fugai[rt] = -1;
}
else //如果有覆盖操作就不可能有取反操作(想想为什么)
if (qufan[rt]!=0)
{
pre_change(rt << 1, len - (len >> 1));
pre_change(rt << 1 | 1, len >> 1);
qufan[rt] = 0;
}
}
void up_data(int op, int l, int r, int begin, int end, int rt)
{
if (l <= begin && end <= r)
{
if (op <= 1) //覆盖操作
{
fugai[rt] = op;
qufan[rt] = 0;
tihuan(rt, end - begin + 1,op);
}
else //取反操作
pre_change(rt, end - begin + 1);
return;
}
push_down(rt, end - begin + 1);
int m = (begin + end) >> 1;
if (l <= m)
up_data(op, l, r, lson);
if (m < r)
up_data(op, l, r, rson);
push_up(rt, end - begin + 1);
}
int query_sum(int l, int r, int begin, int end, int rt)//求和
{
if (l <= begin && end <= r)
return sum[rt];
int dd = 0;
push_down(rt,end-begin+1);
int m = (begin + end) >> 1;
if (l <= m)
dd += query_sum(l, r, lson);
if (m < r)
dd += query_sum(l, r, rson);
return dd;
}
int query_lx(int l, int r, int begin, int end, int rt)//寻找最长连续1
{
if (l <= begin && end <= r)
return lx[1][rt];
push_down(rt, end - begin + 1);
int dd = 0;
int m = (begin + end) >> 1;
bool flag1 = false, flag2 = false;
if (l <= m)
{
dd = max(dd, query_lx(l, r, lson));
flag1 = true;
}
if (m < r)
{
dd = max(dd, query_lx(l, r, rson));
flag2 = true;
}
//在左边，在右边，横跨中间
if (flag1 && flag2 && rnum[rt << 1] == 1 && lnum[rt << 1 | 1] == 1)
{
int temp1 = min(m - l + 1, rlx[1][rt << 1]);
int temp2 = min(r - m, llx[1][rt << 1 | 1]);
dd = max(dd, temp1 + temp2);
}
return dd;
}
void output_ans()
{
for (int i = 1; i <= m; i++)
{
int op, x, y;
scanf("%d%d%d", &op, &x, &y);
x++; y++;
if (op <= 2)
up_data(op, x, y, 1, n, 1);
else
if (op == 3)
printf("%d
", query_sum(x, y, 1, n, 1));
else
if (op == 4)
printf("%d
", query_lx(x, y, 1, n, 1));
}
}
int main()
{
// freopen("F:\rush.txt", "r", stdin);
//freopen("F:\rush_out.txt", "w", stdut);
int t;
scanf("%d", &t);
while (t--)
{
init();
input_data();
output_ans();
}
return 0;
}