hdu3397 Sequence operation

 #include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+;
struct node {
/// l,r表示当前结点区间范围[l,r]
int l, r;
/// val=0时为全0标志,表示区间[l,r]的值全为0
/// val=1时为全1标志,表示区间[l,r]的值全为1
/// val=-1时则代表无操作
/// xor为异或标志,表示区间[l,r]的值取异或操作
int val, Xor;
/// lmax_0表示区间[l,r]从左往右开始连续0的个数
/// rmax_0表示区间[l,r]从右往左开始连续0的个数
/// max_0表示当前区间最大连续0的个数
int lmax_0, rmax_0, max_0, sum_0;
int lmax_1, rmax_1, max_1, sum_1;
/// 得到当前区间长度
int len() { return r-l+; } /// 更新操作,val_代表01操作,xor_代表异或操作
void change(int val_, int Xor_) {
/// [l,r]全置为0
if (val_ == ) {
lmax_0 = rmax_0 = max_0 = sum_0 = len();
lmax_1 = rmax_1 = max_1 = sum_1 = ;
val = , Xor = ;
}
/// [l,r]全置为1
else if (val_ == ) {
lmax_0 = rmax_0 = max_0 = sum_0 = ;
lmax_1 = rmax_1 = max_1 = sum_1 = len();
val = , Xor = ;
}
/// [l,r]全异或
if (Xor_ == ) {
swap(lmax_0,lmax_1); swap(rmax_0,rmax_1);
swap(max_0,max_1); swap(sum_0,sum_1);
Xor ^= ;
}
}
}tree[maxn*];
int a[maxn];
void pushup(node &fa, node &ls, node &rs) {
/// 父节点的左边最长0串=左子树的左边最长0串
fa.lmax_0 = ls.lmax_0, fa.rmax_0 = rs.rmax_0;
fa.lmax_1 = ls.lmax_1, fa.rmax_1 = rs.rmax_1;
/// 父节点0的数量=左子树0的数量+右子树0的数量
fa.sum_0 = ls.sum_0+rs.sum_0;
fa.sum_1 = ls.sum_1+rs.sum_1;
/// 父节点最大连续0串等于左右子树里面中最大连续0串的最大值
/// 或者是左子树从右开始的0串+右子树从左开始的0串之和
fa.max_0 = max(max(ls.max_0,rs.max_0), ls.rmax_0+rs.lmax_0);
fa.max_1 = max(max(ls.max_1,rs.max_1), ls.rmax_1+rs.lmax_1); /// 如果左子树整串都为0串
if (ls.len() == ls.lmax_0) fa.lmax_0 += rs.lmax_0;
if (ls.len() == ls.lmax_1) fa.lmax_1 += rs.lmax_1;
if (rs.len() == rs.rmax_0) fa.rmax_0 += ls.rmax_0;
if (rs.len() == rs.rmax_1) fa.rmax_1 += ls.rmax_1;
}
void pushdown(int rt) {
if (tree[rt].val != - || tree[rt].Xor) {
tree[rt*].change(tree[rt].val,tree[rt].Xor);
tree[rt*+].change(tree[rt].val,tree[rt].Xor);
tree[rt].val = -, tree[rt].Xor = ;
}
}
void build(int rt, int l, int r) {
/// 结点初始化
tree[rt].l = l, tree[rt].r = r;
tree[rt].lmax_0 = tree[rt].rmax_0 = ;
tree[rt].lmax_1 = tree[rt].rmax_1 = ;
tree[rt].max_0 = tree[rt].max_1 = ;
tree[rt].sum_0 = tree[rt].sum_1 = ;
tree[rt].Xor = , tree[rt].val = -;
/// 如果是叶子结点
if (l == r) {
tree[rt].change(a[l],);
return;
}
int mid = (l+r)/;
build(rt*,l,mid);
build(rt*+,mid+,r);
pushup(tree[rt],tree[rt*],tree[rt*+]);
}
void update(int rt, int l, int r, int op) {
int L = tree[rt].l, R = tree[rt].r;
if (l <= L && R <= r) {
/// 根据op执行不同操作
if (op == || op == ) tree[rt].change(op,);
else if (op == ) tree[rt].change(-,);
return;
}
pushdown(rt);
int mid = (L+R)/;
if (mid >= l) update(rt*,l,r,op);
if (mid < r) update(rt*+,l,r,op);
pushup(tree[rt],tree[rt*],tree[rt*+]);
}
int query(int rt, int l, int r, int op) {
int L = tree[rt].l, R = tree[rt].r;
if (l <= L && R <= r) {
if (op == ) return tree[rt].sum_1;
else if (op == ) return tree[rt].max_1;
}
int mid = (L+R)/;
pushdown(rt);
if (r <= mid) return query(rt*,l,r,op);
else if (l > mid) return query(rt*+,l,r,op);
else {
int max1 = query(rt*,l,r,op);
int max2 = query(rt*+,l,r,op);
if (op == ) return max1+max2;
int max3 = min(tree[rt*].r-l+,tree[rt*].rmax_1)+min(r-tree[rt*+].l+,tree[rt*+].lmax_1);
return max(max(max1,max2),max3);
}
}
int main() {
int t; scanf("%d",&t);
while (t--) {
int n, m; scanf("%d%d",&n,&m);
for (int i = ; i < n; ++i)
scanf("%d",&a[i]);
build(,,n-);
while (m--) {
int op, a, b;
scanf("%d%d%d",&op,&a,&b);
if (op == || op == || op == ) update(,a,b,op);
else printf("%d\n",query(,a,b,op));
}
}
return ;
}
05-07 15:45