Guest User

KQUERY2

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