首页 > 代码库 > hdu 3379 Sequence operation(成段更新，区间合并)
hdu 3379 Sequence operation(成段更新，区间合并)
http://acm.hdu.edu.cn/showproblem.php?pid=3397
线段树很好的题。涉及到的知识点：lazy操作处理异或操作和置01，区间合并。
有五种操作：
0 a b 将[a,b]变为0
1 a b 将[a,b]变为1
2 a b 将[a,b]取反
3 a b 输出[a,b]的1的个数
4 a b 输出[a,b]内最长的连续1的个数
对区间的操作与poj 3225类似。置01与取反是互斥的，一段区间上只能有一个标记，discuss里面也说了取反的时候若递归到区间全为0或1的时候再取反违背了线段树的本质。因此对于这两个操作设置一个变量lazy，它的取值有-1,0,1,2，-1表示没有操作，0和1表示被0或1覆盖，2表示区间取反。因为两次取反后相当于没取，lazy标记在这里起到很大作用，若要对这个区间取反，只需将其lazy置为2，下次再取反时就变为原来的，即置为-1。
询问区间的1的个数时，只需要sum维护区间的和即可。求连续的1的长度时，需要区间合并，又因为有取反操作，同时还要记录区间内连续的0的个数。
#include <stdio.h>
#include <iostream>
#include <map>
#include <set>
#include <list>
#include <stack>
#include <vector>
#include <math.h>
#include <string.h>
#include <queue>
#include <string>
#include <stdlib.h>
#include <algorithm>
//#define LL long long
#define LL __int64
#define eps 1e-12
#define PI acos(-1.0)
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 100010;
/*
节点共有如下信息：
lazy:标记区间中的操作或覆盖情况，
sum:区间的和,
ll[2]表示从左边数连续的0和1的个数，rr[2]表示从右边数连续的0和1的个数，
long0、long1分别表示最长的连续的0和1的长度。
*/
struct node
{
int l,r;
int lazy;
int sum;
int ll[2],rr[2];
int long1,long0;
}tree[maxn*4];
int a[maxn];
/*
向上更新，更新父亲节点的和以及ll[],rr[],long0,long1
*/
void push_up(int v)
{
int l = tree[v].l,r = tree[v].r;
int ls = v*2,rs = v*2+1;
int mid = (l+r)>>1;
tree[v].sum = tree[ls].sum + tree[rs].sum;
tree[v].ll[0] = tree[ls].ll[0];
if(tree[ls].sum == 0)
tree[v].ll[0] += tree[rs].ll[0];
tree[v].ll[1] = tree[ls].ll[1];
if(tree[ls].sum == mid-l+1)
tree[v].ll[1] += tree[rs].ll[1];
tree[v].rr[0] = tree[rs].rr[0];
if(tree[rs].sum == 0)
tree[v].rr[0] += tree[ls].rr[0];
tree[v].rr[1] = tree[rs].rr[1];
if(tree[rs].sum == r-mid)
tree[v].rr[1] += tree[ls].rr[1];
tree[v].long0 = max(max(tree[ls].long0,tree[rs].long0),tree[ls].rr[0]+tree[rs].ll[0]);
tree[v].long1 = max(max(tree[ls].long1,tree[rs].long1),tree[ls].rr[1]+tree[rs].ll[1]);
}
/*
向下更新，lazy为0或1时直接覆盖子区间，为2时看子区间是否被完全覆盖，若是就直接取反，否则子节点的lazy取反
*/
void push_down(int v)
{
if(tree[v].l == tree[v].r || tree[v].lazy == -1)
return;
int l = tree[v].l,r = tree[v].r;
int ls = v*2,rs = v*2+1;
int mid = (l + r)>>1;
if(tree[v].lazy == 0)
{
tree[ls].lazy = tree[rs].lazy = 0;
tree[ls].sum = tree[rs].sum = 0;
tree[ls].long1 = tree[rs].long1 = 0;
tree[ls].ll[1] = tree[ls].rr[1] = tree[rs].ll[1] = tree[rs].rr[1] = 0;
tree[ls].ll[0] = tree[ls].rr[0] = tree[ls].long0 = mid-l+1;
tree[rs].ll[0] = tree[rs].rr[0] = tree[rs].long0 = r-mid;
}
else if(tree[v].lazy == 1)
{
tree[ls].lazy = tree[rs].lazy = 1;
tree[ls].sum = mid-l+1;
tree[rs].sum = r-mid;
tree[ls].long0 = tree[rs].long0 = 0;
tree[ls].ll[0] = tree[ls].rr[0] = tree[rs].ll[0] = tree[rs].rr[0] = 0;
tree[ls].ll[1] = tree[ls].rr[1] = tree[ls].long1 = mid-l+1;
tree[rs].ll[1] = tree[rs].rr[1] = tree[rs].long1 = r-mid;
}
else if(tree[v].lazy == 2)
{
if(tree[ls].lazy == -1 || tree[ls].lazy == 2)
{
tree[ls].lazy = 1-tree[ls].lazy;
tree[ls].sum = mid-l+1-tree[ls].sum;
swap(tree[ls].long0,tree[ls].long1);
swap(tree[ls].ll[0],tree[ls].ll[1]);
swap(tree[ls].rr[0],tree[ls].rr[1]);
}
else if(tree[ls].lazy == 1)
{
tree[ls].lazy = 0;
tree[ls].sum = 0;
tree[ls].long0 = tree[ls].ll[0] = tree[ls].rr[0] = mid-l+1;
tree[ls].long1 = tree[ls].ll[1] = tree[ls].rr[1] = 0;
}
else if(tree[ls].lazy == 0)
{
tree[ls].lazy = 1;
tree[ls].sum = mid-l+1;
tree[ls].long0 = tree[ls].ll[0] = tree[ls].rr[0] = 0;
tree[ls].long1 = tree[ls].ll[1] = tree[ls].rr[1] = mid-l+1;
}
if(tree[rs].lazy == -1 || tree[rs].lazy == 2)
{
tree[rs].lazy = 1-tree[rs].lazy;
tree[rs].sum = r-mid-tree[rs].sum;
swap(tree[rs].long0,tree[rs].long1);
swap(tree[rs].ll[0],tree[rs].ll[1]);
swap(tree[rs].rr[0],tree[rs].rr[1]);
}
else if(tree[rs].lazy == 1)
{
tree[rs].lazy = 0;
tree[rs].sum = 0;
tree[rs].long0 = tree[rs].ll[0] = tree[rs].rr[0] = r-mid;
tree[rs].long1 = tree[rs].ll[1] = tree[rs].rr[1] = 0;
}
else if(tree[rs].lazy == 0)
{
tree[rs].lazy = 1;
tree[rs].sum = r-mid;
tree[rs].long0 = tree[rs].ll[0] = tree[rs].rr[0] = 0;
tree[rs].long1 = tree[rs].ll[1] = tree[rs].rr[1] = r-mid;
}
}
tree[v].lazy = -1;
}
void build(int v, int l, int r)
{
tree[v].l = l;
tree[v].r = r;
tree[v].lazy = -1;
tree[v].sum = 0;
tree[v].ll[0] = tree[v].rr[0] = tree[v].long0 = 0;
tree[v].ll[1] = tree[v].rr[1] = tree[v].long1 = 0;
if(l == r)
{
tree[v].sum = a[l];
if(a[l] == 0)
tree[v].ll[0] = tree[v].rr[0] = tree[v].long0 = 1;
else
tree[v].ll[1] = tree[v].rr[1] = tree[v].long1 = 1;
return;
}
int mid = (l+r)>>1;
build(v*2,l,mid);
build(v*2+1,mid+1,r);
push_up(v);
}
void update(int v, int l, int r, int op)
{
if(tree[v].l == l && tree[v].r == r)
{
if(op == 0)
{
tree[v].lazy = tree[v].sum = 0;
tree[v].ll[0] = tree[v].rr[0] = tree[v].long0 = tree[v].r - tree[v].l + 1;
tree[v].ll[1] = tree[v].rr[1] = tree[v].long1 = 0;
}
else if(op == 1)
{
tree[v].lazy = 1;
tree[v].sum = tree[v].r - tree[v].l + 1;
tree[v].ll[1] = tree[v].rr[1] = tree[v].long1 = tree[v].r - tree[v].l + 1;
tree[v].ll[0] = tree[v].rr[0] = tree[v].long0 = 0;
}
else if(op == 2)
{
if(tree[v].lazy == 0)
{
tree[v].lazy = 1;
tree[v].sum = tree[v].r - tree[v].l + 1;
tree[v].ll[1] = tree[v].rr[1] = tree[v].long1 = tree[v].r-tree[v].l+1;
tree[v].ll[0] = tree[v].rr[0] = tree[v].long0 = 0;
}
else if(tree[v].lazy == 1)
{
tree[v].lazy = tree[v].sum = 0;
tree[v].ll[1] = tree[v].rr[1] = tree[v].long1 = 0;
tree[v].ll[0] = tree[v].rr[0] = tree[v].long0 = tree[v].r-tree[v].l+1;
}
else if(tree[v].lazy == -1 || tree[v].lazy == 2)
{
tree[v].lazy = 1-tree[v].lazy;
tree[v].sum = tree[v].r-tree[v].l+1-tree[v].sum;
swap(tree[v].long0,tree[v].long1);
swap(tree[v].ll[0],tree[v].ll[1]);
swap(tree[v].rr[0],tree[v].rr[1]);
}
}
return;
}
push_down(v);
int mid = (tree[v].l + tree[v].r) >> 1;
if(r <= mid)
update(v*2,l,r,op);
else if(l > mid)
update(v*2+1,l,r,op);
else
{
update(v*2,l,mid,op);
update(v*2+1,mid+1,r,op);
}
push_up(v);
}
int query(int v, int l, int r,int op)
{
if(tree[v].l == l && tree[v].r == r)
{
if(op == 3)
return tree[v].sum;
else
return tree[v].long1;
}
push_down(v);
int mid = (tree[v].l + tree[v].r) >> 1;
if(r <= mid)
return query(v*2,l,r,op);
else if(l > mid)
return query(v*2+1,l,r,op);
else
{
if(op == 3)
return query(v*2,l,mid,op) + query(v*2+1,mid+1,r,op);
else
{
//求区间[l,r]中最长的连续是1的长度。
int tmp = min(tree[v*2].rr[1],mid-l+1) + min(tree[v*2+1].ll[1],r-mid);
return max(tmp,max(query(v*2,l,mid,op),query(v*2+1,mid+1,r,op)));
}
}
}
int main()
{
int test;
int n,m;
int op,l,r;
scanf("%d",&test);
while(test--)
{
scanf("%d %d",&n,&m);
for(int i = 1; i <= n; i++)
scanf("%d",&a[i]);
build(1,1,n);
while(m--)
{
scanf("%d %d %d",&op,&l,&r);
l++;
r++;
if(op <= 2)
{
update(1,l,r,op);
}
else
{
int ans = query(1,l,r,op);
printf("%d\n",ans);
}
}
}
return 0;
}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。