本文主要是介绍HDU - 3911 Black And White 区间翻转+区间连续最长，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
区间翻转的裸题，wrong了两发，没找bug，直接又打了一遍，这么大量的代码找bug是疯了。
重新开始做线段树的一些题了，感觉对于pushdown与lazy数组有点印象了。
首先，lazy数组是记录的当前数组的改变，不管是这个题的异或，还是加减，lazy数组就是线段树的主要优化原因，当你用的时候你再下放，大大减少了复杂度。但是记录的时候lazy[i]=1时候，tree[i]是要先处理的，然后每次每一查找的时候是先看该节点成不成立，不成立的话，再下放lazy。还有就是update的时候也要下放lazy.
就是这样，这道题的话主要的问题就是区间反转，lazy[i]变换两次的话就是不变，所以用异或来处理刚刚好，区间连续最长的问题就是个模板，记录左最长，右最长，总体最长。
1.在pushup的时候，要注意如果左儿子的左最长已经占了左边的总长，那么父亲节点的左最长就还要加上右儿子的左最长。
父节点的右最长也是相同的
tree[i].wl=tree[lson].wl+((tree[lson].wl==mid-l+1)?tree[rson].wl:0);2.第二个问题就是在query的时候，找的是左儿子的总体最长，右儿子总体最长，以及左儿子的右最长+右儿子的左最长在询问左端点ql,询问右端点qr之间的总长度。
return max3(query(Lson,ql,mid),query(Rson,mid+1,qr),min(mid-ql+1,tree[lson].br)+min(qr-mid,tree[rson].bl));结合全部代码，用宏定义，写起来会快很多还简
洁，但是可能会慢一点，理解理解。
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<set>
#include<stack>
#include<vector>
#include<map>
#include<queue>
#define myself i,l,r
#define lson i<<1//左儿子
#define rson i<<1|1//右儿子
#define Lson i<<1,l,mid
#define Rson i<<1|1,mid+1,r
#define half (l+r)/2
#define inff 0x3f3f3f3f
#define lowbit(x) x&(-x)
#define me(a,b) memset(a,b,sizeof(a))
#define min4(a,b,c,d) min(min(a,b),min(c,d))
#define min3(x,y,z) min(min(x,y),min(y,z))
#define max4(a,b,c,d) max(max(a,b),max(c,d))
#define max3(x,y,z) max(max(x,y),max(y,z))
typedef long long ll;
using namespace std;
const int maxn=1e5+5;
struct node
{int wl,wr,wm,bl,br,bm;//w表示白的左，右，总；b就是black黑左右总
}tree[maxn<<2];
int lazy[maxn<<2];
int n,m;
void pushup(int i,int l,int r)//往上更新
{int mid=half;tree[i].wl=tree[lson].wl+((tree[lson].wl==mid-l+1)?tree[rson].wl:0);tree[i].bl=tree[lson].bl+((tree[lson].bl==mid-l+1)?tree[rson].bl:0);tree[i].wr=tree[rson].wr+((tree[rson].wr==r-mid)?tree[lson].wr:0);tree[i].br=tree[rson].br+((tree[rson].br==r-mid)?tree[lson].br:0);tree[i].wm=max3(tree[lson].wm,tree[rson].wm,tree[lson].wr+tree[rson].wl);tree[i].bm=max3(tree[lson].bm,tree[rson].bm,tree[lson].br+tree[rson].bl);
}
void change(int x)
{swap(tree[x].wl,tree[x].bl);swap(tree[x].wr,tree[x].br);swap(tree[x].wm,tree[x].bm);
}
void pushdown(int i,int l,int r)
{if(lazy[i]){lazy[lson]^=1;lazy[rson]^=1;change(lson);change(rson);lazy[i]=0;return;}
}
void update(int i,int l,int r,int ql,int qr)
{if(ql<=l&&qr>=r){change(i);lazy[i]^=1;return ;}int mid=half;pushdown(myself);if(qr<=mid) update(Lson,ql,qr);else if(ql>mid) update(Rson,ql,qr);else{update(Lson,ql,mid);update(Rson,mid+1,qr);}pushup(myself);
}
int query(int i,int l,int r,int ql,int qr)
{if(ql<=l&&qr>=r)return tree[i].bm;pushdown(myself);int mid=half;if(qr<=mid) return query(Lson,ql,qr);else if(ql>mid) return query(Rson,ql,qr);else return max3(query(Lson,ql,mid),query(Rson,mid+1,qr),min(mid-ql+1,tree[lson].br)+min(qr-mid,tree[rson].bl));
}
void build(int i,int l,int r)
{int x;lazy[i]=0;if(l==r){scanf("%d",&x);tree[i].bl=tree[i].br=tree[i].bm=x;tree[i].wl=tree[i].wr=tree[i].wm=x^1;return;}int mid=half;build(Lson);build(Rson);pushup(myself);
}
int main()
{int num,x,y;while(scanf("%d",&n)!=EOF){build(1,1,n);scanf("%d",&m);while(m--){scanf("%d%d%d",&num,&x,&y);if(num==0)printf("%d\n",query(1,1,n,x,y));elseupdate(1,1,n,x,y);}}return 0;
}
这篇关于HDU - 3911 Black And White 区间翻转+区间连续最长的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
