RangeUpdateQuery RangeModuloQuery and RangeSumQuery
コードについての説明
区間更新 $a_i \leftarrow val (val \ge 0 とする) (i \in [l, r))$, 区間剰余更新 $a_i \leftarrow a_i \% val (val \ge 1 とする) (i \in [l, r))$, 区間和 $\underset{l \le i < r}{\mathrm{sum}} a_i$ のクエリを効率的に処理できる.
詳しくは ここの part2 に書いている. 計算量は $\O (\log ^2 n)$ と書いてあるがポテンシャルを考えると $\O(\log n \log \mathrm{MAX \_ VAL})$ だと思う. ならしの解析は これ と同じように行う.
セグ木が保持するノード($2n$ 個ぐらいある) に対応する区間 $[l, r)$ について $D(l, r)$ を区間 $[l, r)$ に含まれる数のうち異なる数 $a[k]$ の $\mathrm{ceil} (\log (a[k] + 1))$ の和とする. ただしここで区間内に値が $1$ 種類のみの場合は $0$ と定めることにする. またすべてのノードの $D(l, r)$ の和をポテンシャル $C$ とする. ここで $C = \O(n \log n \log \mathrm{MAX \_ VAL})$ であることに注意する.
区間更新にかかる実際の計算量は $\O (\log n)$ であるが、 区間更新に伴う $C$ の値の増加分を考えると, 中途半端に区間更新される部分($D(l, r)$ の一部だけが更新されるような区間 $[l, r)$) は $\O (\log n)$ 個なのでポテンシャルは全体で高々 $\O (\log n \log \mathrm{MAX \_ VAL})$ だけ増加する.
次に剰余更新 ($\% val$) の場合は $max \_ val[k] \neq min \_ val[k]$ かつ $max \_ val[k] \ge val$ の場合に通常の遅延更新より深く探索することになるが、このような探索を $1$ 度行うとその区間内の $D(l, r)$ の値が少なくとも $1$ 減る. これは区間内には $2$ 種類以上の数があること, $max \_ val[k] \ge val$ が成り立つこと, ある数 $p$ をそれ以下の数 $q$ で剰余をとったときに $p/2$ 未満になること, から言える.
以上より区間更新, 区間剰余更新のならし計算量は各回の $C$ の増加分および減少分と $C = \O (n \log n \log \mathrm{MAX \_ VAL})$ という事実を考えると $\O( \log n \log \mathrm{MAX \_ VAL})$ であることが分かる.
剰余更新の場合、 RangeAddQuery は上記のならしが回らないため相性が悪い.
時間計算量: 構築 $\O (n)$, query(区間和) $\O( \log n)$, update, modulo_update ならし $\O (\log n \log \mathrm{MAX \_ VAL})$ ($\mathrm{MAX \_ VAL}$ はデータの値の最大値とする)
コード
template<typename T> class segtree {
private:
int n,sz;
vector<T> node, min_val, max_val, lazy;
vector<bool> lazyFlag;
void update(int id){
node[id] = node[2*id+1] + node[2*id+2];
min_val[id] = min(min_val[2*id+1],min_val[2*id+2]);
max_val[id] = max(max_val[2*id+1],max_val[2*id+2]);
}
public:
segtree(const vector<T>& v) : n(1), sz((int)v.size()){
while(n < sz) n *= 2;
node.resize(2*n-1,0);
lazy.resize(2*n-1,0);
lazyFlag.resize(2*n-1,false);
min_val.resize(2*n-1,numeric_limits<T>::max());
max_val.resize(2*n-1,numeric_limits<T>::min());
for(int i = 0; i < sz; i++){
node[i+n-1] = min_val[i+n-1] = max_val[i+n-1] = v[i];
}
for(int i=n-2; i>=0; i--){
update(i);
}
}
void eval(int k, int l, int r) {
if(lazyFlag[k]){
node[k] = (r - l) * lazy[k];
min_val[k] = max_val[k] = lazy[k];
if(r - l > 1){
lazy[k*2+1] = lazy[k*2+2] = lazy[k];
lazyFlag[k*2+1] = lazyFlag[k*2+2] = true;
}
lazyFlag[k] = false;
}
}
void update(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){
return;
}
if(a <= l && r <= b){
lazy[k] = x;
lazyFlag[k] = true;
eval(k, l, r);
}else{
update(a, b, x, 2*k+1, l, (l+r)/2);
update(a, b, x, 2*k+2, (l+r)/2, r);
update(k);
}
}
void modulo_update(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 || max_val[k] < x){
return;
}
if(a <= l && r <= b && max_val[k] == min_val[k]) {
lazy[k] = max_val[k] % x;
lazyFlag[k] = true;
eval(k, l, r);
}else{
modulo_update(a, b, x, 2*k+1, l, (l+r)/2);
modulo_update(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 0;
}
if(a <= l && r <= b){
return node[k];
}
T vl = query(a, b, 2*k+1, l, (l+r)/2);
T vr = query(a, b, 2*k+2, (l+r)/2, r);
return vl + vr;
}
void print()
{
for(int i = 0; i < sz; i++){
cout << query(i,i+1) << " ";
}
cout << endl;
}
};
verify 用の問題
区間 mod, 一点更新, 区間和の verify
Codeforces : The Child and Sequence
提出コード