HDU 3911 Black And White （線段樹區(qū)間更新）
[導(dǎo)讀]題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=3911
題面：
Black And White
Time Limit: 9000/3000 MS (
題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=3911
題面：
Black And White Time Limit: 9000/3000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 4358????Accepted Submission(s): 1271
Problem Description There are a bunch of stones on the beach; Stone color is white or black. Little Sheep has a magic brush, she can change the color of a continuous stone, black to white, white to black. Little Sheep like black very much, so she want to know the longest period of consecutive black stones in a range [i, j]. ?
Input ??There are multiple cases, the first line of each case is an integer n(1<= n <= 10^5), followed by n integer 1 or 0(1 indicates black stone and 0 indicates white stone), then is an integer M(1<=M<=10^5) followed by M operations formatted as x i j(x = 0 or 1) , x=1 means change the color of stones in range[i,j], and x=0 means ask the longest period of consecutive black stones in range[i,j] ?
Output When x=0 output a number means the longest length of black stones in range [i,j]. ?
Sample Input 4 1 0 1 0 5 0 1 4 1 2 3 0 1 4 1 3 3 0 4 4 ?
Sample Output 1 2 0 ?
Source 2011 Multi-University Training Contest 8 - Host by HUST
題目大意：
??? 初始給定一01序列，兩種操作，1 a b，取反a到b間的元素，0 a b，問a b區(qū)間內(nèi)最長的連續(xù)1的長度。
解題：
??? 第一顆區(qū)間更新的線段樹，來得有點(diǎn)晚啊，借鑒、理解也算是寫出來了。題意看似簡單，合并操作比較復(fù)雜。需要維護(hù)5個(gè)值。maxw,maxb,le,ri,lazy。
??? maxw/maxb，該區(qū)間的最長連續(xù)0/1長度，取反時(shí)直接交換兩值。
??? le/ri，該區(qū)間的左右連續(xù)塊長度，用于合并。
??? lazy該區(qū)間是否需要繼續(xù)向下更新。
代碼：
#include
#include
#include
#define siz 100010
//左右子樹編號(hào)
#define ls i<<1
#define rs (i<<1)|1
using namespace std;
//左右邊界，該區(qū)間最多連續(xù)黑塊數(shù)，白塊數(shù)，因?yàn)榉崔D(zhuǎn)區(qū)間需要
//區(qū)間左邊界連續(xù)塊數(shù)，右邊解連續(xù)塊數(shù)，正表黑，負(fù)表白，用于區(qū)間合并
//lazy標(biāo)記如果為1，代表更新到該區(qū)間，其下區(qū)間尚未更新
struct SEGTree
{
int l,r,maxb,maxw,le,ri,lazy;
}STree[siz<<2];
int a[siz];
//取大
int max(int x,int y)
{
return x>y?x:y;
}
//取小
int min(int a,int b)
{
return a0&&STree[rs].le>0)
{
tmp=STree[ls].ri+STree[rs].le;
if(tmp>maxb)
maxb=tmp;
}
//更新
STree[i].maxb=maxb;
//白塊更新同上
int maxw=max(STree[ls].maxw,STree[rs].maxw);
if(STree[ls].ri<0&&STree[rs].le<0)
{
tmp=STree[ls].ri+STree[rs].le;
tmp=-tmp;
if(tmp>maxw)
maxw=tmp;
}
STree[i].maxw=maxw;
//區(qū)間左端最長連續(xù)塊數(shù)le，如果左子區(qū)單色，且能與右子區(qū)相連，更新le
if(abs(STree[ls].le)==(STree[ls].r-STree[ls].l+1)&&(STree[ls].ri*STree[rs].le>0))
STree[i].le=STree[ls].le+STree[rs].le;
//否則直接取左子區(qū)le
else STree[i].le=STree[ls].le;
//更新ri，同上
if(abs(STree[rs].ri)==(STree[rs].r-STree[rs].l+1)&&(STree[ls].ri*STree[rs].le>0))
STree[i].ri=STree[ls].ri+STree[rs].ri;
else STree[i].ri=STree[rs].ri;
}
//向下更新
void push_down(int i)
{
//該區(qū)間的懶標(biāo)記清零
STree[i].lazy=0;
//更新左右子區(qū)間
swap(STree[ls].maxw,STree[ls].maxb);
STree[ls].le=-STree[ls].le;
STree[ls].ri=-STree[ls].ri;
STree[ls].lazy=!STree[ls].lazy;
swap(STree[rs].maxw,STree[rs].maxb);
STree[rs].le=-STree[rs].le;
STree[rs].ri=-STree[rs].ri;
STree[rs].lazy=!STree[rs].lazy;
}
//建樹
void build(int i,int l,int r)
{
STree[i].l=l;
STree[i].r=r;
STree[i].lazy=0;
//葉子節(jié)點(diǎn)
if(l==r)
{
//如果是黑塊
if(a[l])
{
STree[i].maxb=1;
STree[i].maxw=0;
STree[i].le=1;
STree[i].ri=1;
}
//白塊
else
{
STree[i].maxw=1;
STree[i].maxb=0;
STree[i].le=-1;
STree[i].ri=-1;
}
return;
}
//向下遞歸
int mid=(l+r)>>1;
build(i<<1,l,mid);
build((i<<1)|1,mid+1,r);
//向上更新
push_up(i);
}
void update(int i,int l,int r)
{
//如果剛好區(qū)間吻合
if(STree[i].l==l&&STree[i].r==r)
{
//黑白塊交換
swap(STree[i].maxw,STree[i].maxb);
STree[i].le=-STree[i].le;
STree[i].ri=-STree[i].ri;
//lazy取反
STree[i].lazy=!STree[i].lazy;
return;
}
//如果沒有剛好吻合，要訪問的區(qū)間為當(dāng)前區(qū)間子區(qū)間，
//且該區(qū)間還有懶標(biāo)記未下放，則向下更新，并向下訪問
if(STree[i].lazy)
push_down(i);
int mid=(STree[i].l+STree[i].r)>>1;
if(r<=mid)
update(ls,l,r);
else if(l>mid)
update(rs,l,r);
else
{
update(ls,l,mid);
update(rs,mid+1,r);
}
//更新之后，向上更新
push_up(i);
}
int query(int i,int l,int r)
{
//如果剛好吻合，則返回區(qū)間最大連續(xù)黑塊
if(l==STree[i].l&&r==STree[i].r)
return STree[i].maxb;
int mid=(STree[i].l+STree[i].r)>>1;
//不能完全符合，且該區(qū)間尚有懶標(biāo)記，下放懶標(biāo)記
if(STree[i].lazy)
push_down(i);
//向下查詢
if(r<=mid)
return query(ls,l,r);
else if(l>mid)
return query(rs,l,r);
else
{
int res,tmp;
//取左右最值，合并的最值
res=max(query(ls,l,mid),query(rs,mid+1,r));
//此處不僅僅合并左右區(qū)間最值，還需限制左右邊界不能超出查詢區(qū)間以mid為中心的左右邊界
tmp=min(mid-l+1,STree[ls].ri)+min(r-mid,STree[rs].le);
if(tmp>res)
res=tmp;
return res;
}
}
int main()
{
int n,q,oper,fm,to;
while(~scanf("%d",&n))
{
//讀入
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
//建樹
build(1,1,n);
scanf("%d",&q);
for(int i=1;i<=q;i++)
{
scanf("%d",&oper);
scanf("%d%d",&fm,&to);
if(oper)
update(1,fm,to);
else
{
int ans=query(1,fm,to);
printf("%dn",ans);
}
}
}
return 0;
}
下載文檔
