程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj 3225 區間(區間的交並補操作)

poj 3225 區間(區間的交並補操作)

編輯：C++入門知識

poj 3225 區間(區間的交並補操作)

一道題又做了一天。。這道題對我來說起初有N多難點。

1：區間的開閉如何解決。、

2：怎樣把區間的交並補、對稱差轉化為對線段樹的操作。

後來與實驗室的同學討論了後解決了前面兩個問題。

對於區間的開閉，可以將區間放大一倍，偶數點表示端點，奇數點表示區間內線段，前開的話左端點加1，右開的話右端點減1。例如[1,3]可以表示成[2,6]，(1,3)表示成(3,5)。

對於區間的交並補問題，可以轉化為區間覆蓋問題，若T區間為[a,b]。

U T:[a,b]覆蓋為1.

I T:[0,a-1] [b+1,maxn] 覆蓋為0

D T:[a,b]覆蓋為0

C T:[0,a-1] [b+1,maxn] 覆蓋為0,[a,b]取反

S T:[a,b]取反

然後處理區間的覆蓋和異或操作。

起初對異或操作沒想到lazy,考慮到異或的性質，兩次異或相當於沒變。所以節點附加兩個信息：col,rev。

col表示覆蓋信息，col=0說明全被覆蓋為0，col=1說明全被覆蓋為1，col=-1說明沒有全被覆蓋。

rev表示異或信息，rev=1說明區間整體異或，rev=0說明不用異或。

可見只有當col=-1時rev才有用。更新時，若是區間覆蓋，相應區間覆蓋後抹去異或操作，若是異或操作，判斷區間是否完全覆蓋，若是直接異或，否則rev進行異或。push_down的時候，若區間完全覆蓋，將覆蓋信息推送下去並將左右兒子的異或操作抹去，若區間沒有完全覆蓋，必定有異或操作，將左右兒子可以異或的異或掉，不能異或的將其rev異或。

#include 
#include 
#include
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
//#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 = 131072;

struct node
{
	int l,r;
	int col;
	int rev;
}tree[maxn*4];

char s1[10],s2[10];
int a[maxn+10];

void build(int v, int l, int r)
{
	tree[v].l = l;
	tree[v].r = r;
	tree[v].col = 0;
	tree[v].rev = 0;
	if(l == r)
		return;
	int mid = (l+r)>>1;
	build(v*2,l,mid);
	build(v*2+1,mid+1,r);
}

void push_down(int v)
{
	if(tree[v].l == tree[v].r)
		return;
	if(tree[v].col != -1) //區間被完全覆蓋
	{
		tree[v*2].col = tree[v*2+1].col = tree[v].col; //向下推送，並把自己的col置為-1
		tree[v].col = -1;
		tree[v].rev = 0;
		tree[v*2].rev = tree[v*2+1].rev = 0; //兒子節點也被完全覆蓋，因此抹去異或操作
	}
	if(tree[v].rev) //區間沒被完全覆蓋且需要異或
	{
		if(tree[v*2].col != -1) //兒子節點被完全覆蓋，直接異或
			tree[v*2].col ^= 1;
		else tree[v*2].rev ^= 1;//否則rev進行異或。
		if(tree[v*2+1].col != -1)
			tree[v*2+1].col ^= 1;
		else tree[v*2+1].rev ^= 1;
		tree[v].rev = 0;
	}
}

void update(int v, int l, int r, int col)
{
	if(l > r) //l > r的區間忽略不計
		return;
	if(tree[v].l == l && tree[v].r == r)
	{
		if(col == 0 || col == 1)
		{
			tree[v].col = col;
			tree[v].rev = 0;
		}
		else
		{
			if(tree[v].col != -1)
				tree[v].col ^= 1;
			else
				tree[v].rev ^= 1;
		}
		return;
	}
	push_down(v);
	int mid = (tree[v].l + tree[v].r) >> 1;
	if(r <= mid)
		update(v*2,l,r,col);
	else if(l > mid)
		update(v*2+1,l,r,col);
	else
	{
		update(v*2,l,mid,col);
		update(v*2+1,mid+1,r,col);
	}
}

void query(int v)
{
	if(tree[v].col == 1)
	{
		for(int i = tree[v].l; i <= tree[v].r; i++)
			a[i] = tree[v].col;
		return;
	}
	if(tree[v].col == 0)
		return;
	if(tree[v].l == tree[v].r)
		return;
	push_down(v);
	query(v*2);
	query(v*2+1);
}

int main()
{
	build(1,0,maxn);
	int l,r,len;
    memset(a,0,sizeof(a));
	while(~scanf(%s %s,s1,s2))
	{
		l = 0;
		r = 0;
		len = strlen(s2);
		int i;
		for(i = 1; s2[i] >= '0' && s2[i] <= '9'; i++)
			l = l*10 + s2[i]-'0';
		i++;
		for(; s2[i] >= '0' && s2[i] <= '9'; i++)
			r = r*10 + s2[i]-'0';

		if(s2[0] == '[')
			l = l*2;
		else l = l*2+1;
		if(s2[len-1] == ']')
			r = r*2;
		else r = r*2-1;

		if(s1[0] == 'U')
		{
			update(1,l,r,1);
		}
		else if(s1[0] == 'I')
		{
			update(1,0,l-1,0);
			update(1,r+1,maxn,0);
		}
		else if(s1[0] == 'D')
		{
			update(1,l,r,0);
		}
		else if(s1[0] == 'C')
		{
			update(1,0,l-1,0);
			update(1,r+1,maxn,0);
			update(1,l,r,2); //取反
		}
		else
		{
			update(1,l,r,2);//取反
		}
	}

	query(1);
	int flag = 0;

	for(int i = 0; i < maxn; i++)
	{
		if(a[i] == 1 && (i == 0 || a[i-1] == 0)) l = i;
		if(a[i] == 1 && (i == maxn-1 || a[i+1] == 0))
		{
			if(flag == 0) flag = 1;
			else printf( );
			if(l%2)
				printf(();
			else printf([);
			printf(%d,,l/2);
			printf(%d,(i+1)/2);
			if(i%2)
				printf());
			else printf(]);
		}
	}
	if(flag == 0)
		printf(empty set
);
	else printf(
);
	return 0;
}