poj 3225 间隙(横截面和填充操作)

电玩女神 2022-04-10 10:51 45阅读 0赞

[http://poj.org/problem?id=3225][http_poj.org_problem_id_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异或。**

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\\n"); else printf("\\n"); return 0; \}

**做了[hdu 3379][],又尝试了一种写法，就是将上面的col和rev合并起来，由于它们是相互排斥的，一个节点仅仅会有一个信息。**

**所以仅仅用col表示。col为2时表示取反。为-1表示不操作。若開始是-1，当两次取反后又变回-1。**

#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 = 131072;
    
    struct node
    {
    	int l,r;
    	int col;
    }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;
    	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].col == -1 || tree[v].l == tree[v].r)
    		return;
    	if(tree[v].col == 0 || tree[v].col == 1)
    	{
    		tree[v*2].col = tree[v*2+1].col = tree[v].col;
    	}
    	else
    	{
    		if(tree[v*2].col == 0 || tree[v*2].col == 1)
    			tree[v*2].col ^= 1;
    		else
    			tree[v*2].col = 1-tree[v*2].col;
    
    		if(tree[v*2+1].col == 0 || tree[v*2+1].col == 1)
    			tree[v*2+1].col ^= 1;
    		else tree[v*2+1].col = 1-tree[v*2+1].col;
    	}
    	tree[v].col = -1;
    	return;
    }
    
    void update(int v, int l, int r, int col)
    {
    	if(l > r)
    		return;
    	if(tree[v].l == l && tree[v].r == r)
    	{
    		if(col == 0 || col == 1)
    		{
    			tree[v].col = col;
    		}
    		else
    		{
    			if(tree[v].col == 0 || tree[v].col == 1)
    				tree[v].col ^= 1;
    			else tree[v].col = 1-tree[v].col;
    		}
    		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\n");
    	else printf("\n");
    	return 0;
    }

[http_poj.org_problem_id_3225]: http://poj.org/problem?id=3225
[hdu 3379]: http://blog.csdn.net/u013081425/article/details/38664407