In this editorial, we denote \(A_l, A_{l+1} , \dots A_r = A[l,r]\).

This problem can be solved with a data structure called merge-sort tree as described below.

For simplicity, let us fix \(N=2^{18} = 262144\). (In this problem, one can set \(A_i = 2 \times 10^9\) for \(A_i (i > N)\).)

• The data structure holds an array obtained by sorting \(A[1,2^{18}]\).
• It also holds an array obtained by sorting \(A[1,2^{17}]\), and another for \(A[2^{17}+1,2^{18}]\), as the children of the first array.
• This is recursively repeated; i.e. as the children of the array \(A[l,r]\) sorted, arrays \(A[l,(l+r-1)/2]\) and \(A[(l+r+1)/2, r]\), sorted, are also stored.

Complex as it may seem on text, it is a segment-tree-like structure but stores sorted arrays in a nutshell. The time and spacial complexity on construction is \(O(N \log N)\).

If you also maintain the cumulative sums for each array as well, you can inspect nodes in the same manner as an ordinary segment tree, and perform binary search for each of the inspected arrays, so that the problem is solved in a total of \(O(Q \log^2 N)\) time. This algorithm is indeed online.

Sample code (C++):

#include<bits/stdc++.h>

#define MSTSZ 262144

using namespace std;

vector<long long> merge(vector<long long> l,vector<long long> r){
  vector<long long> res;
  long long lp=0,rp=0;
  while(lp<l.size() || rp<r.size()){
    if(lp==l.size()){res.push_back(r[rp]);rp++;}
    else if(rp==r.size()){res.push_back(l[lp]);lp++;}
    else if(l[lp]<r[rp]){res.push_back(l[lp]);lp++;}
    else{res.push_back(r[rp]);rp++;}
  }
  return res;
}

long long soll,solr;
long long solx;

long long solve(
  long long l,long long r,long long id,
  vector<vector<long long>> &mst,vector<vector<long long>> &sum){
  if(l>=r){return 0;}
  if(solr<l){return 0;}
  if((r-1)<soll){return 0;}

  if(soll<=l && (r-1)<=solr){
    long long nl=0,nr=mst[id].size()-1;
    while(nl<=nr){
      long long te=(nl+nr)/2;
      if(mst[id][te]<=solx){nl=te+1;}
      else{nr=te-1;}
    }
    if(nr>=0){return sum[id][nr];}
    return 0;
  }

  long long up=0;
  up+=solve(l,(l+r)/2,2*id+1,mst,sum);
  up+=solve((l+r)/2,r,2*id+2,mst,sum);
  return up;
}

int main(){
  int n;
  cin >> n;
  vector<long long> a(n);
  for(auto &nx : a){cin >> nx;}
  long long big=2e9;
  while(a.size()<MSTSZ){a.push_back(big);}

  vector<vector<long long>> mst(2*MSTSZ);

  for(int i=0;i<MSTSZ;i++){
    mst[(MSTSZ-1)+i].push_back(a[i]);
  }
  for(int i=MSTSZ-2;i>=0;i--){
    mst[i]=merge(mst[2*i+1],mst[2*i+2]);
  }

  vector<vector<long long>> sum=mst;
  for(auto &nx : sum){
    int l=nx.size();
    for(int i=1;i<l;i++){
      nx[i]+=nx[i-1];
    }
  }

  int q;
  cin >> q;
  long long b=0;
  vector<long long> res;
  while(q>0){
    q--;
    long long alp,bet,gam;
    cin >> alp >> bet >> gam;

    long long l=(alp^b);
    long long r=(bet^b);
    long long x=(gam^b);

    soll=l-1;
    solr=r-1;
    solx=x;

    b=solve(0,MSTSZ,0,mst,sum);
    res.push_back(b);
  }
  
  for(auto &nx : res){
    cout << nx << "\n";
  }
  return 0;
}