Advertisement
Ganesh1648

Untitled

Sep 27th, 2022 (edited)
996
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.75 KB | None | 0 0
  1. /*
  2.   Goal: Become better in CP!
  3.   Key: Consistency and Discipline
  4.   Desire: SDE @ Google USA
  5.   Motto: Do what i Love <=> Love what i do
  6.   If you don't use your brain 100%, it deteriorates gradually
  7. */
  8.  
  9. import java.util.*;
  10. import java.io.*;
  11. import java.math.*;
  12.  
  13. public class A2 {
  14.  
  15.   static StringBuffer str=new StringBuffer();
  16.   static BufferedReader bf;
  17.   static PrintWriter pw;
  18.   static int n, q;
  19.   static long a[];
  20.   static long bit[];
  21.   static long mod=(long)1e18+3;
  22.   static int N=(int)1e6+7;
  23.   static Map<Long, Long> z, zz;
  24.   static Random random;
  25.  
  26.   static void templateSortArray(long a[]) {
  27.     int n=a.length;
  28.     List < Long > l = new ArrayList < > ();
  29.     for (int i = 0; i < n; i++) l.add(a[i]);
  30.     Collections.sort(l);
  31.     for (int i = 0; i < n; i++) a[i] = l.get(i);
  32.   }
  33.  
  34.   static long myRand(long mod){
  35.     return random.nextLong()%mod;
  36.   }
  37.  
  38.   static void pre(){
  39.     z=new HashMap<>();
  40.     random=new Random(5);
  41.     for (long i = 0; i < N; i++) {
  42.       long val=myRand(mod);
  43.       z.put(i, val);
  44.     }
  45.   }
  46.  
  47.   static long query(int idx) {
  48.     long sum = 0;
  49.     idx++;
  50.     while (idx > 0) {
  51.         sum = (sum + bit[idx])%mod;
  52.         idx -= (idx & (-idx));
  53.     }
  54.     return sum;
  55.   }
  56.   static void update(int idx, long v) {
  57.     idx++;
  58.     while (idx <= n) {
  59.         bit[idx] = (bit[idx] + v + mod)%mod;
  60.         idx += (idx & (-idx));
  61.     }
  62.   }
  63.   static void update(int l, int r, long v) {
  64.     update(l, v);
  65.     if ((r + 1) <= n) update(r + 1, -v);
  66.   }
  67.  
  68.   static void solve(int te) throws Exception{
  69.     zz=new HashMap<>();
  70.     bit=new long[n+1];
  71.     // stores hashes
  72.     for(int i=0;i<n;i++){
  73.       update(i, z.get(a[i]));
  74.       zz.put(z.get(a[i]), zz.getOrDefault(z.get(a[i]), 0l)+1);
  75.     }
  76.     q=Integer.parseInt(bf.readLine().trim());
  77.     int cnt=0;
  78.     for(int i=0;i<q;i++){
  79.       int type;
  80.       String s[]=bf.readLine().trim().split("\\s+");
  81.       type=Integer.parseInt(s[0]);
  82.       if(type==1){
  83.         int idx=Integer.parseInt(s[1]);
  84.         idx--;
  85.         int val=Integer.parseInt(s[2]);
  86.         zz.put(z.get(a[idx]), zz.get(z.get(a[idx]))-1);
  87.         update(idx, -z.get(a[idx]));
  88.         a[idx]=val;
  89.         update(idx, z.get(a[idx]));
  90.         zz.put(z.get(a[idx]), zz.getOrDefault(z.get(a[idx]), 0l)+1);
  91.       }else{
  92.         int l, r;
  93.         l=Integer.parseInt(s[1]);
  94.         r=Integer.parseInt(s[2]);
  95.         l--;
  96.         r--;
  97.         int len=r-l+1;
  98.         if(len%2==0){
  99.           continue;
  100.         }else{
  101.           for(int x=l+len/2;x<=l+len/2+1;x++){
  102.             long left=(query(x-1)-query(l-1)+mod)%mod;
  103.             long right=(query(r)-query(x-1)+mod)%mod;
  104.             long val=(x == l + len / 2 ? (right-left+mod)%mod : (left-right+mod)%mod);
  105.             if(zz.getOrDefault(val, 0l)>0){
  106.               cnt++;
  107.               break;
  108.             }
  109.           }
  110.         }
  111.       }
  112.     }
  113.     str.append("Case #").append(te).append(": ").append(cnt).append("\n");
  114.   }
  115.  
  116.   public static void main(String[] args) throws java.lang.Exception {
  117.     boolean lenv=true;
  118.     int te=1;
  119.     if(lenv){
  120.       bf = new BufferedReader(
  121.                           new FileReader("input.txt"));
  122.       pw=new PrintWriter(new
  123.             BufferedWriter(new FileWriter("output.txt")));
  124.     }else{
  125.       bf = new BufferedReader(new InputStreamReader(System.in));
  126.       pw = new PrintWriter(new OutputStreamWriter(System.out));
  127.     }
  128.    
  129.     pre();
  130.     int q1 = Integer.parseInt(bf.readLine().trim());
  131.     for(te=1;te<=q1;te++) {
  132.       n=Integer.parseInt(bf.readLine().trim());
  133.       String s[]=bf.readLine().trim().split("\\s+");
  134.       a=new long[n];
  135.       for(int i=0;i<n;i++) a[i]=Long.parseLong(s[i]);
  136.       solve(te);
  137.     }
  138.     pw.print(str);
  139.     pw.flush();
  140.     // System.out.println(str);
  141.   }
  142. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement