-
Notifications
You must be signed in to change notification settings - Fork 0
/
wavelet.hpp
95 lines (93 loc) · 2.65 KB
/
wavelet.hpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#pragma once
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
*/