fork(1) download
copy 
  1. import java.util.*;
  2. import java.io.*;
  3. class KQUERY2{
  4. 	static class Node{
  5. 		int val;
  6. 		Node left;
  7. 		Node right;
  8. 		int count;
  9. 		int sum;
  10. 		Node(int val){
  11. 			this.val = val;
  12. 			count = 1;
  13. 			sum = 1;
  14. 			left = null;
  15. 			right = null;
  16. 		}
  17. 	}
  18. 	static int n ;
  19. 	static int []a;
  20. 	static Node []st;
  21. 	static int count;
  22. 	public static void main(String []arg) throws IOException{
  23. 		InputReader in = new InputReader(System.in);
  24.         OutputWriter out = new OutputWriter(System.out);
  25.         n = in.readInt();
  26.         a = new int[n];
  27.         for(int i=0;i<n;i++){
  28.         	a[i] = in.readInt();
  29.         }
  30.         st = new Node[4*n];
  31.         constructST(0,n-1,0);
  32.         int m = in.readInt();
  33.         while(m-- >0){
  34.         	int flag = in.readInt();
  35.         	if(flag == 0){
  36.         		int ind = in.readInt()-1;
  37.         		int val = in.readInt();
  38.         		updateST(0,n-1,ind,val,0);
  39.         	}else{
  40.         		int l = in.readInt()-1;
  41.         		int r = in.readInt()-1;
  42.         		int k = in.readInt();
  43.         		count = 0;
  44.         		query(0,n-1,l,r,k,0);
  45.         		System.out.println(count);
  46.         	}
  47.         }
  48. 	}
  49.  
  50. 	static void inOrder(Node root){
  51. 		if(root == null){
  52. 			return ;
  53. 		}
  54. 		if(root.left != null){
  55. 			inOrder(root.left);
  56. 		}
  57. 		System.out.print(root.val+" ");
  58. 		if(root.right != null){
  59. 			inOrder(root.right);
  60. 		}
  61. 	}
  62.  
  63. 	static void query(int s,int e,int l,int r,int k,int i){
  64. 		if(l > e || r < s){
  65. 			return ;
  66. 		}
  67. 		if(l <= s && r >= e){
  68. 			search(st[i],k);
  69. 			return ;
  70. 		}
  71. 		int mid = s + (e-s)/2;
  72. 		query(s,mid,l,r,k,2*i+1);
  73. 		query(mid+1,e,l,r,k,2*i+2);
  74. 	}
  75.  
  76. 	static void search(Node root,int val){
  77. 		if(root == null){
  78. 			return ;
  79. 		}
  80. 		if(val < root.val){
  81. 			count += (root.count+getCount(root.right));
  82. 			search(root.left,val);
  83. 		}else if(val > root.val){
  84. 			search(root.right,val);
  85. 		}else{
  86. 			count += getCount(root.right);
  87. 		}
  88. 	}
  89.  
  90. 	static void updateST(int s,int e,int ind,int val,int i){
  91. 		if(e < s){
  92. 			return ;
  93. 		}
  94. 		if(ind < s || ind > e){
  95. 			return ;
  96. 		}
  97. 		st[i] = delete(st[i],a[ind]);
  98. 		st[i] = insert(st[i],val);
  99. 		if(s == e){
  100. 			return ;
  101. 		}
  102. 		int mid = s + (e-s)/2;
  103. 		updateST(s,mid,ind,val,2*i+1);
  104. 		updateST(mid+1,e,ind,val,2*i+2);
  105. 	}
  106.  
  107. 	static Node delete(Node root,int val){
  108. 		if(root == null){
  109. 			return root;
  110. 		}
  111. 		if(val < root.val){
  112. 			root.left = delete(root.left,val);
  113. 		}else if(val > root.val){
  114. 			root.right = delete(root.right,val);
  115. 		}else{
  116. 			if(root.count > 1){
  117. 				root.count -= 1;
  118. 				root.sum -= 1;
  119. 				return root;
  120. 			}else{
  121. 				if(root.left == null){
  122. 					return root.right;
  123. 				}
  124. 				if(root.right == null){
  125. 					return root.left;
  126. 				}
  127. 				root.val = getSuc(root.right);
  128. 				root.right = delete(root.right,root.val);
  129. 			}
  130. 		}
  131. 		root.sum = root.count + getCount(root.left) + getCount(root.right);
  132. 		return root;
  133. 	}
  134.  
  135. 	static int getSuc(Node root){
  136. 		int val = root.val;
  137. 		while(root.left != null){
  138. 			root = root.left;
  139. 			val = root.val;
  140. 		}
  141. 		return val;
  142. 	}
  143.  
  144. 	static void constructST(int s,int e,int i){
  145. 		if(e < s){
  146. 			return ;
  147. 		}
  148. 		if(e == s){
  149. 			st[i] = insert(st[i],a[s]);
  150. 			return ;
  151. 		}
  152. 		int mid = s + (e-s)/2;
  153. 		constructST(s,mid,2*i+1);
  154. 		constructST(mid+1,e,2*i+2);
  155. 		for(int j=s;j<=e;j++){
  156. 			st[i] = insert(st[i],a[j]);
  157. 		}
  158. 	}
  159.  
  160. 	static Node insert(Node root,int val){
  161. 		if(root == null){
  162. 			return new Node(val);
  163. 		}
  164. 		if(val == root.val){
  165. 			root.count += 1;
  166. 			root.sum += 1;
  167. 			return root;
  168. 		}else if(val < root.val){
  169. 			root.left = insert(root.left,val);
  170. 		}else if(val > root.val){
  171. 			root.right = insert(root.right,val);
  172. 		}
  173. 		root.sum = getCount(root.left) + getCount(root.right) + root.count;
  174. 		return root;
  175. 	}
  176.  
  177. 	static int getCount(Node root){
  178. 		if(root == null){
  179. 			return 0;
  180. 		}else{
  181. 			return root.sum;
  182. 		}
  183. 	}
  184.  
  185. 	//For Fast I/O
  186. 	private static class InputReader{
  187.         private InputStream stream;
  188.         private byte[] buf = new byte[1024];
  189.         private int curChar;
  190.         private int numChars;
  191.         private SpaceCharFilter filter;
  192.  
  193.         public InputReader(InputStream stream){
  194.             this.stream = stream;
  195.         }
  196.  
  197.         public int read(){
  198.             if (numChars == -1)
  199.                 throw new InputMismatchException();
  200.             if (curChar >= numChars){
  201.                 curChar = 0;
  202.                 try{
  203.                     numChars = stream.read(buf);
  204.                 } catch (IOException e){
  205.                     throw new InputMismatchException();
  206.                 }
  207.                 if (numChars <= 0)
  208.                     return -1;
  209.             }
  210.             return buf[curChar++];
  211.         }
  212.  
  213.         public int readInt(){
  214.             int c = read();
  215.             while (isSpaceChar(c))
  216.                 c = read();
  217.             int sgn = 1;
  218.             if (c == '-'){
  219.                 sgn = -1;
  220.                 c = read();
  221.             }
  222.             int res = 0;
  223.             do{
  224.                 if (c < '0' || c > '9')
  225.                     throw new InputMismatchException();
  226.                 res *= 10;
  227.                 res += c - '0';
  228.                 c = read();
  229.             } while (!isSpaceChar(c));
  230.             return res * sgn;
  231.         }
  232.  
  233.         public String readString(){
  234.             int c = read();
  235.             while (isSpaceChar(c))
  236.                 c = read();
  237.             StringBuilder res = new StringBuilder();
  238.             do{
  239.                 res.appendCodePoint(c);
  240.                 c = read();
  241.             } while (!isSpaceChar(c));
  242.             return res.toString();
  243.         }
  244.  
  245.         public boolean isSpaceChar(int c){
  246.             if (filter != null)
  247.                 return filter.isSpaceChar(c);
  248.             return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
  249.         }
  250.  
  251.         public String next(){
  252.             return readString();
  253.         }
  254.  
  255.         public interface SpaceCharFilter{
  256.             public boolean isSpaceChar(int ch);
  257.         }
  258.     }
  259.  
  260.     private static class OutputWriter{
  261.         private final PrintWriter writer;
  262.  
  263.         public OutputWriter(OutputStream outputStream){
  264.             writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
  265.         }
  266.  
  267.         public OutputWriter(Writer writer){
  268.             this.writer = new PrintWriter(writer);
  269.         }
  270.  
  271.         public void print(Object... objects){
  272.             for (int i = 0; i < objects.length; i++){
  273.                 if (i != 0)
  274.                     writer.print(' ');
  275.                 writer.print(objects[i]);
  276.             }
  277.         }
  278.  
  279.         public void printLine(Object... objects) {
  280.             print(objects);
  281.             writer.println();
  282.         }
  283.  
  284.         public void close(){
  285.             writer.close();
  286.         }
  287.  
  288.         public void flush(){
  289.             writer.flush();
  290.         }
  291.     }
  292. } 
  293.  
Success #stdin #stdout 0.04s 4386816KB
comments (?)
stdin
copy 
5
5 1 2 3 4
6
1 2 4 1
0 4 10
1 4 4 4
0 3 1
0 1 2
1 1 5 2
stdout
copy 
2
1
2
https://ideone.com/7CNrkk
language:
Java (HotSpot 12)
created:
6 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!