kumaraditya1999

/* 
  These function returns the increment/decrement to the answer.
  The get function can be implemented using a bit tree of segtree,
  that would return the number of element in the range.
  The update function is also function of segtree/bit tree.
  that increment or decrements the value of element by 1.
*/
int add(int ele){
  // get the increment then add in the range
  int inc =  get(ele-d,ele+d);

kumaraditya1999

// the sort would sort the query in the way defined by the < operator in struct defination
sort(queries.begin(),queries.end()); 
  
  // initially the block is empty and the answer is zero
  int l=1,r=0,ans=0;

  // we will write add and del function separatly
  // they will return the value to be added/subtracted from the current answer
  // on insertion/ deletion of the new element

kumaraditya1999

int bs = sqrt(N); // bs refers to the block size

struct query{
    // i stores the index of the query, this is used later to print in the order of asking of queries
    // l is the left end of the query r is the right end of the query   
    // l/bs will give the block index of the query
    // for queries in the same block we sort them on the increaseing order of their r
    int i,l,r; 

    bool operator < (query b) const

kumaraditya1999

// constant query for range minimum
int query(int left,int right){
    int range_size = right-left+1;
//  find the highest power less than equal to range size
//  to find that we use the previousl caluculated log values
    int x = l[range_size];
    int min_value = min(m[left][x],m[right-(1<<x)+1][x]);
    return min_value;
}

kumaraditya1999

// here we will calculate the sum of an range
int query(int left,int right){
   int ans = 0;
  
  for(int i=logn;i>=0;i--){
    // if the current size of the range lies completly with the actual range take it
    if( (1<<i) <= right + left - 1 ){
      ans += sum[left][i];
      // change l to the next range's start
      left += (1<<i);

kumaraditya1999

// here we are building the sparse table for finding gcd of a range
void build(int n){
    
//   calculated to get the upper bound on the table size
    int logn = ceil(log2(n));

//   base condition, table[i][0] contains the value for range [i,i]
    for(int i=0;i<n;i++){
        g[i][0] = arr[i];
    }

kumaraditya1999

int query(int in,int qs,int qe,int ss,int se,int si){
    // process this range
    pushdown(in,si,ss,se);
 
    // if the segment range doesn't lie inside the query range return
    if(qs>se || qe<ss){
       return 0;
    }
    
    // if the query range lies completly inside return the answer

kumaraditya1999

void upd(int in,int qs,int qe,int ss,int se,int si,int v){
    // once you reach this node, update the node
    pushdown(in,si,ss,se);
    
    // if the node doesn't lie in the given range just go back
    if(qs>se || qe<ss){
       return;
    }
    
    // if it lies completly inside , update this node and return

kumaraditya1999

void pushdown(int in,int si,int ss,int se){
// if there is any update in this node process it 
// 1 in lazy node means that all the characters in this range have been set
// -1 in the lazy node means that all the characters in this range have been erased
    if(lazy[in][si]){
      // processing, the number of character would be equal to the lenght of this segment
      tree[in][si] = (lazy[in][si]==1)*(se-ss+1); 
      if(ss!=se){
        // if this node is node a leaf then send the lazy update to its children      
        lazy[in][2*si+1]=lazy[in][si];

kumaraditya1999

// us - update start, ue - update end, ss - segment start, se - segment end, si - segment index, val - value
void upd(ll us,ll ue,ll ss,ll se,ll si,ll val){
// if there is no intersection in update interval and this segment return
    if(us>se || ue<ss || us>qe || ss>se){
       return;
    }
  
// if this segment lies completly inside the update segment, then update the value and repalce the tree node with new one
    if(ss>=us && se<=ue){
        arr[ss] = val;