fork download 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4. using namespace __gnu_pbds;
  5. #define int long long
  6. #define oset tree < pair<int, int> ,  null_type ,  less<pair<int, int>> ,  rb_tree_tag ,  tree_order_statistics_node_update >
  7. using namespace std;
  8. set<int> subarrays;
  9. int findans(int x){ //The second type of query
  10.     //For any element k, the first element in the subarray of element k is -
  11.     //The largest element j in sa such j<=k
  12.  
  13.     //Find the first element j such that j > k
  14.     //j--; (The previous element)
  15.     auto it = subarrays.upper_bound(x);
  16.     it--;
  17.     return (*it);
  18. }
  19. void remove(int x){
  20.     subarrays.erase(x);
  21. }
  22. signed main(){
  23.     //N -> size of the array// N<=1e6
  24.     //A[N] positive integers
  25.     //We are dividing the entire array into subarrays
  26.     //If i and i+1 are in the same subarray then A(i+1)%A(i) == 0
  27.     //S(i) is the index of the subarray in which the ith element lies
  28.     //Q queries, Q = 2e5
  29.     //Changing A(i) to X
  30.     //2 i, we have to output the first element in the same subarray as i
  31.     //Required complexity is either O(Q) or O(Q.LogN)
  32.  
  33.     //In this problem, we have to form continuous subarrays
  34.     //For any index i, if A(i+1)%A(i) ==0, then we should place i+1 and i in the same subarray
  35.     //If we can place A(i), A(i+1) in the same subarray, then they should be in the same subarray
  36.  
  37.     //How do we store the partitions of the subarrays?
  38.  
  39.     //Since the subarrays are all contigious, we only need to store the first element of each subarray
  40.  
  41.     //{2, 6, 5, 10, 20, 3}
  42.     //{2, 6} -> index of the first element of each subarray
  43.     //{5, 10}
  44.     //{3}
  45.  
  46.     //sa
  47.     //{1 -> 1/2, 3 -> 3/4/5, 6 -> 6}
  48.     //For the second type of query, we need to output the first element of the subarray of index k
  49.     //For any element k, the first element in the subarray of element k is -
  50.     //The largest element j in sa such j<=k
  51.  
  52.     //We need a data structures that can:
  53.     //Store elements in a sorted order - set
  54.     //Erase elements in O(1) or O(LogN) - set
  55.     //Find the largest element j in sa such j<=k in O(1) or O(LogN) - set
  56.  
  57.     int n, q;
  58.     cin>>n>>q;
  59.     int a[n+1];
  60.     for(int i = 1;i<=n;i++) cin>>a[i];
  61.     //We need to create the subarrays
  62.     subarrays.insert(1); //1 will always be the start of some subarray
  63.     for(int i = 2;i<=n;i++){
  64.         //For any index i, if A(i+1)%A(i) ==0, then we should place i+1 and i in the same subarray
  65.         //If we can place A(i), A(i+1) in the same subarray, then they should be in the same subarray
  66.         if(a[i]%a[i-1] == 0) continue; //we can place i and i-1 in the same subarray
  67.         //we skip because we have already stored the start of the (i-1)th subarray
  68.         subarrays.insert(i); //When a[i] and a[i-1] could not be in the same subarray, we inserted i into the set
  69.     } //We have created the basic partitions before any queries took place
  70.  
  71.     while(q--){
  72.         int type, i;
  73.         cin>>type>>i;
  74.         if(type==1){
  75.             cin>>a[i]; //the updated value of a(i)
  76.             //There are 4 things that can happen
  77.             //a(i) and a(i-1) can now be in the same subarray -> DONE
  78.             //A(i) and A(i-1) can no longer be in the same subarray -> DONE
  79.             //A(i) and A(i+1) can now be in the same subarray -> DONE
  80.             //A(i) and A(i+1) can no longer be in the same subarray
  81.             if(i>1) {
  82.                 if ((findans(i) == i) &&
  83.                     ((a[i] % a[i - 1]) == 0)) { //now a[i] and a[i-1] should be in the same subarray
  84.                     //We need to reverse the operation on line 68
  85.                     remove(i);
  86.                 } else if ((findans(i) < i) &&
  87.                            ((a[i] % a[i - 1]) != 0)) { //this means a[i] and a[i-1] were in the same subarray
  88.                     //We need to perform the operation on line 68 to separate the elements
  89.                     subarrays.insert(i);
  90.                 }
  91.             }
  92.             if(i<n){
  93.                 if((findans(i+1)>i && ((a[i+1] % a[i]) == 0))){
  94.                     remove(i+1);
  95.                 }
  96.                 else if((findans(i+1)<=i) && ((a[i+1]%a[i])!=0)){
  97.                     subarrays.insert(i+1);
  98.                 }
  99.             }
  100.         }
  101.         else{
  102.             cout<<findans(i)<<endl;
  103.         }
  104.     }
  105. }
  106. //acdabcd
  107.  
Runtime error #stdin #stdout 0s 4316KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/L7U015
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!