Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // author: www.codechef.com/users/mayank12559
- import java.util.*;
- import java.io.*;
- class KQUERY2{
- static class Node{
- int val;
- Node left;
- Node right;
- int count;
- int sum;
- Node(int val){
- this.val = val;
- count = 1;
- sum = 1;
- left = null;
- right = null;
- }
- }
- static int n ;
- static int []a;
- static Node []st;
- static int count;
- public static void main(String []arg) throws IOException{
- InputReader in = new InputReader(System.in);
- OutputWriter out = new OutputWriter(System.out);
- n = in.readInt();
- a = new int[n];
- for(int i=0;i<n;i++){
- a[i] = in.readInt();
- }
- st = new Node[4*n];
- constructST(0,n-1,0);
- int m = in.readInt();
- while(m-- >0){
- int flag = in.readInt();
- if(flag == 0){
- int ind = in.readInt()-1;
- int val = in.readInt();
- updateST(0,n-1,ind,val,0);
- a[ind] = val;
- }else{
- int l = in.readInt()-1;
- int r = in.readInt()-1;
- int k = in.readInt();
- count = 0;
- query(0,n-1,l,r,k,0);
- System.out.println(count);
- }
- }
- }
- static void inOrder(Node root){
- if(root == null){
- return ;
- }
- if(root.left != null){
- inOrder(root.left);
- }
- System.out.print(root.val+" ");
- if(root.right != null){
- inOrder(root.right);
- }
- }
- static void query(int s,int e,int l,int r,int k,int i){
- if(l > e || r < s){
- return ;
- }
- if(l <= s && r >= e){
- search(st[i],k);
- return ;
- }
- int mid = s + (e-s)/2;
- query(s,mid,l,r,k,2*i+1);
- query(mid+1,e,l,r,k,2*i+2);
- }
- static void search(Node root,int val){
- if(root == null){
- return ;
- }
- if(val < root.val){
- count += (root.count+getCount(root.right));
- search(root.left,val);
- }else if(val > root.val){
- search(root.right,val);
- }else{
- count += getCount(root.right);
- }
- }
- static void updateST(int s,int e,int ind,int val,int i){
- if(e < s){
- return ;
- }
- if(ind < s || ind > e){
- return ;
- }
- st[i] = delete(st[i],a[ind], false);
- st[i] = insert(st[i],val);
- if(s == e){
- return ;
- }
- int mid = s + (e-s)/2;
- updateST(s,mid,ind,val,2*i+1);
- updateST(mid+1,e,ind,val,2*i+2);
- }
- static Node delete(Node root, int val, boolean deleteAll){
- if(root == null){
- return root;
- }
- if(val < root.val){
- root.left = delete(root.left,val, deleteAll);
- }else if(val > root.val){
- root.right = delete(root.right,val, deleteAll);
- }else{
- if(deleteAll || root.count==1){
- if(root.left == null){
- return root.right;
- }
- if(root.right == null){
- return root.left;
- }
- // changes here
- Node tmp = getSuc(root.right);
- root.val = tmp.val;
- root.count = tmp.count;
- root.right = delete(root.right, root.val, true);
- }else{
- root.count -= 1;
- root.sum -= 1;
- return root;
- }
- }
- root.sum = root.count + getCount(root.left) + getCount(root.right);
- return root;
- }
- // changes here
- static Node getSuc(Node root){
- while(root.left != null)
- root = root.left;
- return root;
- }
- static void constructST(int s,int e,int i){
- if(e < s){
- return ;
- }
- if(e == s){
- st[i] = insert(st[i],a[s]);
- return ;
- }
- int mid = s + (e-s)/2;
- constructST(s,mid,2*i+1);
- constructST(mid+1,e,2*i+2);
- for(int j=s;j<=e;j++){
- st[i] = insert(st[i],a[j]);
- }
- }
- static Node insert(Node root,int val){
- if(root == null){
- return new Node(val);
- }
- if(val == root.val){
- root.count += 1;
- root.sum += 1;
- return root;
- }else if(val < root.val){
- root.left = insert(root.left,val);
- }else if(val > root.val){
- root.right = insert(root.right,val);
- }
- root.sum = getCount(root.left) + getCount(root.right) + root.count;
- return root;
- }
- static int getCount(Node root){
- if(root == null){
- return 0;
- }else{
- return root.sum;
- }
- }
- //For Fast I/O
- private static class InputReader{
- private InputStream stream;
- private byte[] buf = new byte[1024];
- private int curChar;
- private int numChars;
- private SpaceCharFilter filter;
- public InputReader(InputStream stream){
- this.stream = stream;
- }
- public int read(){
- if (numChars == -1)
- throw new InputMismatchException();
- if (curChar >= numChars){
- curChar = 0;
- try{
- numChars = stream.read(buf);
- } catch (IOException e){
- throw new InputMismatchException();
- }
- if (numChars <= 0)
- return -1;
- }
- return buf[curChar++];
- }
- public int readInt(){
- int c = read();
- while (isSpaceChar(c))
- c = read();
- int sgn = 1;
- if (c == '-'){
- sgn = -1;
- c = read();
- }
- int res = 0;
- do{
- if (c < '0' || c > '9')
- throw new InputMismatchException();
- res *= 10;
- res += c - '0';
- c = read();
- } while (!isSpaceChar(c));
- return res * sgn;
- }
- public String readString(){
- int c = read();
- while (isSpaceChar(c))
- c = read();
- StringBuilder res = new StringBuilder();
- do{
- res.appendCodePoint(c);
- c = read();
- } while (!isSpaceChar(c));
- return res.toString();
- }
- public boolean isSpaceChar(int c){
- if (filter != null)
- return filter.isSpaceChar(c);
- return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
- }
- public String next(){
- return readString();
- }
- public interface SpaceCharFilter{
- public boolean isSpaceChar(int ch);
- }
- }
- private static class OutputWriter{
- private final PrintWriter writer;
- public OutputWriter(OutputStream outputStream){
- writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
- }
- public OutputWriter(Writer writer){
- this.writer = new PrintWriter(writer);
- }
- public void print(Object... objects){
- for (int i = 0; i < objects.length; i++){
- if (i != 0)
- writer.print(' ');
- writer.print(objects[i]);
- }
- }
- public void printLine(Object... objects) {
- print(objects);
- writer.println();
- }
- public void close(){
- writer.close();
- }
- public void flush(){
- writer.flush();
- }
- }
- }
Add Comment
Please, Sign In to add comment