fork(2) download
copy 
  1. #include <iostream>
  2. #include<cstdio>
  3. #include<cmath>
  4. #include<cstring>
  5. #define sf(x) scanf("%d",&x)
  6. using namespace std;
  7. #define SIZE 100005
  8. struct node {
  9. 	int number;
  10. 	int count;
  11.  
  12. 	int ln;
  13. 	int lc;
  14. 	int rn;
  15. 	int rc;
  16. };
  17. node st[4*SIZE];
  18. int arr[SIZE];
  19. void construct(int ss,int se,int index)
  20. {
  21. 	if(ss==se)
  22. 	{
  23. 		st[index].number=st[index].ln=st[index].rn=arr[ss];
  24. 		st[index].count=st[index].lc=st[index].rc=1;
  25.  
  26. 		// cout<<st[index].number<<" "<<st[index].count<<" "<<st[index].ln<<" "<<st[index].lc<<" "<<st[index].rn<<" "<<st[index].rc<<" "<<index<<endl;
  27. 		return;
  28. 	}
  29.  
  30. 	int mid=(ss+se)/2;
  31. 	construct(ss,mid,2*index+1);
  32. 	construct(mid+1,se,2*index+2);
  33.  
  34. 	node left=st[2*index+1];
  35. 	node right=st[2*index+2];
  36.  
  37. 	st[index].ln=left.ln;
  38. 	st[index].lc=left.lc;
  39.  
  40. 	st[index].rn=right.rn;
  41. 	st[index].rc=right.rc;
  42.  
  43. 	if(left.number==right.number)
  44. 	{
  45. 		st[index].number=left.number;
  46. 		st[index].count=left.count+right.count;
  47. 	}
  48. 	else
  49. 	{
  50. 		int m=-1;
  51. 		if(left.rn==right.ln)
  52. 		{
  53. 			m=left.rc+right.lc;
  54. 		}
  55. 		int ans=max(left.count,max(m,right.count));
  56. 		if(ans==left.count)
  57. 		{
  58. 				st[index].number=left.number;
  59. 				st[index].count=left.count;
  60. 		}
  61. 		else if(ans==right.count)
  62. 		{
  63. 				st[index].number=right.number;
  64. 				st[index].count=right.count;
  65. 		}
  66. 		else
  67. 		{
  68. 			st[index].number=left.rn;
  69. 			st[index].count=m;
  70. 		}
  71. 	}
  72. 	if(st[index].ln==st[index].number)
  73. 	st[index].lc=st[index].count;
  74. 	if(st[index].rn==st[index].number)
  75. 	st[index].rc=st[index].count;
  76.  
  77. 		// cout<<st[index].number<<" "<<st[index].count<<" "<<st[index].ln<<" "<<st[index].lc<<" "<<st[index].rn<<" "<<st[index].rc<<" "<<index<<endl;
  78. }
  79. node search(int ss,int se,int qs,int qe,int index)
  80. {
  81.  
  82. 	if(qs>se || ss>qe)
  83. 	{
  84. 		node temp;
  85. 		temp.number=temp.ln=temp.rn=-100000;
  86. 		temp.count=temp.lc=temp.rc=-1;
  87. 		return temp;
  88. 	}
  89. 	// cout<<ss<<" "<<se<<endl;
  90. 	if(qs<=ss && se<=qe)
  91. 	{
  92. 		return st[index];
  93. 	}
  94. 	int mid=(ss+se)/2;
  95. 	node left=search(ss,mid,qs,qe,2*index+1);
  96. 	node right=search(mid+1,se,qs,qe,2*index+2);
  97.  
  98. 	node res;
  99. 	res.ln=left.ln;
  100. 	res.lc=left.lc;
  101.  
  102. 	res.rn=right.rn;
  103. 	res.rc=right.rc;
  104.  
  105. 	if(left.number==right.number)
  106. 	{
  107. 		res.number=left.number;
  108. 		res.count=left.count+right.count;
  109. 	}
  110. 	else
  111. 	{
  112. 		int m=-1;
  113. 		if(left.rn==right.ln)
  114. 		{
  115. 			m=left.rc+right.lc;
  116. 		}
  117. 		int ans=max(left.count,max(m,right.count));
  118. 		if(ans==left.count)
  119. 		{
  120. 				res.number=left.number;
  121. 				res.count=left.count;
  122. 		}
  123. 		else if(ans==right.count)
  124. 		{
  125. 				res.number=right.number;
  126. 				res.count=right.count;
  127. 		}
  128. 		else
  129. 		{
  130. 			res.number=left.rn;
  131. 			res.count=m;
  132. 		}
  133. 	}
  134. 	if(res.ln==res.number)
  135. 	res.lc=st[index].count;
  136. 	if(res.rn==res.number)
  137. 	res.rc=res.count;
  138.  
  139. 	return res;
  140. }
  141. int main() 
  142. {
  143. 	// your code goes here
  144. 	ios::sync_with_stdio(false);
  145. 	int n,t;
  146. 	scanf("%d",&n);
  147. 	while(n!=0)
  148. 	{
  149. 		scanf("%d",&t);
  150. 		for(int i=0;i<n;i++)
  151. 		{
  152. 			scanf("%d",&arr[i]);
  153. 		}
  154. 		construct(0,n-1,0);
  155. 		while(t--)
  156. 		{
  157. 			int a,b;
  158. 			scanf("%d %d",&a,&b);
  159. 			node res=search(0,n-1,a-1,b-1,0);
  160. 			printf("%d\n",res.count);
  161. 		}
  162. 		scanf("%d",&n);
  163. 	}
  164. 	return 0;
  165. }
  166.  
  167.  
Success #stdin #stdout 0s 13248KB
comments (?)
stdin
copy 
10 3
-1 -1 1 1 1 1 3 10 10 10
2 3
1 10
5 10
0
stdout
copy 
1
4
3
https://ideone.com/leiE86
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!