RangeAndUpdateQuery RangeOrUpdateQuery and RangeMinQuery
コードについての説明
区間 and 更新 $a_i \leftarrow a_i \& val (i \in [l, r))$, 区間 or 更新 $a_i \leftarrow a_i | val (i \in [l, r))$, 区間最小値 $\underset{l \le i < r}{\min} a_i$ のクエリを効率的に処理できる.
CSAcademy の And or Max で出てきたデータ構造. ならしの解析は これ と同じように行う.
以下では CSAcademy の解説とは異なり, ハミング距離をポテンシャルとしてならし計算量を解析する(このように解析すると計算量が落ちるので).
セグ木が保持するノード($2n$ 個ぐらいある) に対応する区間 $[l, r)$ について $D(l, r)$ を区間 $[l, r)$ に含まれる数の全要素の and と全要素の or の間のハミング距離とする. またすべてのノードの $D(l, r)$ の和を $C$ とする. ここで $C = \O (n \log \mathrm{MAX \_ VAL})$ であることに注意する.
range_and の "$({\scriptsize \sim}x \& \_ and[k]) = ({\scriptsize \sim}x \& \_ or[k])$" の意味は $\& x$ を取ることによって消えるビットが $\_ and[k]$ と $\_ or[k]$ で等しいということを意味していて言い換えると, $\& x$ を区間減算と見ることのできるような区間という意味になる(区間内のすべての数から一様に立っていたビットが消えるので).
同様に range_or の "$(x \& {\scriptsize \sim}\_ or[k]) = (x \& {\scriptsize \sim}\_ and[k])$" の意味は $| x$ を取ることによって増えるビットが $\_ and[k]$ と $\_ or[k]$ で等しいということを意味していて言い換えると, $| x$ を区間加算と見ることのできるような区間という意味になる(区間内のすべての数に一様にビットを立てるので).
このとき range_and で "$({\scriptsize \sim}x \& \_ and[k]) \neq ({\scriptsize \sim}x \& \_ or[k])$" となる場合つまり余分に探索する場合は探索後 ${\scriptsize \sim}x \& \_ and[k] と {\scriptsize \sim}x \& \_ or[k]$ が等しくなるので少なくともその区間の $D(l,r)$ は $1$ 小さくなる. 同様に range_or で
"$(x \& {\scriptsize \sim}\_ and[k]) \neq (x \& {\scriptsize \sim}\_ or[k])$" となる場合つまり余分に探索する場合は探索後 $x \& {\scriptsize \sim}\_ and[k]$ と $x \& {\scriptsize \sim}\_ or[k]$ が等しくなるので少なくともその区間の $D(l, r)$ は $1$ 小さくなる.
よって $C = \O (n \log \mathrm{MAX \_ VAL})$ と合わせて各クエリのならし計算量は $\O (\max(\log n, \log \mathrm{MAX \_ VAL}))$ となる.
RangeUpdateQuery や RangeSumQuery を加えたりは容易にできるが, RangeAddQuery はならしが回らないので相性が悪い.
時間計算量: 各クエリならし $\O (\max(\log n, \log \mathrm{MAX \_ VAL}))$
コード
template<typename T> class segtree
{
private:
int n,sz;
vector<T> node, _and, _or, lazy;
void update(int id){
node[id] = min(node[2*id+1],node[2*id+2]);
_and[id] = (_and[2*id+1] & _and[2*id+2]);
_or[id] = (_or[2*id+1] | _or[2*id+2]);
}
void eval(int k, int l, int r){
if(lazy[k] != 0){
node[k] += lazy[k], _and[k] += lazy[k], _or[k] += lazy[k];
if(r - l > 1) {
lazy[2*k+1] += lazy[k], lazy[2*k+2] += lazy[k];
}
lazy[k] = 0;
}
}
public:
segtree(const vector<T>& v) : n(1), sz((int)v.size()){
while(n < sz) n *= 2;
node.resize(2*n-1, numeric_limits<T>::max()), _and.resize(2*n-1, 0);
_or.resize(2*n-1, 0), lazy.resize(2*n-1, 0);
for(int i = 0; i < sz; i++){
node[i+n-1] = _and[i+n-1] = _or[i+n-1] = v[i];
}
for(int i=n-2; i>=0; i--){
update(i);
}
}
void range_and(int a, int b, T x, int k=0, int l=0, int r=-1){
if(r < 0) r = n;
eval(k, l, r);
if(b <= l || r <= a || !(~x & _or[k])){
return;
}
if(a <= l && r <= b && (~x & _and[k]) == (~x & _or[k])){
lazy[k] -= (~x & _and[k]);
eval(k,l,r);
}else{
range_and(a, b, x, 2*k+1, l, (l+r)/2), range_and(a, b, x, 2*k+2, (l+r)/2, r);
update(k);
}
}
void range_or(int a, int b, T x, int k=0, int l=0, int r=-1){
if(r < 0) r = n;
eval(k, l, r);
if(b <= l || r <= a || !(x & ~_and[k])){
return;
}
if(a <= l && r <= b && (x & ~_or[k]) == (x & ~_and[k])){
lazy[k] += (x & ~_or[k]);
eval(k,l,r);
}else{
range_or(a, b, x, 2*k+1, l, (l+r)/2), range_or(a, b, x, 2*k+2, (l+r)/2, r);
update(k);
}
}
T query(int a, int b, int k=0, int l=0, int r=-1){
if(r < 0) r = n;
eval(k, l, r);
if(b <= l || r <= a){
return numeric_limits<T>::max();
}
if(a <= l && r <= b){
return node[k];
}
T vl = query(a, b, 2*k+1, l, (l+r)/2), vr = query(a, b, 2*k+2, (l+r)/2, r);
return min(vl,vr);
}
void print(){
for(int i = 0; i < sz; i++){
cout << query(i,i+1) << " ";
}
cout << endl;
}
};
verify 用の問題
CSAcademy : And or Max 提出コード