Guest User

KGSS

a guest
Jan 19th, 2021
41
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.io.*;
  2.  
  3. class Spoj
  4. {
  5.     public static void main(String args[])throws Exception
  6.     {
  7.         BufferedReader bu=new BufferedReader(new InputStreamReader(System.in));
  8.         StringBuilder sb=new StringBuilder();
  9.         int n=Integer.parseInt(bu.readLine());
  10.         int i;
  11.         String s[]=bu.readLine().split(" ");
  12.         for(i=0;i<n;i++)
  13.         {
  14.             a[i]=Integer.parseInt(s[i]);
  15.             update(0,n-1,i,0);
  16.         }
  17.         int q=Integer.parseInt(bu.readLine());
  18.         while(q-->0)
  19.         {
  20.             s=bu.readLine().split(" ");
  21.             int x=Integer.parseInt(s[1])-1,y=Integer.parseInt(s[2]);
  22.             if(s[0].equals("U"))
  23.             {
  24.                 a[x]=y;
  25.                 update(0,n-1,x,0);
  26.             }
  27.             else
  28.             {
  29.                 y--;
  30.                 int m1=query(0,n-1,x,y,0),tem=a[m1];
  31.                 a[m1]=0; update(0,n-1,m1,0);
  32.  
  33.                 int m2=query(0,n-1,x,y,0);
  34.                 sb.append(tem+a[m2]+"\n");
  35.                 a[m1]=tem;
  36.                 update(0,n-1,m1,0);
  37.             }
  38.         }
  39.         System.out.print(sb);
  40.     }
  41.     static int N=100000,st[]=new int[4*N],a[]=new int[N];
  42.  
  43.     static void update(int ss,int se,int i,int n)
  44.     {
  45.         if(i<ss || i>se) return;
  46.         if(ss==se) st[n]=i;
  47.         else
  48.         {
  49.             int m=ss+(se-ss)/2;
  50.             if(i>=ss && i<=m) update(ss,m,i,2*n+1);
  51.             else update(m+1,se,i,2*n+2);
  52.             if(a[st[2*n+1]]>a[st[2*n+2]]) st[n]=st[2*n+1];
  53.             else st[n]=st[2*n+2];
  54.         }
  55.     }
  56.  
  57.     static int query(int ss,int se,int qs,int qe,int n)
  58.     {
  59.         if(qs<=ss && qe>=se) return st[n];
  60.         if(se<qs || ss>qe) return -1;
  61.  
  62.         int m=ss+(se-ss)/2;
  63.         int e1=query(ss,m,qs,qe,2*n+1),e2=query(m+1,se,qs,qe,2*n+2);
  64.         if(e1==-1 && e2==-1) return -1;
  65.         else if(e1!=-1 && e2==-1) return e1;
  66.         else if(e1==-1 && e2!=-1) return e2;
  67.         else
  68.         {
  69.             if(a[e1]>a[e2]) return e1;
  70.             else return e2;
  71.         }
  72.     }
  73. }
RAW Paste Data