解説中では、 \(A_l, A_{l+1} , \dots A_r = A[l,r]\) と表現します。

以下のような merge-sort tree と呼ばれるデータ構造を用いるとこの問題に正解できます。

簡単のため、 \(N=2^{18} = 262144\) と固定しましょう。( 例えば、この問題では \(A_i (i > N)\) なる \(A_i\) について \(A_i = 2 \times 10^9\) としてしまえばよいです。 )

• まず、 \(A[1,2^{18}]\) をソートした配列を持ちます。
• この配列の子として、 \(A[1,2^{17}],A[2^{17}+1,2^{18}]\) をそれぞれソートした配列を持ちます。
• これを再帰的に繰り返します。すなわち、 \(A[l,r]\) をソートした配列の子として、 \(A[l,(l+r-1)/2], A[(l+r+1)/2, r]\) をソートした配列を持ちます。

言葉で書くと複雑ですが、実際は segment tree と同じような構造でソートした配列を持ちます。構築時の時間 / 空間計算量は \(O(N \log N)\) です。

この時、各配列に対してそれらの累積和も保持することとすると、 segment tree に対するアクセスと同じ要領を使いながらアクセスした各配列に対して二分探索することで、 \(O(Q \log^2 N)\) でこの問題に正解できます。
また、確かにこのアルゴリズムはオンラインです。

実装例 (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;
}