fork(2) download
copy 
  1. import java.io.DataInputStream;
  2. import java.io.FileInputStream;
  3. import java.io.IOException;
  4. import java.io.PrintWriter;
  5.  
  6.  
  7. class FREQUENT {
  8. static int a[];
  9. 	public static void main(String[] args) throws IOException {
  10. 		// TODO Auto-generated method stub
  11. Reader r=new Reader();
  12. StringBuilder sb=new StringBuilder();
  13. PrintWriter pr=new PrintWriter(System.out);
  14. while(true){
  15. int n=r.nextInt();
  16. if(n==0)break;
  17. int q=r.nextInt();
  18.  a=new int[n+1];
  19. for(int i=1;i<=n;i++)a[i]=r.nextInt();
  20. Segment_Tree st=new Segment_Tree(1,n);
  21. //Segment_Tree.printPostOrder(st);
  22. for(int i=0;i<q;i++){
  23. 	int s=r.nextInt();
  24. 	int e=r.nextInt();
  25. 	int ans=st.query(s, e).freq;
  26. 	sb.append(ans+"\n");
  27. }
  28. }
  29. 	pr.write(sb.toString());
  30. 	pr.flush();
  31. 	}
  32. 	static class Segment_Tree{
  33. 		int start,end;
  34. 		int leftmost,freq1,rightmost,freq2,best,freq;
  35. 		Segment_Tree left_child,right_child;
  36. 		public Segment_Tree(){}
  37. 		//public Segment_Tree(){}
  38. 		public Segment_Tree(int a,int b){
  39. 			start=a;end=b;
  40. 			if(start!=end){
  41. 				int mid=(start+end)>>1;
  42. 				left_child=new Segment_Tree(a,mid);
  43. 				right_child=new Segment_Tree(mid+1, b);
  44. 				join(this, left_child, right_child);
  45. 			}
  46. 			else{
  47. 				leftmost=rightmost=best=FREQUENT.a[start];
  48. 				freq1=freq2=freq=1;
  49. 			}
  50. 		}
  51. 		public static void join(Segment_Tree parent,Segment_Tree left_child,Segment_Tree right_child){
  52. 			int combine=0;
  53. 			if(parent.start==0 && parent.end==0){
  54. 				parent.start=left_child.start;parent.end=right_child.end;
  55. 			}
  56. 			int mid=(parent.start+parent.end)>>1;
  57. 			if(FREQUENT.a[mid]==FREQUENT.a[mid+1]){
  58. 				parent.freq1=left_child.freq1+right_child.freq1*(FREQUENT.a[mid]==FREQUENT.a[parent.start]?1:0);
  59. 				parent.freq2=right_child.freq2+left_child.freq2*(FREQUENT.a[mid+1]==FREQUENT.a[parent.end]?1:0);
  60. 				combine=left_child.freq2+right_child.freq1;
  61. 				parent.freq=Math.max(combine, Math.max(parent.freq1, parent.freq2));
  62. 			}
  63. 			else{
  64. 				parent.freq1=left_child.freq1;
  65. 				parent.freq2=right_child.freq2;
  66. 				parent.freq=Math.max(parent.freq1, parent.freq2);
  67. 			}
  68. 		}
  69. 		public Segment_Tree query(int a,int b){
  70. 			if(a>b || a>end || b<start)return null;
  71. 			if(start==a && end==b)return this;
  72. 			int mid=(start+end)>>1;
  73. 			if(a>mid)return right_child.query(a, b);
  74. 			else if(b<=mid)return left_child.query(a, b);
  75. 			Segment_Tree ans=new Segment_Tree();
  76. 			Segment_Tree left=left_child.query(a,mid);
  77. 			Segment_Tree right=right_child.query(mid+1, b);
  78. 			join(ans,left,right);
  79. 			//printDetails(ans, left, right);
  80. 			return ans;
  81. 		}
  82. 		public static void printPostOrder(Segment_Tree parent){
  83. 			if(parent==null)return;
  84. 			else{
  85. 				printPostOrder(parent.left_child);
  86. 				printPostOrder(parent.right_child);
  87. 				System.out.println(parent.start+"-"+parent.end);
  88. 				System.out.println(parent.best+" "+parent.freq);
  89. 				System.out.println(parent.leftmost+" "+parent.freq1);
  90. 				System.out.println(parent.rightmost+" "+parent.freq2);
  91. 			}
  92. 		}
  93. 		public static void printDetails(Segment_Tree parent,Segment_Tree left_child,Segment_Tree right_child){
  94. 			System.out.println(left_child.start+"-"+left_child.end);
  95. 			System.out.println(right_child.start+"-"+right_child.end);
  96. 			System.out.println(left_child.leftmost+" "+left_child.freq1);
  97. 			System.out.println(left_child.rightmost+" "+left_child.freq2);
  98. 			System.out.println(right_child.leftmost+" "+right_child.freq1);
  99. 			System.out.println(right_child.rightmost+" "+right_child.freq2);
  100. 			System.out.println(parent.best+" "+parent.freq);
  101. 			System.out.println(parent.leftmost+" "+parent.freq1);
  102. 			System.out.println(parent.rightmost+" "+parent.freq2);
  103. 		}
  104. 	}
  105. static class Reader {
  106. 	final private int BUFFER_SIZE = 1 << 16;
  107. 	private DataInputStream din;
  108. 	private byte[] buffer;
  109. 	private int bufferPointer, bytesRead;
  110.  
  111. 	public Reader() {
  112. 		din = new DataInputStream(System.in);
  113. 		buffer = new byte[BUFFER_SIZE];
  114. 		bufferPointer = bytesRead = 0;
  115. 	}
  116.  
  117. 	public Reader(String file_name) throws IOException {
  118. 		din = new DataInputStream(new FileInputStream(file_name));
  119. 		buffer = new byte[BUFFER_SIZE];
  120. 		bufferPointer = bytesRead = 0;
  121. 	}
  122.  
  123. 	public String readLine() throws IOException {
  124. 		byte[] buf = new byte[64];
  125. 		int cnt = 0, c;
  126. 		while ((c = read()) != -1) {
  127. 			if (c == '\n')
  128. 				break;
  129. 			buf[cnt++] = (byte) c;
  130. 		}
  131. 		return new String(buf, 0, cnt);
  132. 	}
  133.  
  134. 	public int nextInt() throws IOException {
  135. 		int ret = 0;
  136. 		byte c = read();
  137. 		while (c <= ' ')
  138. 			c = read();
  139. 		boolean neg = (c == '-');
  140. 		if (neg)
  141. 			c = read();
  142. 		do {
  143. 			ret = ret * 10 + c - '0';
  144. 		} while ((c = read()) >= '0' && c <= '9');
  145. 		if (neg)
  146. 			return -ret;
  147. 		return ret;
  148. 	}
  149.  
  150. 	public long nextLong() throws IOException {
  151. 		long ret = 0;
  152. 		byte c = read();
  153. 		while (c <= ' ')
  154. 			c = read();
  155. 		boolean neg = (c == '-');
  156. 		if (neg)
  157. 			c = read();
  158. 		do {
  159. 			ret = ret * 10 + c - '0';
  160. 		} while ((c = read()) >= '0' && c <= '9');
  161. 		if (neg)
  162. 			return -ret;
  163. 		return ret;
  164. 	}
  165.  
  166. 	public double nextDouble() throws IOException {
  167. 		double ret = 0, div = 1;
  168. 		byte c = read();
  169. 		while (c <= ' ')
  170. 			c = read();
  171. 		boolean neg = (c == '-');
  172. 		if (neg)
  173. 			c = read();
  174. 		do {
  175. 			ret = ret * 10 + c - '0';
  176. 		} while ((c = read()) >= '0' && c <= '9');
  177. 		if (c == '.')
  178. 			while ((c = read()) >= '0' && c <= '9')
  179. 				ret += (c - '0') / (div *= 10);
  180. 		if (neg)
  181. 			return -ret;
  182. 		return ret;
  183. 	}
  184.  
  185. 	private void fillBuffer() throws IOException {
  186. 		bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
  187. 		if (bytesRead == -1)
  188. 			buffer[0] = -1;
  189. 	}
  190.  
  191. 	private byte read() throws IOException {
  192. 		if (bufferPointer == bytesRead)
  193. 			fillBuffer();
  194. 		return buffer[bufferPointer++];
  195. 	}
  196.  
  197. 	public void close() throws IOException {
  198. 		if (din == null)
  199. 			return;
  200. 		din.close();
  201. 	}
  202. }
  203.  
  204. }
  205. /*
  206. 10 5
  207. -1 -1 -1 -1 1 1 1 1 2 2
  208. 2 7
  209. 6 10
  210. 3 7
  211. 2 5
  212. 1 10
  213. 0
  214. */
Success #stdin #stdout 0.07s 381184KB
comments (?)
stdin
copy 
10 1
-1 -1 -1 -1 -1 1 1 1 2 2
2 7
0
stdout
copy 
6
https://ideone.com/d3zEqv
language:
Java (HotSpot 12)
created:
9 years ago
visibility:
secret

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!