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

<a target="_blank" href="http://poj.org/problem?id=3225">http://poj.org/problem?id=3225</a>

一道题又做了一天。

。这道题对我来说起初有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 &gt; r) //l &gt; r的区间忽略不计

return;

if(tree[v].l == l &amp;&amp; tree[v].r == r)

if(col == 0 || col == 1)

tree[v].col = col;

else

if(tree[v].col != -1)

tree[v].col ^= 1;

tree[v].rev ^= 1;

push_down(v);

int mid = (tree[v].l + tree[v].r) &gt;&gt; 1;

if(r &lt;= mid)

update(v*2,l,r,col);

else if(l &gt; mid)

update(v*2+1,l,r,col);

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 &lt;= tree[v].r; i++)

a[i] = tree[v].col;

if(tree[v].col == 0)

if(tree[v].l == tree[v].r)

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] &gt;= '0' &amp;&amp; s2[i] &lt;= '9'; i++)

l = l*10 + s2[i]-'0';

i++;

for(; s2[i] &gt;= '0' &amp;&amp; s2[i] &lt;= '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,l,r,2); //取反

update(1,l,r,2);//取反

query(1);

int flag = 0;

for(int i = 0; i &lt; maxn; i++)

if(a[i] == 1 &amp;&amp; (i == 0 || a[i-1] == 0)) l = i;

if(a[i] == 1 &amp;&amp; (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;

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

版权声明：本文博主原创文章。博客，未经同意不得转载。

本文转自mfrbuaa博客园博客，原文链接：http://www.cnblogs.com/mfrbuaa/p/4870050.html，如需转载请自行联系原作者