C++分析研究  
C++
日历
<2013年9月>
25262728293031
1234567
891011121314
15161718192021
22232425262728
293012345
统计
  • 随笔 - 92
  • 文章 - 4
  • 评论 - 4
  • 引用 - 0

导航

常用链接

留言簿

随笔档案

文章档案

搜索

  •  

最新评论

阅读排行榜

评论排行榜

 

  题意:区间交、并、减、补

  思路:用线段树的叶子节点记录该点是否被区间覆盖,因为有开区间的情况,因此考虑离散,将数值乘以2。

  U:把区间[l,r]覆盖成1

  I:把[-∞,l)(r,∞]覆盖成0

  D:把区间[l,r]覆盖成0

  C:把[-∞,l)(r,∞]覆盖成0 , 且[l,r]区间0/1互换

  S:[l,r]区间0/1互换

  区间修改容易做,但是加上区间异或就难了。

  我们考虑维护这样一棵线段树,如果区段的setv不是-1(初始化时候为-1),则说明该节点所对应的区段内全部的值为setv,如果根节点和子节点的setv值都不为-1,我们只认根节点上面的setv值。然后维护一个xorv值,表示该节点对应区段是否被异或奇数次(异或偶数次和没异或一样,是0)。这个xorv值一定出现在查找时第一次遇到setv值的前面,也就是说,查找时会先遇到有意义的xorv值,再遇到有意义的setv值(有意义是指,xorv=1,或者setv!=-1)。当要修改某个区段或寻找某个区段的过程中,xorv值和setv值会用pushdown不断往下压。明显我们可以知道这个性质:当一个区间被覆盖后,不管之前有没有异或标记都没有意义了。所以当一个节点得到覆盖标记时把异或标记清空托福答案

  而当一个节点得到异或标记的时候,先判断覆盖标记,如果是0或1,直接改变一下覆盖标记,不然的话改变异或标记托福改分

  输出的时候,我们可以用一个hash数组记录,用一个query将线段树上的值往下压到hash数组里面。

  注意几个问题:1.出现0的情况

  2.(3,3)这种空集的情况

  #include<cstdio>

  #include<cstring>

  #define M ((L+R)>>1)

  #define ls (o<<1)

  #define rs (o<<1|1)

  #define lson ls,L,M

  #define rson rs,M+1,R

  const int maxn=66666*2;

  bool hash[maxn],empty=1,flag=0;

  int n,yl,yr,v,setv[maxn*4],xorv[maxn*4],a,b,low=0,high;

  char op,left,right;

  void fxor(int o) {if(setv[o]>=0) setv[o]^=1; else xorv[o]^=1;}

  void pushdown(int o)

  {

  if(setv[o]>=0) {setv[ls]=setv[rs]=setv[o];xorv[ls]=xorv[rs]=0;setv[o]=-1;}

  if(xorv[o])

  {

  fxor(ls);

  fxor(rs);

  xorv[o]=0;

  }

  }

  void setupdate(int o,int L,int R)

  {

  if(yl<=L && R<=yr) {xorv[o]=0;setv[o]=v;return;}

  pushdown(o);

  if(yl<=M) setupdate(lson);

  if(M<yr) setupdate(rson);

  }

  void xorupdate(int o,int L,int R)

  {

  if(yl<=L && R<=yr){fxor(o);return;}

  pushdown(o);

  if(yl<=M) xorupdate(lson);

  if(M<yr) xorupdate(rson);

  }

  void query(int o,int L,int R)

  {

  if(setv[o]>=0)

  {

  if(setv[o]) for(int i=L;i<=R;++i) hash[i]=1;//将信息压倒hash里面去

  return;

  }

  pushdown(o);

  if(yl<=M) query(lson);

  if(M<yr) query(rson);

  }

  void init()

  {

  memset(setv,-1,sizeof(setv));

  memset(hash,0,sizeof(hash));

  xorv[1]=setv[1]=0;

  }

  void read()

  {

  while(~scanf("%c %c%d,%d%c ",&op,&left,&a,&b,&right))

  {

  a=(a+1)*2,b=(b+1)*2;

  if(left=='(') ++a; if(right==')') --b;

  if(op=='U')

  {

  v=1,yl=a,yr=b;

  if(yl<=yr) setupdate(1,1,maxn-1);

  }

  else if(op=='I')

  {

  v=0,yl=1,yr=a-1;

  if(yl<=yr) setupdate(1,1,maxn-1);

  yl=b+1,yr=maxn-1;

  if(yl<=yr) setupdate(1,1,maxn-1);

  }

  else if(op=='D')

  {

  v=0,yl=a,yr=b;

  if(yl<=yr) setupdate(1,1,maxn-1);

  }

  else if(op=='C')

  {

  v=0,yl=1,yr=a-1;

  if(yl<=yr) setupdate(1,1,maxn-1);

  yl=b+1,yr=maxn-1;

  if(yl<=yr) setupdate(1,1,maxn-1);

  yl=a,yr=b;

  if(yl<=yr) xorupdate(1,1,maxn-1);

  }

  else if(op=='S')

  {

  yl=a,yr=b;

  if(yl<=yr) xorupdate(1,1,maxn-1);

  }

  }

  }

  void print()

  {

  yl=1,yr=maxn-1;

  query(1,1,maxn-1);

  while(low<maxn)

  {

  while(!hash[low] && low<maxn) ++low;

  high=low+1;

  while(hash[high] && high<maxn) ++high;

  --high;

  if(low>=maxn) break;

  empty=0;

  if(flag) printf(" ");

  flag=1;

  if(low&1) printf("(");

  else printf("[");

  printf("%d,%d",(low/2)-1,(high-1)/2);

  if(high&1) printf(")");

  else printf("]");

  low=high+1;

  }

  if(empty) printf("empty set");

  puts("");

  }

  int main()

  {

  init();

  read();

  print();

  return 0;

  }

 

posted on 2013-09-03 00:21 HAOSOLA 阅读(371) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


 
Copyright © HAOSOLA Powered by: 博客园 模板提供:沪江博客
PK10开奖 PK10开奖