hdu 3911セグメントツリー

http://acm.hdu.edu.cn/showproblem.php?pid=3911
マルチキャリブレーション(8)
 
題意:配列要素が0と1しか与えられず、2つの操作があり、1 i jは[i,j]を変更するすべての要素を表し、0 i jは[i,j]の中で最も長い連続1を求める列の長さを表す.
 
分析:
膨大なパラメータが設定されていますね..あるセグメントの最左端連続の0個数、連続の1個数、最右端連続の0個数連続の1個数、全セグメント最長の連続0個数と最長の連続1個数を維持した後、タグ値cntを設定し、そのノードの更新回数を記録し、更新ごとにセグメントのみ更新し、cntに記録し、次に、更新または検索するたびにcntを更新します.の書くのは大変ですね...
 
1午後も悩んでいましたね...書くと死ぬ...少し漏れてもうっとうしくてたまらない...特にansのあの地方の誤りを求めてやっと探し当てます.
 
巨大スタンプのコード: もう一度書きましたが、すぐには書けないでしょう...手の速さをよく練習する.

 
#include<iostream>
using namespace std;

const int N=100010;
int n, m;
struct node
{
	int l, r, mid;
	int max1, max0, llen, rlen;
	bool lcolor, rcolor, cnt;
} a[N*4], tmp1, tmp2;

int _max(int a, int b)
{
	return a>b ? a:b;
}
int _min(int a, int b)
{
	return a<b ? a:b;
}
void build(int l, int r, int p)
{
	a[p].l = l;
	a[p].r = r;
	a[p].mid = (l+r)>>1;
	a[p].max0 = a[p].llen = a[p].rlen = (r-l+1);
	a[p].max1 = 0;
	a[p].lcolor = 0;
	a[p].rcolor = 0;
	a[p].cnt = 0;
	if(l==r)
		return;
	build(l, a[p].mid, p*2);
	build(a[p].mid+1, r, p*2+1);
}

void change(node &a)
{
	if(a.cnt==0)
		return;
	swap(a.max0, a.max1);
	a.lcolor ^= 1;
	a.rcolor ^= 1;
}

void update(int l, int r, int p)
{
	if(a[p].l==l && a[p].r==r)
	{
		a[p].cnt ^= 1;
		return;
	}

	if(a[p].cnt==1)
	{
		a[p*2].cnt ^= a[p].cnt;
		a[p*2+1].cnt ^= a[p].cnt;
		a[p].cnt = 0;
	}

	if(r<=a[p].mid)
		update(l, r, p*2);
	else if(l>a[p].mid)
		update(l, r, p*2+1);
	else
	{
		update(l, a[p].mid, p*2);
		update(a[p].mid+1, r, p*2+1);
	}
	tmp1 = a[p*2];
	tmp2 = a[p*2+1];
	change(tmp1);
	change(tmp2);
	a[p].lcolor = tmp1.lcolor;
	a[p].rcolor = tmp2.rcolor;
	a[p].llen = tmp1.llen;
	a[p].rlen = tmp2.rlen;
	a[p].max0 = _max(tmp1.max0, tmp2.max0);
	a[p].max1 = _max(tmp1.max1, tmp2.max1);
	if(tmp1.rcolor==tmp2.lcolor)
	{
		if(tmp1.llen==tmp1.r-tmp1.l+1)
			a[p].llen += tmp2.llen;
		if(tmp2.rlen==tmp2.r-tmp2.l+1)
			a[p].rlen += tmp1.rlen;
		if(tmp1.rcolor==0)
			a[p].max0 = _max(a[p].max0, tmp1.rlen+tmp2.llen);
		else
			a[p].max1 = _max(a[p].max1, tmp1.rlen+tmp2.llen);
	}
}

int query(int l, int r, int p)
{
	if(a[p].l==l && a[p].r==r)
	{
		if(a[p].cnt==0)
			return a[p].max1;
		else
			return a[p].max0;
	}
	if(a[p].cnt==1)
	{
		a[p*2].cnt ^= a[p].cnt;
		a[p*2+1].cnt ^= a[p].cnt;
	}

	int ans;
	if(r<=a[p].mid)
		ans = query(l, r, p*2);
	else if(l>a[p].mid)
		ans = query(l, r, p*2+1);
	else
	{
		ans = _max(query(l,a[p].mid, p*2), query(a[p].mid+1, r, p*2+1));
		tmp1 = a[p*2];
		tmp2 = a[p*2+1];
		change(tmp1);
		change(tmp2);
		if(tmp1.rcolor==1 && tmp2.lcolor==1)
		{
			int l1, l2;
			l1 = _min(a[p].mid-l+1, tmp1.rlen);
			l2 = _min(r-a[p].mid, tmp2.llen);
			ans = _max(ans, l1+l2);
		}
	}
	if(a[p].cnt==0)
		return ans;

	tmp1 = a[p*2];
	tmp2 = a[p*2+1];
	change(tmp1);
	change(tmp2);
	a[p].lcolor = tmp1.lcolor;
	a[p].rcolor = tmp2.rcolor;
	a[p].llen = tmp1.llen;
	a[p].rlen = tmp2.rlen;
	a[p].max0 = _max(tmp1.max0, tmp2.max0);
	a[p].max1 = _max(tmp1.max1, tmp2.max1);
	if(tmp1.rcolor==tmp2.lcolor)
	{
		if(tmp1.llen==tmp1.r-tmp1.l+1)
			a[p].llen += tmp2.llen;
		if(tmp2.rlen==tmp2.r-tmp2.l+1)
			a[p].rlen += tmp1.rlen;
		if(tmp1.rcolor==0)
			a[p].max0 = _max(a[p].max0, tmp1.rlen+tmp2.llen);
		else
			a[p].max1 = _max(a[p].max1, tmp1.rlen+tmp2.llen);
	}
	a[p].cnt = 0;
	return ans;
}

int main()
{
	int i, j, k, op, x, y;
	while(scanf("%d", &n)!=EOF)
	{
		build(1, n, 1);
		for(i=1; i<=n; i++)
		{
			scanf("%d", &x);
			if(x==1)
				update(i, i, 1);
		}
		scanf("%d", &m);
		while(m--)
		{			
			scanf("%d%d%d", &op, &x, &y);
			if(op==0)
				printf("%d
", query(x, y, 1));
			else
				update(x, y, 1);
		}
	}

	return 0;
}