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异或。
#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;
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\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;
}
版权声明：本文博主原创文章。博客，未经同意不得转载。