library
This documentation is automatically generated by online-judge-tools/verification-helper
Range LIS Query
(DataStructure/rangelis.hpp)
- View this file on GitHub
- Last update: 2023-01-17 00:59:32+09:00
- Include:
#include "DataStructure/rangelis.hpp"
Depends on
Verified with
Code
#pragma once
#include "DataStructure/wavelet.hpp"
struct RangeLIS{
WaveletMatrix<int> wm;
int N;
RangeLIS(vector<int> p){
N=1;
while(N<int(p.size()))N<<=1;
rep(i,p.size(),N)p.push_back(i);
auto init=seaweed(p);
wm=WaveletMatrix<int>(init);
}
int query(int L,int R){
if(L>=R)return 0;
return R-L-wm.freq(0,R,L,N);
}
private:
vector<int> seaweed(const vector<int>& p){
int n=p.size();
if(n==1)return {inf};
vector<int> lo,hi,lpos,hpos;
rep(i,0,n){
if(p[i]<n/2){
lo.push_back(p[i]);
lpos.push_back(i);
}
else{
hi.push_back(p[i]-n/2);
hpos.push_back(i);
}
}
auto x=seaweed(lo),y=seaweed(hi);
vector<int> s(n),t(n);
iota(ALL(s),0);
iota(ALL(t),0);
int xi=0,yi=0;
rep(i,0,n){
if(p[i]<n/2){
if(x[xi]==inf)s[i]=inf;
else s[i]=lpos[x[xi]];
xi++;
}
else{
if(y[yi]==inf)t[i]=inf;
else t[i]=hpos[y[yi]];
yi++;
}
}
vector<int> a(n,inf),b(n);
vector<int> revs(n,inf);
rep(i,0,n)if(s[i]!=inf)revs[s[i]]=i;
int pos=n-1;
vector<int> tos(n,inf),tot(n,inf);
for(int i=n-1;i>=0;i--)if(revs[i]!=inf){
a[revs[i]]=pos;
tos[pos--]=i;
}
rep(i,0,n)if(a[i]==inf)a[i]=pos--;
pos=0;
vector<int> used(n);
rep(i,0,n)if(t[i]!=inf){
b[pos]=t[i];
tot[pos++]=i;
used[t[i]]=1;
}
rep(i,0,n)if(!used[i]){
b[pos++]=i;
}
auto c=squaredot(a,b);
vector<int> res(n,inf);
rep(i,0,n)if(tot[i]!=inf and tos[c[i]]!=inf){
res[tot[i]]=tos[c[i]];
}
return res;
}
vector<int> squaredot(const vector<int>& a,const vector<int>& b){
int n=a.size();
if(n==1)return {0};
vector<int> alo,ahi,blo,bhi;
vector<int> inva(n);
rep(i,0,n)inva[a[i]]=i;
int aloi=0,ahii=0;
vector<int> azip(n),alov,ahiv;
rep(i,0,n){
if(inva[i]<n/2){
azip[inva[i]]=aloi++;
alov.push_back(i);
}
else{
azip[inva[i]]=ahii++;
ahiv.push_back(i);
}
if(b[i]<n/2)blo.push_back(b[i]);
else bhi.push_back(b[i]-n/2);
}
rep(i,0,n){
if(i<n/2)alo.push_back(azip[i]);
else ahi.push_back(azip[i]);
}
auto sublo=squaredot(alo,blo);
auto subhi=squaredot(ahi,bhi);
vector<int> clo(n,inf),chi(n,inf),res(n,inf);
int subloi=0,subhii=0;
rep(i,0,n){
if(b[i]<n/2)clo[i]=alov[sublo[subloi++]];
else chi[i]=ahiv[subhi[subhii++]];
}
vector<int> invclo(n,inf),invchi(n,inf);
rep(i,0,n){
if(clo[i]!=inf)invclo[clo[i]]=i;
if(chi[i]!=inf)invchi[chi[i]]=i;
}
int cloi=n,cloj=-1,chii=n,chij=-1;
int ldelta=0,hdelta=0;
for(;;){
if(cloi<0 and chij>=n)break;
if(ldelta>0){
cloj++;
if(cloj<n and chi[cloj]!=inf and chi[cloj]<cloi)ldelta--;
if(cloj<n and clo[cloj]!=inf and clo[cloj]>=cloi)ldelta--;
}
else{
cloi--;
if(cloi>=0 and invchi[cloi]!=inf and invchi[cloi]<=cloj)ldelta++;
if(cloi>=0 and invclo[cloi]!=inf and invclo[cloi]>cloj)ldelta++;
}
if(0<=cloj and cloj<n and clo[cloj]!=inf and clo[cloj]<=cloi)res[cloj]=clo[cloj];
if(hdelta>=0){
chij++;
if(chij<n and chi[chij]!=inf and chi[chij]<chii)hdelta--;
if(chij<n and clo[chij]!=inf and clo[chij]>=chii)hdelta--;
}
else{
chii--;
if(chii>=0 and invchi[chii]!=inf and invchi[chii]<=chij)hdelta++;
if(chii>=0 and invclo[chii]!=inf and invclo[chii]>chij)hdelta++;
}
if(0<=chij and chij<n and chi[chij]!=inf and chi[chij]>=chii)res[chij]=chi[chij];
if(cloi==chii and cloj==chij)res[cloj]=cloi;
}
return res;
}
};
/**
* @brief Range LIS Query
*/#line 2 "DataStructure/wavelet.hpp"
template<typename T>struct WaveletMatrix{
struct BitVector{
vector<unsigned long long> buf;
vector<int> rui;
BitVector(const vector<char>& a={}){
int n=a.size();
buf.assign((n+63)>>6,0);
rui.assign(buf.size()+1,0);
rep(i,0,n)if(a[i]){
buf[i>>6]|=1ull<<(i&63);
rui[(i>>6)+1]++;
}
rep(i,0,buf.size())rui[i+1]+=rui[i];
}
int rank(int k,bool f=1){
int ret=rui[k>>6]+__builtin_popcountll(buf[k>>6]&((1ull<<(k&63))-1));
if(!f)return k-ret;
else return ret;
}
};
int N,lg;
vector<int> mid;
vector<BitVector> buf;
WaveletMatrix(){}
WaveletMatrix(vector<T> a):N(a.size()),lg(0){
T mx=0;
for(auto& x:a)chmax(mx,x);
while((T(1)<<lg)<=mx)lg++;
mid.resize(lg);
buf.resize(lg);
for(int d=lg-1;d>=0;d--){
vector<char> add;
vector nxt(2,vector<T>());
for(auto& x:a){
add.push_back(x>>d&1);
nxt[x>>d&1].push_back(x);
}
mid[d]=(int)nxt[0].size();
buf[d]=BitVector(add);
swap(a,nxt[0]);
a.insert(a.end(),ALL(nxt[1]));
}
}
int rank(int L,int R,T x){
if((T(1)<<lg)<=x)return 0;
for(int d=lg-1;d>=0;d--){
bool f=(x>>d&1);
L=buf[d].rank(L,f)+(f?mid[d]:0);
R=buf[d].rank(R,f)+(f?mid[d]:0);
}
return R-L;
}
T quantile(int L,int R,int k){
T ret=0;
for(int d=lg-1;d>=0;d--){
int l0=buf[d].rank(L,0),r0=buf[d].rank(R,0);
if(k<r0-l0)L=l0,R=r0;
else{
k-=r0-l0;
ret|=T(1)<<d;
L+=mid[d]-l0,R+=mid[d]-r0;
}
}
return ret;
}
int freq(int L,int R,T x){
if((T(1)<<lg)<=x)return R-L;
int ret=0;
for(int d=lg-1;d>=0;d--){
bool f=(x>>d&1);
if(f)ret+=buf[d].rank(R,0)-buf[d].rank(L,0);
L=buf[d].rank(L,f)+(f?mid[d]:0);
R=buf[d].rank(R,f)+(f?mid[d]:0);
}
return ret;
}
int freq(int L,int R,T a,T b){
return freq(L,R,b)-freq(L,R,a);
}
T prev(int L,int R,T x){
int cnt=freq(L,R,x);
return cnt==R-L?T(-1):quantile(L,R,cnt);
}
T next(int L,int R,T x){
int cnt=freq(L,R,x);
return cnt==0?T(-1):quantile(L,R,cnt-1);
}
};
/**
* @brief Wavelet Matrix
* @docs docs/wavelet.md
*/
#line 3 "DataStructure/rangelis.hpp"
struct RangeLIS{
WaveletMatrix<int> wm;
int N;
RangeLIS(vector<int> p){
N=1;
while(N<int(p.size()))N<<=1;
rep(i,p.size(),N)p.push_back(i);
auto init=seaweed(p);
wm=WaveletMatrix<int>(init);
}
int query(int L,int R){
if(L>=R)return 0;
return R-L-wm.freq(0,R,L,N);
}
private:
vector<int> seaweed(const vector<int>& p){
int n=p.size();
if(n==1)return {inf};
vector<int> lo,hi,lpos,hpos;
rep(i,0,n){
if(p[i]<n/2){
lo.push_back(p[i]);
lpos.push_back(i);
}
else{
hi.push_back(p[i]-n/2);
hpos.push_back(i);
}
}
auto x=seaweed(lo),y=seaweed(hi);
vector<int> s(n),t(n);
iota(ALL(s),0);
iota(ALL(t),0);
int xi=0,yi=0;
rep(i,0,n){
if(p[i]<n/2){
if(x[xi]==inf)s[i]=inf;
else s[i]=lpos[x[xi]];
xi++;
}
else{
if(y[yi]==inf)t[i]=inf;
else t[i]=hpos[y[yi]];
yi++;
}
}
vector<int> a(n,inf),b(n);
vector<int> revs(n,inf);
rep(i,0,n)if(s[i]!=inf)revs[s[i]]=i;
int pos=n-1;
vector<int> tos(n,inf),tot(n,inf);
for(int i=n-1;i>=0;i--)if(revs[i]!=inf){
a[revs[i]]=pos;
tos[pos--]=i;
}
rep(i,0,n)if(a[i]==inf)a[i]=pos--;
pos=0;
vector<int> used(n);
rep(i,0,n)if(t[i]!=inf){
b[pos]=t[i];
tot[pos++]=i;
used[t[i]]=1;
}
rep(i,0,n)if(!used[i]){
b[pos++]=i;
}
auto c=squaredot(a,b);
vector<int> res(n,inf);
rep(i,0,n)if(tot[i]!=inf and tos[c[i]]!=inf){
res[tot[i]]=tos[c[i]];
}
return res;
}
vector<int> squaredot(const vector<int>& a,const vector<int>& b){
int n=a.size();
if(n==1)return {0};
vector<int> alo,ahi,blo,bhi;
vector<int> inva(n);
rep(i,0,n)inva[a[i]]=i;
int aloi=0,ahii=0;
vector<int> azip(n),alov,ahiv;
rep(i,0,n){
if(inva[i]<n/2){
azip[inva[i]]=aloi++;
alov.push_back(i);
}
else{
azip[inva[i]]=ahii++;
ahiv.push_back(i);
}
if(b[i]<n/2)blo.push_back(b[i]);
else bhi.push_back(b[i]-n/2);
}
rep(i,0,n){
if(i<n/2)alo.push_back(azip[i]);
else ahi.push_back(azip[i]);
}
auto sublo=squaredot(alo,blo);
auto subhi=squaredot(ahi,bhi);
vector<int> clo(n,inf),chi(n,inf),res(n,inf);
int subloi=0,subhii=0;
rep(i,0,n){
if(b[i]<n/2)clo[i]=alov[sublo[subloi++]];
else chi[i]=ahiv[subhi[subhii++]];
}
vector<int> invclo(n,inf),invchi(n,inf);
rep(i,0,n){
if(clo[i]!=inf)invclo[clo[i]]=i;
if(chi[i]!=inf)invchi[chi[i]]=i;
}
int cloi=n,cloj=-1,chii=n,chij=-1;
int ldelta=0,hdelta=0;
for(;;){
if(cloi<0 and chij>=n)break;
if(ldelta>0){
cloj++;
if(cloj<n and chi[cloj]!=inf and chi[cloj]<cloi)ldelta--;
if(cloj<n and clo[cloj]!=inf and clo[cloj]>=cloi)ldelta--;
}
else{
cloi--;
if(cloi>=0 and invchi[cloi]!=inf and invchi[cloi]<=cloj)ldelta++;
if(cloi>=0 and invclo[cloi]!=inf and invclo[cloi]>cloj)ldelta++;
}
if(0<=cloj and cloj<n and clo[cloj]!=inf and clo[cloj]<=cloi)res[cloj]=clo[cloj];
if(hdelta>=0){
chij++;
if(chij<n and chi[chij]!=inf and chi[chij]<chii)hdelta--;
if(chij<n and clo[chij]!=inf and clo[chij]>=chii)hdelta--;
}
else{
chii--;
if(chii>=0 and invchi[chii]!=inf and invchi[chii]<=chij)hdelta++;
if(chii>=0 and invclo[chii]!=inf and invclo[chii]>chij)hdelta++;
}
if(0<=chij and chij<n and chi[chij]!=inf and chi[chij]>=chii)res[chij]=chi[chij];
if(cloi==chii and cloj==chij)res[cloj]=cloi;
}
return res;
}
};
/**
* @brief Range LIS Query
*/