KQUERYO - K-Query Online(vector in segtree , merege sort )

KQUERYO - K-Query Online

no tags 

Given a sequence of n numbers a1, a2, ..., an and a number of k- queries. A k-query is a triple (i, j, k) (1 ≤ i ≤ j ≤ n). For each k-query (i, j, k), you have to return the number of elements greater than k in the subsequence ai, ai+1, ..., aj.

Input

• Line 1: n (1 ≤ n ≤ 30000).
• Line 2: n numbers a1, a2, ..., an (1 ≤ ai ≤ 109).
• Line 3: q (1 ≤ q ≤ 200000), the number of k- queries.
• In the next q lines, each line contains 3 numbers a, b, c representing a k-query. You should do the following:
• i = a xor last_ans
• j = b xor last_ans
• k = c xor last_ans
• After that 1 ≤ i ≤ j ≤ n, 1 ≤ k ≤ 109  holds. 

Where last_ans = the answer to the last query (for the first query it's 0).

Output

• For each k-query (i, j, k), print the number of elements greater than k in the subsequence ai, ai+1, ..., aj in a single line.

Example

Input:

6
6
8 9 3 5 1 9
5
2 3 5
3 3 7
0 0 11
0 0 2
3 7 4

3 3 26 8 9 3 5 1 9 5 2 3 5 3 3 7 0 0 11 0 0 2 3 7 4


0 5

Output:
1
1
0
0
2
--------------------------------------editorial---------------------------------------------------

In this type of segment tree, for each node we have a vector (we may also have some other variables beside this) .

Example : Online approach for problem KQUERYO (I added this problem as the online version of KQUERY):

It will be nice if for each node, with interval [l, r) such that i ≤ l ≤ r ≤ j + 1 and this interval is maximal (it's parent's interval is not in the interval [i, j + 1) ), we can count the answer.

For that propose, we can keep all elements of al, al + 1, ..., ar in increasing order and use binary search for counting. So, memory will beO(n.log(n)) (each element is in O(log(n)) nodes ). We keep this sorted elements in verctor v[i] for i - th node. Also, we don't need to run sort on all node's vectors, for node i, we can merge v[2 * i] and v[2 * id + 1] (like merge sort) .

So, build function is like below :
void build(int id = 1,int l = 0,int r = n){
 if(r - l < 2){
  v[id].push_back(a[l]);
  return ;
 }
 int mid = (l+r)/2;
 build(2 * id, l, mid);
 build(2*id+1, mid, r);
 merge(v[2 * id].begin(), v[2 * id].end(), v[2 * id + 1].begin(), v[2 * id + 1].end(), back_inserter(v[id])); // read more about back_inserter in http://www.cplusplus.com/reference/iterator/back_inserter/
}

And function for solving queries :
int cnt(int x,int y,int k,int id = 1,int l = 0,int r  = n){// solve the query (x,y-1,k)
 if(x >= r or l >= y) return 0;
 if(x <= l && r <= n)
  return v[id].size() - (upper_bound(v[id].begin(), v[id].end(), k) - v[id].begin());
 int mid = (l+r)/2;
 return cnt(x, y, k, 2 * id, l, mid) +
     cnt(x, y, k, 2*id+1, mid, r) ;
}
--------------------------------code----------------------------------------------
#include<iostream>
using namespace std;
#include<bits/stdc++.h>
struct node
 {
  vector<int> v;
  
 } seg[300000];
int arr[300000];
 int val,qs,qe;
 void build(int index,int start,int end)
  {
   //cout<<start<<" "<<end<<endl;
   if(start==end)
    {
     seg[index].v.push_back(arr[start]);
     return ;
    }
    else if(start>end) return;
    int mid=(start+end)/2;
     build(2*index,start,mid);
     build(2*index+1,mid+1,end);
     
     int len1=seg[2*index].v.size();
     int len2=seg[2*index+1].v.size();
     int p=0,q=0;
     while(p!=len1 && q!=len2)
      {
         if(seg[2*index].v[p]<=seg[2*index+1].v[q])
          {
           seg[index].v.push_back(seg[2*index].v[p]);
           p++;
    }
    else
    {
     seg[index].v.push_back(seg[2*index+1].v[q]);
           q++;
    }
   }
   while(p<len1)
    {
     seg[index].v.push_back(seg[2*index].v[p]);
           p++;
    }
     while(q<len2)
    {
     seg[index].v.push_back(seg[2*index+1].v[q]);
           q++;
    }
    
 //   cout<<"vector of index "<<index<<endl;
 //   for(int i=0;i<seg[index].v.size();i++)
     {
  //     cout<<seg[index].v[i]<<" ";;
     }
  //    cout<<endl;
    
  
 }
 
 int query(int index,int start,int end)
  {
   
     if(start>end || start>qe || end<qs) return 0;
      if(qs<=start && qe>=end)
      {
       int re=0;
       if(lower_bound(seg[index].v.begin(),seg[index].v.end(),val+1)!=seg[index].v.end())
       {
   if(*lower_bound(seg[index].v.begin(),seg[index].v.end(),val+1)>val)
   re=lower_bound(seg[index].v.begin(),seg[index].v.end(),val+1)-seg[index].v.end();
   
}
        //  cout<<" from index "<<index<<" return "<<-re<<" se  "<<start<<"  "<<end<<endl;
           return -re;
           
             
   }
   int mid=(start+end)/2;
   
   int p1=query(2*index,start,mid);
   int p2=query(2*index+1,mid+1,end);
   return p1+p2;
  }
 
 int main()
  {
   ios_base::sync_with_stdio(0);
   cin.tie(0);

int n;
 cin>>n;
 for(int i=1;i<=n;i++)
  {
    cin>>arr[i];
  }
  build(1,1,n);
  int q;
   int ans=0;
   cin>>q;
   while(q--)
    {
      cin>>qs>>qe>>val;
      //qs-=1;
      //qe-=1;
      qs ^=ans;
      qe ^= ans;
      val ^= ans;
    //  cout<<qs<<"  "<<qe<<"  desdf "<<val<<endl;
      
      ans=query(1,1,n);
      cout<<ans<<endl;
      
 }
  }