• 练习41，[SCOI2010] 序列操作【线段树】

    P2572 [SCOI2010] 序列操作 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

    思路不是很难，码量很大，调试难度高，一个bug找一天（bushi

    稍微难一些的就是求[l,r] 区间内最多有多少个连续的 1，可以分别维护一段区间左端，中间，右端有多少个连续的1和0来实现。同时要注意的点是赋0和赋1标记可以覆盖取反标记，而取反标记不能覆盖赋0和赋1标记，而且取反标记更改时要^=1

    具体看代码注释

    1. #include
    2. using namespace std;
    3. #define INF 0x3f3f3f3f
    4. #define INF_L 0x3f3f3f3f3f3f3f3fLL
    5. #define NOTLE ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
    6. #define endl '\n'
    7. #define T int TT;cin >> TT;while (TT--)
    8. #define lint long long
    9. #define PII pair
    10. #define PLL pair
    11. #define pb push_back
    12. #define eb emplace_back
    13. int a[100010];
    14. int n,m;
    15. struct node{
    16. 	int l,r,sum;
    17. 	int sw,t0,t1; //sw取反标记，t0赋0标记，t1赋1标记
    18. 	int ll1,lm1,lr1,ll0,lm0,lr0;
    19. 	//ll1维护区间左端连续1的长度
    20. 	//lm1维护区间中间最长连续1的长度
    21. 	//lr1维护区间右端连续1的长度
    22. }tree[400010],node0;
    23.  
    24. void pushup(int p){
    25. 	tree[p].sum=tree[p<<1].sum+tree[p<<1|1].sum;
    26. 	
    27. 	tree[p].ll1=tree[p<<1].ll1;
    28. 	tree[p].lr1=tree[p<<1|1].lr1;
    29. 	/*如果左或右端的连续1长度等于区间长度，则需要将另一段要合并的区间的左端或右端
    30. 	的连续1长度加上*/
    31. 	if(tree[p<<1].ll1==tree[p<<1].r-tree[p<<1].l+1){ 
    32. 		tree[p].ll1+=tree[p<<1|1].ll1;
    33. 	}
    34. 	if(tree[p<<1|1].lr1==tree[p<<1|1].r-tree[p<<1|1].l+1){
    35. 		tree[p].lr1+=tree[p<<1].lr1;
    36. 	}
    37. 	tree[p].lm1=max(tree[p<<1].lr1+tree[p<<1|1].ll1,max(tree[p<<1].lm1,tree[p<<1|1].lm1));
    38. 	
    39. 	tree[p].ll0=tree[p<<1].ll0;
    40. 	tree[p].lr0=tree[p<<1|1].lr0;
    41. 	if(tree[p<<1].ll0==tree[p<<1].r-tree[p<<1].l+1){
    42. 		tree[p].ll0+=tree[p<<1|1].ll0;
    43. 	}
    44. 	if(tree[p<<1|1].lr0==tree[p<<1|1].r-tree[p<<1|1].l+1){
    45. 		tree[p].lr0+=tree[p<<1].lr0;
    46. 	}
    47. 	tree[p].lm0=max(tree[p<<1].lr0+tree[p<<1|1].ll0,max(tree[p<<1].lm0,tree[p<<1|1].lm0));
    48. }
    49. void pushdown(int p){
    50. 	if(tree[p].t0){
    51. 		tree[p<<1].t0=tree[p<<1|1].t0=1;
    52. 		tree[p<<1].t1=tree[p<<1|1].t1=0;
    53. 		tree[p<<1].sw=tree[p<<1|1].sw=0;
    54. 		tree[p<<1].sum=0;
    55. 		tree[p<<1].ll1=tree[p<<1].lm1=tree[p<<1].lr1=0;
    56. 		tree[p<<1].ll0=tree[p<<1].lm0=tree[p<<1].lr0=tree[p<<1].r-tree[p<<1].l+1;
    57. 		tree[p<<1|1].sum=0;
    58. 		tree[p<<1|1].ll1=tree[p<<1|1].lm1=tree[p<<1|1].lr1=0;
    59. 		tree[p<<1|1].ll0=tree[p<<1|1].lm0=tree[p<<1|1].lr0=tree[p<<1|1].r-tree[p<<1|1].l+1;
    60. 	}
    61. 	if(tree[p].t1){
    62. 		tree[p<<1].t0=tree[p<<1|1].t0=0;
    63. 		tree[p<<1].t1=tree[p<<1|1].t1=1;
    64. 		tree[p<<1].sw=tree[p<<1|1].sw=0;
    65. 		tree[p<<1].sum=tree[p<<1].r-tree[p<<1].l+1;
    66. 		tree[p<<1].ll1=tree[p<<1].lm1=tree[p<<1].lr1=tree[p<<1].r-tree[p<<1].l+1;
    67. 		tree[p<<1].ll0=tree[p<<1].lm0=tree[p<<1].lr0=0;
    68. 		tree[p<<1|1].sum=tree[p<<1|1].r-tree[p<<1|1].l+1;
    69. 		tree[p<<1|1].ll1=tree[p<<1|1].lm1=tree[p<<1|1].lr1=tree[p<<1|1].r-tree[p<<1|1].l+1;
    70. 		tree[p<<1|1].ll0=tree[p<<1|1].lm0=tree[p<<1|1].lr0=0;
    71. 	}
    72. 	if(tree[p].sw){
    73. 		tree[p<<1].sw^=1;
    74. 		tree[p<<1|1].sw^=1;
    75. 		tree[p<<1].sum=tree[p<<1].r-tree[p<<1].l+1-tree[p<<1].sum;
    76. 		swap(tree[p<<1].ll1,tree[p<<1].ll0);
    77. 		swap(tree[p<<1].lm1,tree[p<<1].lm0);
    78. 		swap(tree[p<<1].lr1,tree[p<<1].lr0);
    79. 		tree[p<<1|1].sum=tree[p<<1|1].r-tree[p<<1|1].l+1-tree[p<<1|1].sum;
    80. 		swap(tree[p<<1|1].ll1,tree[p<<1|1].ll0);
    81. 		swap(tree[p<<1|1].lm1,tree[p<<1|1].lm0);
    82. 		swap(tree[p<<1|1].lr1,tree[p<<1|1].lr0);
    83. 	}
    84. 	tree[p].t0=tree[p].t1=tree[p].sw=0;
    85. }
    86. void build(int l,int r,int p=1){
    87. 	tree[p].l=l,tree[p].r=r;
    88. 	tree[p].ll1=tree[p].lm1=tree[p].lr1=tree[p].ll0=tree[p].lm0=tree[p].lr0=0;
    89. 	tree[p].sw=tree[p].t0=tree[p].t1=0;
    90. 	if(l==r){
    91. 		tree[p].sum=a[l];
    92. 		if(a[l]) tree[p].ll1=tree[p].lm1=tree[p].lr1=1;
    93. 		else tree[p].ll0=tree[p].lm0=tree[p].lr0=1;
    94. 		 return ;
    95. 	}
    96. 	int mid=l+r>>1;
    97. 	build(l,mid,p<<1);
    98. 	build(mid+1,r,p<<1|1);
    99. 	pushup(p);
    100. }
    101. void turn(int l,int r,int t,int p=1){ //赋值
    102. 	if(l<=tree[p].l && r>=tree[p].r){
    103. 		if(t==0){
    104. 			tree[p].t0=1,tree[p].t1=0;
    105. 			tree[p].sum=0;
    106. 			tree[p].ll1=tree[p].lm1=tree[p].lr1=0;
    107. 			tree[p].ll0=tree[p].lm0=tree[p].lr0=tree[p].r-tree[p].l+1;
    108. 		}
    109. 		else {
    110. 			tree[p].t0=0,tree[p].t1=1;
    111. 			tree[p].sum=tree[p].r-tree[p].l+1;
    112. 			tree[p].ll1=tree[p].lm1=tree[p].lr1=tree[p].r-tree[p].l+1;
    113. 			tree[p].ll0=tree[p].lm0=tree[p].lr0=0;
    114. 		}
    115. 		tree[p].sw=0;
    116. 		return ;
    117. 	}
    118. 	pushdown(p);
    119. 	int mid=tree[p].l+tree[p].r>>1;
    120. 	if(l<=mid) turn(l,r,t,p<<1);
    121. 	if(r>mid) turn(l,r,t,p<<1|1);
    122. 	pushup(p);
    123. }
    124. void swc(int l,int r,int p=1){ //取反
    125. 	if(l<=tree[p].l && r>=tree[p].r){
    126. 		tree[p].sum=tree[p].r-tree[p].l+1-tree[p].sum;
    127. 		swap(tree[p].ll1,tree[p].ll0);
    128. 		swap(tree[p].lm1,tree[p].lm0);
    129. 		swap(tree[p].lr1,tree[p].lr0);
    130. 		tree[p].sw^=1;
    131. 		return ;
    132. 	}
    133. 	pushdown(p);
    134. 	int mid=tree[p].l+tree[p].r>>1;
    135. 	if(l<=mid) swc(l,r,p<<1);
    136. 	if(r>mid) swc(l,r,p<<1|1);
    137. 	pushup(p);
    138. }
    139. int querysum(int l,int r,int p=1){ //询问区间1个数
    140. 	if(l<=tree[p].l && r>=tree[p].r) return tree[p].sum;
    141. 	pushdown(p);
    142. 	int mid=tree[p].l+tree[p].r>>1,sum=0;
    143. 	if(l<=mid) sum+=querysum(l,r,p<<1);
    144. 	if(r>mid) sum+=querysum(l,r,p<<1|1);
    145. 	return sum;
    146. }
    147. node queryl(int l,int r,int p=1){ //询问区间最长连续1
    148. 	if(l<=tree[p].l && r>=tree[p].r) return tree[p];
    149. 	pushdown(p);
    150. 	int mid=tree[p].l+tree[p].r>>1;
    151. 	node x=node0,lx=node0,rx=node0;
    152. 	int fl=0,fr=0;
    153. 	if(l<=mid){lx=queryl(l,r,p<<1); fl=1;}
    154. 	if(r>mid){rx=queryl(l,r,p<<1|1); fr=1;}
    155. 	if(fl+fr==2){
    156. 		x.ll1=lx.ll1;
    157. 		x.lr1=rx.lr1;
    158. 		if(lx.ll1==lx.r-lx.l+1){
    159. 		x.ll1+=rx.ll1;
    160. 	}
    161. 	if(rx.lr1==rx.r-rx.l+1){
    162. 		x.lr1+=lx.lr1;
    163. 	}
    164. 		x.lm1=max(lx.lr1+rx.ll1,max(lx.lm1,rx.lm1));
    165. 	}
    166. 	else if(fl==0) x=rx;
    167. 	else if(fr==0) x=lx;
    168. 	return x;
    169. }
    170. void init(){
    171. 	node0.ll1=node0.lm1=node0.lr1=node0.ll0=node0.lm0=node0.lr0=0;
    172. 	node0.sw=node0.t0=node0.t1=0;
    173. }
    174. int main(){
    175.     NOTLE;
    176.     init();
    177.     cin >> n >> m;
    178. 	for(int i=1;i<=n;i++) cin >> a[i];
    179. 	build(1,n);
    180. 	for(int i=1;i<=m;i++){
    181. 		int opt,l,r;
    182. 		cin >> opt >> l >> r;
    183. 		l++,r++;
    184. 		if(opt==0){
    185. 			turn(l,r,0);
    186. 		}
    187. 		if(opt==1){
    188. 			turn(l,r,1);
    189. 		}
    190. 		if(opt==2){
    191. 			swc(l,r);
    192. 		}
    193. 		if(opt==3){
    194. 			cout << querysum(l,r) << endl;
    195. 		}
    196. 		if(opt==4){
    197. 			node x=queryl(l,r);
    198. 			cout << max(max(x.ll1,x.lr1),x.lm1) << endl;
    199. 		}
    200. 	}
    201.     return 0;
    202. }

    此题还有一种解法是珂朵莉树，但只能过随机的数据，无法通过洛谷上已经针对过的数据

    1. #include
    2. using namespace std;
    3. #define INF 0x3f3f3f3f
    4. #define INF_L 0x3f3f3f3f3f3f3f3fLL
    5. #define NOTLE ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
    6. #define endl '\n'
    7. #define T int TT;cin >> TT;while (TT--)
    8. #define lint long long
    9. #define PII pair
    10. #define PLL pair
    11. #define S_IT set::iterator
    12. #define pb push_back
    13. #define eb emplace_back
    14. #define MAXN 100002
    15.  
    16. typedef int type;
    17. struct Node{
    18. 	unsigned int l;
    19. 	unsigned int r;
    20. 	mutable type data;
    21. 	Node(unsigned int a, unsigned int b = 0, type c = 0);
    22. 	bool operator <(const Node &a) const{return l < a.l;}
    23. };
    24. Node::Node(unsigned int a, unsigned int b, type c){l = a; r = b; data = c;}
    25. set s;
    26.  
    27. S_IT split(unsigned int pos){
    28. 	S_IT it = s.lower_bound(Node(pos));
    29. 	if (it != s.end() && it->l == pos) return it;
    30. 	--it;
    31. 	unsigned int l = it->l, r = it->r;
    32. 	type data = it->data;
    33. 	s.erase(it);
    34. 	s.insert(Node(l, pos - 1, data));
    35. 	return s.insert(Node(pos, r, data)).first;
    36. }
    37.  
    38. void swc(int l,int r,int val){
    39. 	S_IT it2 = split(r + 1), it1 = split(l);
    40. 	s.erase(it1, it2);
    41. 	s.insert(Node(l, r, val));
    42. 	return;
    43. }
    44.  
    45. void rev(int l,int r){
    46. 	S_IT it2 = split(r + 1), it1 = split(l);
    47. 	for (; it1 != it2; ++it1)
    48. 		it1->data ^= 1;
    49. }
    50.  
    51. int sum(int l,int r){
    52. 	S_IT it2 = split(r + 1), it1 = split(l);
    53. 	int res=0;
    54. 	for (; it1 != it2; ++it1)
    55. 		if(it1->data) res+=(it1->r)-(it1->l)+1;
    56. 	return res;
    57. }
    58.  
    59. int con(int l,int r){
    60. 	int res=0,temp=0;
    61. 	S_IT it2 = split(r + 1), it1 = split(l);
    62. 	for (; it1 != it2; ++it1){
    63. 		if (it1->data){
    64. 			temp+=(it1->r)-(it1->l)+1;
    65. 		}
    66. 		else{
    67. 			res=max(res,temp);
    68. 			temp=0;
    69. 		}
    70. 	}
    71. 	return max(res, temp);
    72. }
    73.  
    74. int main(){
    75. 	NOTLE;
    76. 	int n, m;
    77. 	cin >> n >> m;
    78. 	for (int i = 0; i < n; ++i){
    79. 		int temp;
    80. 		cin >> temp;
    81. 		s.insert(Node(i, i, temp));
    82. 	}
    83. 	s.insert(Node(n, n, 0));
    84. 	while(m--){
    85. 		int op,a,b;
    86. 		cin >> op >> a >> b;
    87. 		if (op==0) swc(a, b, 0);
    88.         if (op==1) swc(a, b, 1);
    89. 		if (op==2) rev(a, b);
    90. 		if (op==3) cout << sum(a, b) << endl;
    91. 		if (op==4) cout << con(a, b) << endl;
    92. 	}
    93. 	return 0;
    94. }

  • 相关阅读:
    volatile的用途和说明
    LeetCode307 周赛（补记）
    SystemVerilog学习-10-验证量化和覆盖率
    RabbitMQ---SpringAMQP的使用，五种消息模型的示例
    一体化伺服电机在三轴钻孔机中的应用
    7.1、如何理解Flink中的时间语义
    界面控件DevExpress WinForms HTML-CSS模板：预设计UI模板加速.NET应用开发
    【优化算法】基于matlab量子粒子群算法求解单目标优化问题【含Matlab源码 2203期】
    ASP.NET Core - 选项系统之源码介绍
    使用css 与 js 两种方式实现导航栏吸顶效果
  • 原文地址：https://blog.csdn.net/ILECY/article/details/126931496