Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- Goal: Become better in CP!
- Key: Consistency and Discipline
- Desire: SDE @ Google USA
- Motto: Do what i Love <=> Love what i do
- If you don't use your brain 100%, it deteriorates gradually
- */
- import java.util.*;
- import java.io.*;
- import java.math.*;
- public class A2 {
- static StringBuffer str=new StringBuffer();
- static BufferedReader bf;
- static PrintWriter pw;
- static int n, q;
- static long a[];
- static long bit[];
- static long mod=(long)1e9+7;
- static long mod2=(long)1e9+3013;
- static long pow(long a, long b) {
- long res = 1;
- while (b > 0) {
- if (b % 2 == 1) res = (res * a + mod2)%mod2;
- a = (a * a + mod2)%mod2;
- b = b >> 1l;
- }
- return res;
- }
- static long query(int idx) {
- long sum = 0;
- idx++;
- while (idx > 0) {
- sum = (sum + bit[idx])%mod2;
- idx -= (idx & (-idx));
- }
- return sum;
- }
- static void update(int idx, long v) {
- idx++;
- while (idx <= n) {
- bit[idx] = (bit[idx] + v + mod2)%mod2;
- idx += (idx & (-idx));
- }
- }
- static void update(int l, int r, long v) {
- update(l, v);
- if ((r + 1) <= n) update(r + 1, -v);
- }
- static void solve(int te) throws Exception{
- long b[]=new long[n];
- Map<Long, Long> hashMap=new HashMap<>();
- // generate hash
- for(int i=0;i<n;i++){
- b[i]=pow(mod, a[i]-1)%mod2;
- hashMap.put(b[i], hashMap.getOrDefault(b[i], 0l)+1);
- }
- bit=new long[n+1];
- // stores hashes
- for(int i=0;i<n;i++){
- update(i, b[i]);
- }
- q=Integer.parseInt(bf.readLine().trim());
- int cnt=0;
- for(int i=0;i<q;i++){
- int type;
- String s[]=bf.readLine().trim().split("\\s+");
- type=Integer.parseInt(s[0]);
- if(type==1){
- int idx=Integer.parseInt(s[1]);
- idx--;
- long val=Long.parseLong(s[2]);
- hashMap.put(b[idx], hashMap.get(b[idx])-1);
- update(idx, -b[idx]);
- update(idx, pow(mod, val-1)%mod2);
- b[idx]=pow(mod, val-1)%mod2;
- hashMap.put(b[idx], hashMap.getOrDefault(b[idx], 0l)+1);
- }else{
- int l, r;
- l=Integer.parseInt(s[1]);
- r=Integer.parseInt(s[2]);
- l--;
- r--;
- int len=r-l+1;
- if(len%2==0){
- continue;
- }else{
- for(int x=l+len/2;x<=l+len/2+1;x++){
- long left=(query(x-1)-query(l-1)+mod2)%mod2;
- long right=(query(r)-query(x-1)+mod2)%mod2;
- long val=(x == l + len / 2 ? (right-left+mod2)%mod2 : (left-right+mod2)%mod2);
- if(hashMap.getOrDefault(val, 0l)>0){
- cnt++;
- break;
- }
- }
- }
- }
- }
- str.append("Case #").append(te).append(": ").append(cnt).append("\n");
- }
- public static void main(String[] args) throws java.lang.Exception {
- boolean lenv=true;
- int te=1;
- if(lenv){
- bf = new BufferedReader(
- new FileReader("input.txt"));
- pw=new PrintWriter(new
- BufferedWriter(new FileWriter("output.txt")));
- }else{
- bf = new BufferedReader(new InputStreamReader(System.in));
- pw = new PrintWriter(new OutputStreamWriter(System.out));
- }
- int q1 = Integer.parseInt(bf.readLine().trim());
- for(te=1;te<=q1;te++) {
- n=Integer.parseInt(bf.readLine().trim());
- String s[]=bf.readLine().trim().split("\\s+");
- a=new long[n];
- for(int i=0;i<n;i++) a[i]=Long.parseLong(s[i]);
- solve(te);
- }
- pw.print(str);
- pw.flush();
- // System.out.println(str);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement