fork download 
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4. import java.io.PrintWriter;
  5. import java.util.ArrayList;
  6. import java.util.Arrays;
  7. import java.util.Collections;
  8. import java.util.StringTokenizer;
  9.  
  10. public class Main {
  11.  
  12.  
  13. 	static class SegmentTree {
  14.  
  15. 		int tree[];
  16. 		int n;
  17.  
  18. 		public SegmentTree(int len) {
  19. 			computeN(len);
  20. 			tree = new int[n];
  21. 		}
  22.  
  23. 		int query(int i, int j) {
  24. 			return query(1, 1, n / 2, i, j);
  25. 		}
  26.  
  27. 		int query(int node, int l, int r, int i, int j) {
  28. 			if (node > n || node < 1 || r < l || l < 1 || r > n / 2 || r < i || l > j)
  29. 				return 0;
  30. 			if (l >= i && r <= j) {
  31. 				return tree[node];
  32. 			}
  33. 			int mid = (l + r) >> 1;
  34. 			int left = node << 1;
  35. 			int right = left | 1;
  36. 			int lf = query(left, l, mid, i, j);
  37. 			int ri = query(right, mid + 1, r, i , j);
  38. 			return lf + ri;
  39. 		}
  40.  
  41. 		void update(int i, int j, int val) {
  42. 			update(1, 1, n / 2, i, j, val);
  43. 		}
  44.  
  45. 		int update(int node, int l, int r, int i, int j, int val) {
  46. 			if (node > n || node < 1 || r < l || l < 1 || r > n / 2)
  47. 				return 0;
  48. 			if (l >= i && r <= j) {
  49. 				//System.out.println("I am putting " + val);
  50. 				return tree[node] = val;
  51. 			}
  52. 			if (r < i || l > j) {
  53. 				return tree[node];
  54. 			}
  55. 			int mid = (l + r) >> 1;
  56. 			int left = node << 1;
  57. 			int right = left | 1;
  58. 			int lf = update(left, l, mid, i, j, val);
  59. 			int ri = update(right, mid + 1, r, i , j, val);
  60. 			return tree[node] = lf + ri;
  61. 		}
  62.  
  63. 		void computeN(int x) {
  64. 			n = 1;
  65. 			while (n < x)
  66. 				n <<= 1;
  67. 			n <<= 1;
  68. 		}
  69. 	}
  70.  
  71. 	static class Query implements Comparable<Query> {
  72. 		int left, right, num, idx;
  73. 		boolean query;
  74. 		public Query(int l, int r, int n, int i, boolean q) {
  75. 			left = l;
  76. 			right = r;
  77. 			num = n;
  78. 			idx = i;
  79. 			query = q;
  80. 		}
  81. 		@Override
  82. 		public int compareTo(Query o) {
  83. 			// TODO Auto-generated method stub
  84. 			if (right == o.right)
  85. 				if (query == o.query)
  86. 					return 0;
  87. 				else
  88. 					if (!query && o.query)
  89. 						return -1;
  90. 					else
  91. 						return 1;
  92. 			else 
  93. 				if (right < o.right)
  94. 					return -1;
  95. 				else
  96. 					return 1;
  97. 		}
  98. 	}
  99.  
  100. 	public static void main(String[] args) throws Exception {
  101. 		PrintWriter out = new PrintWriter(System.out);
  102. 		int n = next_int();
  103. 		SegmentTree segtree = new SegmentTree(n);
  104. 		ArrayList<Query> queries = new ArrayList<Query>(1);
  105. 		for (int i = 0; i < n; i++) {
  106. 			int x = next_int();
  107. 			queries.add(new Query(1, i + 1, x, i, false));
  108. 		}
  109. 		int q = next_int();
  110. 		for (int i = 0; i < q; i++) {
  111. 			int l = next_int();
  112. 			int r = next_int();
  113. 			queries.add(new Query(l, r, 0, i, true));
  114. 		}
  115. 		Collections.sort(queries);
  116. 		int idxs[] = new int[1000001];
  117. 		int qans[] = new int[q];
  118. 		for (int i = 0; i < n + q; i++) {
  119. 			if (queries.get(i).query) {
  120. 				qans[queries.get(i).idx] = segtree.query(queries.get(i).left, queries.get(i).right);
  121. 			}
  122. 			else {
  123. 				if (idxs[queries.get(i).num] != 0) {
  124. 					segtree.update(idxs[queries.get(i).num], idxs[queries.get(i).num], 0);
  125. 				}
  126. 				segtree.update(queries.get(i).right, queries.get(i).right, 1);
  127. 				idxs[queries.get(i).num] = queries.get(i).right;
  128. 			}
  129. 		}
  130. 		for (int i = 0; i < q; i++) {
  131. 			out.println(qans[i]);
  132. 		}
  133. 		out.flush();
  134. 		out.close();
  135. 	}
  136.  
  137.  
  138. 	static int index, size;
  139. 	static byte[] b = new byte[1024];
  140.  
  141. 	static byte next_byte() throws Exception {
  142. 		if (index == size) {
  143. 			index = 0;
  144. 			size = System.in.read(b);
  145. 		}
  146. 		return b[index++];
  147. 	}
  148.  
  149. 	static int next_int() throws Exception {
  150. 		int n = 0;
  151. 		byte c = next_byte();
  152. 		while (!('0' <= c && c <= '9')) {
  153. 			c = next_byte();
  154. 		}
  155. 		while ('0' <= c && c <= '9') {
  156. 			n = n * 10 + c - '0';
  157. 			c = next_byte();
  158. 		}
  159. 		return n;
  160. 	}
  161.  
  162. }
Runtime error #stdin #stdout #stderr 0.11s 320512KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
stderr 
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 1024
	at Main.next_byte(Main.java:146)
	at Main.next_int(Main.java:153)
	at Main.main(Main.java:102)
https://ideone.com/itwocf
language:
Java (12.0.1)
created:
8 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!