[关闭]
@ysner 2018-09-29T19:03:33.000000Z 字数 3658 阅读 1578

[SCOI2010]序列操作

线段树


题面

最近收到了一个序列,序列里面包含了个数,这些数要么是,要么是,现在对于这个序列有五种变换操作和询问操作:

对于每一种询问操作,都需要给出回答,聪明的程序员们,你们能帮助他吗?

解析

线段树模板题。
只是要维护许多信息,考验细节和代码能力而已。
蒟蒻维护了个:
这一段左边有多少个连续的
这一段右边有多少个连续的
这一段左边有多少个连续的
这一段右边有多少个连续的
这一段是否全部为;
这一段是否全部为;
这一段最多有多少个连续的;
这一段最多有多少个连续的;
这一段有多少个
前三个操作的懒标记。

难度集中在信息合并:
讲了没意思,有需要自己看代码吧。

我是不会承认我调了只因没有意识到两个操作是可以抵消的。。。

  1. #include<iostream>
  2. #include<cmath>
  3. #include<cstdio>
  4. #include<cstdlib>
  5. #include<cstring>
  6. #include<algorithm>
  7. #define ll long long
  8. #define re register
  9. #define il inline
  10. #define ls x<<1
  11. #define rs x<<1|1
  12. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  13. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  14. using namespace std;
  15. const int N=4e5+100;
  16. int n,m,t1[N],t0[N],lt1[N],rt1[N],lt0[N],rt0[N],s[N],tag0[N],tag1[N],la0[N],la1[N],la2[N];
  17. il int max(re int x,re int y){return x>y?x:y;}
  18. il int min(re int x,re int y){return x<y?x:y;}
  19. struct dat{int t1,lt1,rt1,tag1;};
  20. il int gi()
  21. {
  22. re int x=0,t=1;
  23. re char ch=getchar();
  24. while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  25. if(ch=='-') t=-1,ch=getchar();
  26. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  27. return x*t;
  28. }
  29. il void upd(re int x)
  30. {
  31. s[x]=s[ls]+s[rs];
  32. t1[x]=max(t1[ls],t1[rs]);
  33. t1[x]=max(t1[x],rt1[ls]+lt1[rs]);
  34. t0[x]=max(t0[ls],t0[rs]);
  35. t0[x]=max(t0[x],rt0[ls]+lt0[rs]);
  36. if(tag1[ls]) lt1[x]=lt1[ls]+lt1[rs];else lt1[x]=lt1[ls];
  37. if(tag1[rs]) rt1[x]=rt1[rs]+rt1[ls];else rt1[x]=rt1[rs];
  38. if(tag0[ls]) lt0[x]=lt0[ls]+lt0[rs];else lt0[x]=lt0[ls];
  39. if(tag0[rs]) rt0[x]=rt0[rs]+rt0[ls];else rt0[x]=rt0[rs];
  40. t1[x]=max(t1[x],max(lt1[x],rt1[x]));
  41. t0[x]=max(t0[x],max(lt0[x],rt0[x]));
  42. tag1[x]=tag1[ls]&tag1[rs];tag0[x]=tag0[ls]&tag0[rs];
  43. }
  44. il void Build(re int x,re int l,re int r)
  45. {
  46. if(l==r)
  47. {
  48. lt1[x]=rt1[x]=s[x]=t1[x]=tag1[x]=gi();
  49. if(!t1[x]) t0[x]=lt0[x]=rt0[x]=tag0[x]=1;
  50. return;
  51. }
  52. re int mid=l+r>>1;
  53. Build(ls,l,mid);Build(rs,mid+1,r);
  54. upd(x);
  55. }
  56. il void cover(re int x,re int l,re int r,re int op)
  57. {
  58. if(op==0)
  59. {
  60. s[x]=t1[x]=lt1[x]=rt1[x]=tag1[x]=0;
  61. t0[x]=lt0[x]=rt0[x]=r-l+1;
  62. tag0[x]=la0[x]=1;la1[x]=la2[x]=0;
  63. }
  64. if(op==1)
  65. {
  66. s[x]=t1[x]=lt1[x]=rt1[x]=r-l+1;
  67. t0[x]=lt0[x]=rt0[x]=tag0[x]=0;
  68. tag1[x]=la1[x]=1;la0[x]=la2[x]=0;
  69. }
  70. if(op==2)
  71. {
  72. swap(t1[x],t0[x]);swap(lt1[x],lt0[x]);
  73. swap(rt1[x],rt0[x]);swap(tag0[x],tag1[x]);
  74. s[x]=r-l+1-s[x];la2[x]^=1;
  75. }
  76. }
  77. il void Pushdown(re int x,re int l,re int r)
  78. {
  79. re int mid=l+r>>1;
  80. if(la0[x]) cover(ls,l,mid,0),cover(rs,mid+1,r,0);
  81. if(la1[x]) cover(ls,l,mid,1),cover(rs,mid+1,r,1);
  82. if(la2[x]) cover(ls,l,mid,2),cover(rs,mid+1,r,2);
  83. la0[x]=la1[x]=la2[x]=0;
  84. }
  85. il void Modify(re int x,re int l,re int r,re int ql,re int qr,re int op)
  86. {
  87. if(tag1[x]&&op==1) return;
  88. if(tag0[x]&&op==0) return;
  89. if(ql<=l&&r<=qr) return cover(x,l,r,op);
  90. re int mid=l+r>>1;
  91. Pushdown(x,l,r);
  92. if(ql<=mid) Modify(ls,l,mid,ql,qr,op);
  93. if(qr>mid) Modify(rs,mid+1,r,ql,qr,op);
  94. upd(x);
  95. }
  96. il int Query(re int x,re int l,re int r,re int ql,re int qr)
  97. {
  98. if(ql<=l&&r<=qr) return s[x];
  99. re int mid=l+r>>1;
  100. Pushdown(x,l,r);
  101. if(qr<=mid) return Query(ls,l,mid,ql,qr);
  102. if(ql>mid) return Query(rs,mid+1,r,ql,qr);
  103. return Query(ls,l,mid,ql,qr)+Query(rs,mid+1,r,ql,qr);
  104. }
  105. il dat QueryS(re int x,re int l,re int r,re int ql,re int qr)
  106. {
  107. if(ql<=l&&r<=qr) return (dat){t1[x],lt1[x],rt1[x],tag1[x]};
  108. re int mid=l+r>>1;
  109. Pushdown(x,l,r);
  110. if(qr<=mid) return QueryS(ls,l,mid,ql,qr);
  111. if(ql>mid) return QueryS(rs,mid+1,r,ql,qr);
  112. re dat A=QueryS(ls,l,mid,ql,qr),B=QueryS(rs,mid+1,r,ql,qr);
  113. A.t1=max(A.t1,B.t1);
  114. A.t1=max(A.t1,A.rt1+B.lt1);
  115. if(A.tag1) A.lt1=A.lt1+B.lt1;
  116. if(B.tag1) A.rt1=A.rt1+B.rt1;else A.rt1=B.rt1;
  117. A.t1=max(A.t1,max(A.lt1,A.rt1));
  118. A.tag1=A.tag1&B.tag1;
  119. return A;
  120. }
  121. int main()
  122. {
  123. n=gi();m=gi();
  124. Build(1,1,n);
  125. re int gu=0;
  126. while(m--)
  127. {
  128. re int op=gi(),l=gi()+1,r=gi()+1;
  129. if(op<3) Modify(1,1,n,l,r,op);
  130. if(op==3) printf("%d\n",Query(1,1,n,l,r));
  131. if(op==4) printf("%d\n",QueryS(1,1,n,l,r).t1);
  132. }
  133. return 0;
  134. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注