MergeSortTree

概要

セグ木状に、ソートされた整数列を保持する。

区間の中でL以上R以下の個数みたいなクエリが処理できる？ WaveletMatrixと同じ感じ

総和を取得したい時は、累積和を取った整数列も同じ場所に保持する必要がある。

実装例

code:cpp

vector<ll>merge(vector<ll>l,vector<ll>r){

for(auto i:r)l.push_back(i);

sort(ALL(l));

return l;

}

ll soll,solr,solx;

vector<vector<ll>>mst,Sum;

ll query(ll l,ll r,ll id){

if(l>=r)return 0;

if(solr<l)return 0;

if(soll>r-1)return 0;

if(soll<=l && r-1<=solr){

while(nl<=nr){

ll mid = (nl+nr)/2;

else nr = mid-1;

}

return 0;

}

ll up{};

up += query(l,(l+r)/2,2*id+1);

up += query((l+r)/2,r,2*id+2);

return up;

}

ll X = 262144;

bool solve(){

LL(n);

vector<ll>a(n);cin >> a;

while(a.size()<X)a.push_back(INF);

mst.resize(X*2);

rep(i,X){

}

for(int i =X-2;i>=0;i--){

}

Sum = mst;

for(auto&i:Sum){

rep(j,1,i.size()){

}

}

LL(q);

ll ans{};

for(;q--;){

LL(A,B,C);

A^=ans;

B^=ans;

C^=ans;

soll = A-1,solr = B-1,solx=C;

ans = query(0,X,0);

cout<<ans<<endl;

}

return false;

}