fork download
copy 
  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 DQuery {
  11. 	static class SegmentTree {
  12. 		public SegmentTree(int len) {
  13. 			//computeN(len);
  14. 			n = len;
  15. 			//tree = new int[n];
  16. 		}
  17.  
  18. 		int N = 100011;  // limit for array size
  19. 		int n;  // array size
  20. 		int t[] = new int[2 * N];
  21.  
  22. 		void build() {  // build the tree
  23. 		  for (int i = n - 1; i > 0; --i) t[i] = t[i<<1] + t[i<<1|1];
  24. 		}
  25.  
  26. 		void modify(int p, int value) {  // set value at position p
  27. 		  for (t[p += n] = value; p > 1; p >>= 1) t[p>>1] = t[p] + t[p^1];
  28. 		}
  29.  
  30. 		int query(int l, int r) {  // sum on interval [l, r)
  31. 		  int res = 0;
  32. 		  for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
  33. 		    if ((l&1) != 0) res += t[l++];
  34. 		    if ((r&1) != 0) res += t[--r];
  35. 		  }
  36. 		  return res;
  37. 		}
  38. 	}
  39.  
  40. 	static class Query implements Comparable<Query> {
  41. 		int left, right, num, idx;
  42. 		boolean query;
  43. 		public Query(int l, int r, int n, int i, boolean q) {
  44. 			left = l;
  45. 			right = r;
  46. 			num = n;
  47. 			idx = i;
  48. 			query = q;
  49. 		}
  50. 		@Override
  51. 		public int compareTo(Query o) {
  52. 			// TODO Auto-generated method stub
  53. 			if (right == o.right)
  54. 				if (query == o.query)
  55. 					return 0;
  56. 				else
  57. 					if (!query && o.query)
  58. 						return -1;
  59. 					else
  60. 						return 1;
  61. 			else 
  62. 				if (right < o.right)
  63. 					return -1;
  64. 				else
  65. 					return 1;
  66. 		}
  67. 	}
  68.  
  69. 	public static void main(String[] args) throws Exception {
  70. 		PrintWriter out = new PrintWriter(System.out);
  71. 		int n = next_int();
  72. 		SegmentTree segtree = new SegmentTree(n);
  73. 		ArrayList<Query> queries = new ArrayList<Query>(1);
  74. 		for (int i = 0; i < n; i++) {
  75. 			int x = next_int();
  76. 			queries.add(new Query(1, i + 1, x, i, false));
  77. 		}
  78. 		int q = next_int();
  79. 		for (int i = 0; i < q; i++) {
  80. 			int l = next_int();
  81. 			int r = next_int();
  82. 			queries.add(new Query(l, r, 0, i, true));
  83. 		}
  84. 		Collections.sort(queries);
  85. 		int idxs[] = new int[1000001];
  86. 		int qans[] = new int[q];
  87. 		for (int i = 0; i < n + q; i++) {
  88. 			if (queries.get(i).query) {
  89. 				qans[queries.get(i).idx] = segtree.query(queries.get(i).left, queries.get(i).right + 1);
  90. 			}
  91. 			else {
  92. 				if (idxs[queries.get(i).num] != 0) {
  93. 					segtree.modify(idxs[queries.get(i).num], 0);
  94. 				}
  95. 				segtree.modify(queries.get(i).right, 1);
  96. 				idxs[queries.get(i).num] = queries.get(i).right;
  97. 			}
  98. 		}
  99. 		for (int i = 0; i < q; i++) {
  100. 			out.println(qans[i]);
  101. 		}
  102. 		out.flush();
  103. 		out.close();
  104. 	}
  105.  
  106.  
  107. 	static int index, size;
  108. 	static byte[] b = new byte[1024];
  109.  
  110. 	static byte next_byte() throws Exception {
  111. 		if (index == size) {
  112. 			index = 0;
  113. 			size = System.in.read(b);
  114. 		}
  115. 		return b[index++];
  116. 	}
  117.  
  118. 	static int next_int() throws Exception {
  119. 		int n = 0;
  120. 		byte c = next_byte();
  121. 		while (!('0' <= c && c <= '9')) {
  122. 			c = next_byte();
  123. 		}
  124. 		while ('0' <= c && c <= '9') {
  125. 			n = n * 10 + c - '0';
  126. 			c = next_byte();
  127. 		}
  128. 		return n;
  129. 	}
  130.  
  131. }
  132.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
Main.java:10: error: class DQuery is public, should be declared in a file named DQuery.java
public class DQuery {
       ^
1 error
stdout
copy 
Standard output is empty
https://ideone.com/33m8yZ
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!