Description
lxhgww 最近收到了一个 01 序列, 序列里面包含了 \(n\) 个数, 这些数要么是 \(0\), 要么是 \(1\), 现在对于这个序列有五种变换操作和询问操作:
0 a b把 \([a, b]\) 区间内的所有数全变成 \(0\)1 a b把 \([a, b]\) 区间内的所有数全变成 \(1\)2 a b把 \([a, b]\) 区间内的所有数全部取反, 也就是说把所有的 \(0\) 变成 \(1\), 把所有的 \(1\) 变成 \(0\)3 a b询问 \([a, b]\) 区间内总共有多少个 \(1\)4 a b询问 \([a, b]\) 区间内最多有多少个连续的 \(1\)
对于每一种询问操作, lxhgww 都需要给出回答, 聪明的程序员们, 你们能帮助他吗?
Input
输入数据第一行包括 \(2\) 个数,\(n\) 和 \(m\), 分别表示序列的长度和操作数目.
第二行包括 \(n\) 个数, 表示序列的初始状态.
接下来 \(m\) 行, 每行 \(3\) 个数,\(op, a, b (0 \leq op \leq 4, 0 \leq a \leq b \lt n)\) 表示对于区间 \([a, b]\) 执行标号为 \(op\) 的操作
Output
对于每一个询问操作, 输出一行, 包括 \(1\) 个数, 表示其对应的答案
Sample Input
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 9Sample Output
5
2
6
5Data Range
对于 30% 的数据,\(1 \leq n, m \leq 1000\)
对于 100% 的数据,\(1 \leq n, m \leq 10^5\)
Explanation
看到区间操作当然是直接水线段树了~
只不过这个 RMQ 线段树比较难搞就是了. 我们需要记一堆东西, 包括每段区间内所有 \(0\) 和 \(1\) 的数量 (不然就没法用区间取反操作了, 需要重新算一遍). 与此同时还需要有关于 最长的连续 0-1 串的长度 (当然两种也都要记), 其中还要分情况讨论: 从头开始的, 以尾结束的, 和不一定从头开始或以尾结束的, 这样就可以保存一些状态, 保证每一次的任何 操作都不超过 \(O(\log n)\).
另外关于下传标记的事情, 我们是不能允许两个 flag 同时处在一个节点上的, 因为这样的话我们不知道应该先处理哪一个 flag (得到的结果显然是不一样的). 所以在添加 flag 的时候我特判了一下然后豫先把两个 flag 分类讨论了一下.
最后写出来的程序还是比较快的 (没有本题第一快, 那个人太神了)
Source Code
#include <iostream>
#include <cstdlib>
#include <cstdio>
#define max_3(_x,_y,_z) (max(max((_x),(_y)),(_z)))
#define rep(_var,_begin,_end) for(int _var=_begin;_var<=_end;_var++)
#define range(_begin,_end) rep(_,_begin,_end)
#define range_(_begin,_end) rep(__,_begin,_end)
using namespace std;
typedef long long lli;
const int maxn = 300100; // Should > 262144
class SegmentTree
{
public:
int n, lbnd[maxn], rbnd[maxn];
int lazy_rev[maxn], // 0 for not reversing and vice versa
lazy_val[maxn]; // 0 for changing to 0, 1 for changing to 1, and 2 for not changing
int cnt[maxn][2], // Count of numbers in range
len[maxn][2][3]; // Maximum length of # from 0: left, 1: middle, 2: right
#define lc(_x) (2*(_x))
#define rc(_x) (2*(_x)+1)
#define siz(_x) (rbnd[_x]-lbnd[_x]+1)
void update_data(int p)
{
range(0,1) cnt[p][_] = cnt[lc(p)][_] + cnt[rc(p)][_];
range(0,1) {
len[p][_][0] = len[lc(p)][_][0] == siz(lc(p)) ?
siz(lc(p)) + len[rc(p)][_][0] :
len[lc(p)][_][0];
len[p][_][1] = max_3( len[lc(p)][_][2] + len[rc(p)][_][0],
len[lc(p)][_][1], len[rc(p)][_][1] );
len[p][_][2] = len[rc(p)][_][2] == siz(rc(p)) ?
siz(rc(p)) + len[lc(p)][_][2] :
len[rc(p)][_][2]; // There could have been a [_][1];...
}
return ;
}
void set_value(int p, int val)
{
if (lazy_rev[p])
lazy_rev[p] = false;
lazy_val[p] = val;
cnt[p][val] = siz(p);
cnt[p][!val] = 0;
range(0,2) len[p][val][_] = siz(p),
len[p][!val][_] = 0;
return ;
}
void set_reverse(int p)
{
if (lazy_val[p] != 2) {
set_value(p, !lazy_val[p]);
return ;
}
lazy_rev[p] ^= 1;
swap(cnt[p][0], cnt[p][1]);
range(0,2) swap(len[p][0][_], len[p][1][_]);
return ;
}
void dispatch_lazy(int p)
{
// Reverse values?
if (lazy_rev[p]) {
range(lc(p),rc(p))
set_reverse(_);
lazy_rev[p] = false;
}
// Set entire data to specific value
if (lazy_val[p] != 2) {
int val = lazy_val[p];
range(lc(p),rc(p))
set_value(_, val);
lazy_val[p] = 2;
}
return ;
}
void build_tree(int n_, int arr[])
{
n = 1; while (n < n_) n *= 2;
// Uniting arr[] checking and out-of-bound situations
for (int i = 1; i <= n; i++) {
int j = i + n - 1;
lbnd[j] = rbnd[j] = i;
lazy_rev[j] = false, lazy_val[j] = 2;
if (i > n_ || arr[i] == 0) {
cnt[j][0] = 1, cnt[j][1] = 0;
range(0,2) len[j][0][_] = 1, len[j][1][_] = 0;
} else {
cnt[j][0] = 0, cnt[j][1] = 1;
range(0,2) len[j][0][_] = 0, len[j][1][_] = 1;
}
}
// Continue build the rest of the stuff
for (int i = n - 1; i >= 1; i--) {
lbnd[i] = lbnd[lc(i)], rbnd[i] = rbnd[rc(i)];
lazy_rev[i] = false, lazy_val[i] = 2;
update_data(i);
}
return ;
}
int query_cnt(int p, int l, int r)
{
if (lbnd[p] == l && rbnd[p] == r)
return cnt[p][1];
dispatch_lazy(p);
if (r <= rbnd[lc(p)])
return query_cnt(lc(p), l, r);
else if (l >= lbnd[rc(p)])
return query_cnt(rc(p), l, r);
else return query_cnt(lc(p), l, rbnd[lc(p)]) +
query_cnt(rc(p), lbnd[rc(p)], r);
return 0;
}
int query_cnt(int l, int r)
{
return query_cnt(1, l, r);
}
int query_len(int p, int l, int r, int v)
{
if (lbnd[p] == l && rbnd[p] == r)
return len[p][1][v];
dispatch_lazy(p);
if (r <= rbnd[lc(p)]) {
return query_len(lc(p), l, r, v);
} else if (l >= lbnd[rc(p)]) {
return query_len(rc(p), l, r, v);
} else {
if (v == 0) { int llen = query_len(lc(p), l, rbnd[lc(p)], 0);
if (llen >= rbnd[lc(p)] - l + 1) llen += query_len(rc(p), lbnd[rc(p)], r, 0);
return llen; }
else if (v == 1) { return max_3( query_len(lc(p), l, rbnd[lc(p)], 1),
query_len(rc(p), lbnd[rc(p)], r, 1),
query_len(lc(p), l, rbnd[lc(p)], 2) + query_len(rc(p), lbnd[rc(p)], r, 0) ); }
else if (v == 2) { int rlen = query_len(rc(p), lbnd[rc(p)], r, 2);
if (rlen >= r - lbnd[rc(p)] + 1) rlen += query_len(lc(p), l, rbnd[lc(p)], 2);
return rlen; }
}
return 0;
}
int query_len(int l, int r)
{
return max_3(query_len(1, l, r, 0),
query_len(1, l, r, 1),
query_len(1, l, r, 2));
}
void change(int p, int l, int r, int v)
{
if (lbnd[p] == l && rbnd[p] == r) {
if (v == 0 || v == 1)
set_value(p, v);
else if (v == 2)
set_reverse(p);
return ;
}
dispatch_lazy(p);
if (r <= rbnd[lc(p)])
change(lc(p), l, r, v);
else if (l >= lbnd[rc(p)])
change(rc(p), l, r, v);
else change(lc(p), l, rbnd[lc(p)], v),
change(rc(p), lbnd[rc(p)], r, v);
update_data(p);
return ;
}
void change_val(int l, int r, int v)
{
change(1, l, r, v);
}
void change_reverse(int l, int r)
{
change(1, l, r, 2);
}
} st;
int n, m;
int arr[maxn];
int main(int argc, char** argv)
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%d", &arr[i]);
st.build_tree(n, arr);
for (int i = 1; i <= m; i++) {
int op, a, b;
scanf("%d%d%d", &op, &a, &b);
a++, b++; // Incompatibility between two different styles.
if (op == 0)
st.change_val(a, b, 0);
else if (op == 1)
st.change_val(a, b, 1);
else if (op == 2)
st.change_reverse(a, b);
else if (op == 3)
printf("%d\n", st.query_cnt(a, b));
else if (op == 4)
printf("%d\n", st.query_len(a, b));
}
return 0;
}