AtCoder Library Practice Contest L - Lazy Segment Tree
遅延セグ木の問題その$ 3 ！転倒数を管理する遅延セグ木！
考えたこと
クエリ$ 1 は範囲 flip 更新、クエリ$ 2 は範囲転倒数取得なので、遅延セグメント木を使うであろうと推測できる。
data の型と二項演算$ \text{op} 、単位元$ e の指定
さて、 data 配列の型を考えるために、クエリ$ 2 のみをさばけるようなモノイドを考える。
$ A(a, b) を配列$ A の区間$ [a, b) の部分文字列、$ T(a, b) を$ A(a, b) の転倒数とする。このとき、
「$ A(a, b) に関する情報」$ + 「$ A(b, c) に関する情報」$ = 「$ A(a, c) に関する情報」
「$ A(a, b) に関する情報」には$ T(a, b) が含まれている
を満たすような情報をうまく選んで data 配列で管理する必要がある。ここで$ T(a, c) の値を$ T(a, b), T(b, c) の値を用いて求められないか考えると、以下の事実に気づく。
$ T(a, c)=T(a, b)+T(b, c) $ + 「$ A(a, b) の$ 1 の個数」$ \times 「$ A(b, c) の$ 0 の個数」
これは平面走査の転倒数の求め方のアプローチみたく$ A(b, c) 上の$ 0 に注目すると分かる。
https://scrapbox.io/files/66f7ee20ceab8a001d122ec8.png
よって、 data は「$ T(a, b) 」「$ A(a, b) の$ 0 の個数」「$ A(a, b) の$ 1 の個数」の tuple を管理すれば良いことになる。
$ Z(a, b):= A(a, b) の$ 0 の個数
$ O(a, b):= A(a, b) の$ 1 の個数
としたときの二項演算$ \text{op} を図に示す。また、この操作の単位元$ e は$ \{0, 0, 0\} であることも分かる。
https://scrapbox.io/files/66f8d10a4f12e9001c716a04.png
lazy の型と$ \text{mapping}(x, f), \text{composition}(f, g) の指定
区間 flip 更新にも対応できるように lazy の型と 2 つの操作
$ \text{mapping}(x, f) は lazy 配列に貯められた更新クエリ$ f を data 配列の値$ x に適用させるときに用いる関数
$ \text{composition}(f, g) は今見ているノードの lazy 配列$ f が親ノードの lazy 配列$ g と併合するときに用いる関数
をそれぞれ定義する。
今回の lazy の型は「flip したかどうか」の bool 値を管理すれば良い。つまり「$ f=\text{true} なら flip をしている」「$ f=\text{false} ならば flip していない」とする。
$ \text{mapping}(x, f) を考える。今回の場合、$ A(a, b) の$ 0 と$ 1 を全て flip したとき、$ Z(a, b), O(a, b), T(a, b) がどのように変化するかを考えなければならない。
$ 0 の個数と$ 1 の個数は入れ替わるので$ Z(a, b), O(a, b) を swap する
なのは分かるが$ T(a, b) の値が少しむずかしい...。
ここで、flip 前は転倒数に寄与していた$ 0, 1 のペアは flip 後は寄与しなくなり、 flip 前は転倒数に寄与していない$ 0, 1 のペアは flip 後に寄与することに気づく必要がある。
すなわち、$ A(a, b) の$ 0 と$ 1 を全て flip すると、転倒数に寄与する$ 0, 1 のペアも flip する。
https://scrapbox.io/files/66f8d4ea0841f4001cf1026c.png
よって、$ 0, 1 のペアの個数$ Z(a, b)\times O(a, b) は flip 前後で変化しないので、$ T(a, b) は以下のように更新することができる
$ T(a, b)\leftarrow Z(a, b)\times O(a, b)-T(a, b)
次に$ \text{composition}(f, g) を考える。
これはそこまで難しくない、$ 2 回 flip すると元に戻ることから$ f の後に$ g を行う操作は$ f\oplus g の操作と同じことになる。
これにより操作$ f の$ \text{id} (恒等写像)は $ \text{false} であることも分かる。
以上で作成した遅延セグ木に載せるモノイドの実装例を示す。
code:cpp
// 転倒数: 0 の個数, 1 の個数, 転倒数を管理
using S = tuple<ll, ll, ll>;
constexpr S e = {0, 0, 0};
auto op = &(S a, S b) -> S { return S{a0 + b0, a1 + b1, ainv + binv + a1 * b0};
};
// 区間 flip 更新
using F = bool;
constexpr F id = false;
auto mapping = &(S x, F f) -> S { // f = false なら flip していないので変化なし
if (f == id) return x;
// f = true の場合 flip する
return S{x1, x0, x0 * x1 - xinv};
};
// 2 回 flip するともとに戻ることから f の後に g を合成すると f, g の XOR と等しくなる
auto composition = &(F f, F g) -> F { return f ^ g; }; 最後に遅延 Segment Tree の初期値を考える。
$ A_i=0 のとき：$ \{1, 0, 0\}
$ A_i=1 のとき：$ \{0, 1, 0\}
となる。これで後はクエリを捌けば、この問題を計算量$ O(N+Q\log N) 時間で解くことができた。
実装
code:cpp
using namespace std;
using ll = long long;
#define debug(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__) #define debug(...) (static_cast<void>(0)) template <class T, class E, class F, class G, class H>
struct LazySegmentTree {
int n, len, height;
vector<T> data;
vector<E> lazy;
const F op;
const G mapp;
const H comp;
const T e;
const E id;
LazySegmentTree() = default;
LazySegmentTree(int size, const F& operation, const G& mapping, const H& composition, const T& identity,
const E& lazy_identity)
: n(size), op(operation), mapp(mapping), comp(composition), e(identity), id(lazy_identity) {
init();
}
LazySegmentTree(const vector<T>& v, const F& operation, const G& mapping, const H& composition, const T& identity,
const E& lazy_identity)
: n(int(v.size())), op(operation), mapp(mapping), comp(composition), e(identity), id(lazy_identity) {
init(), build(v);
}
void init() {
len = 1, height = 0;
while (len < n) len <<= 1, height++;
data.assign(len << 1, e);
lazy.assign(len << 1, id);
}
void build(const vector<T>& v) {
for (int i = 0; i < n; i++) datai + len = vi; }
T reflect(int k) { return lazyk == id ? datak : mapp(datak, lazyk); } void eval(int k) {
// 子の要素があれば, 子に遅延配列の伝搬を行う
// 自身を更新
}
void recalc(int k) {
while (k >>= 1) datak = op(reflect(k << 1 | 0), reflect(k << 1 | 1)); }
void thrust(int k) {
for (int i = height; i > 0; i--) eval(k >> i);
}
// [l, r) に val を作用させて更新
void update(int l, int r, E val) {
if (l >= r) return;
// 上側のノードをまず伝搬
l += len, r += len;
thrust(l), thrust(r);
int l0 = l, r0 = r;
while (l < r) {
if (l & 1) lazyl = comp(lazyl, val), l++; if (r & 1) --r, lazyr = comp(lazyr, val); l >>= 1, r >>= 1;
}
l = l0, r = r0;
// 上側のノードを更新
recalc(l), recalc(r - 1);
}
// i 番目の値を val に更新
void set(int i, T val) {
i += len;
thrust(i);
recalc(i);
};
// [l, r) の区間取得
T prod(int l, int r) {
assert(0 <= l && l <= r && r <= n);
if (l >= r) return e;
l += len, r += len;
// 上側のノードをまず伝搬
thrust(l), thrust(r - 1);
T resl = e, resr = e;
while (l < r) {
if (l & 1) resl = op(resl, reflect(l++));
if (r & 1) resr = op(reflect(--r), resr);
l >>= 1, r >>= 1;
}
return op(resl, resr);
}
// i の値を取得
T get(int i) {
i += len;
for (int j = height; j > 0; j--) eval(i >> j);
return reflect(i);
}
T operator[](int i) { return get(i); }
};
int main() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
cout << fixed << setprecision(20);
int N, Q;
cin >> N >> Q;
vector<int> A(N);
for (int i = 0; i < N; i++) cin >> Ai; // 転倒数: 0 の個数, 1 の個数, 転倒数を管理
using S = tuple<ll, ll, ll>;
constexpr S e = {0, 0, 0};
auto op = &(S a, S b) -> S { return S{a0 + b0, a1 + b1, ainv + binv + a1 * b0};
};
// 区間 flip 更新
using F = bool;
constexpr F id = false;
auto mapping = &(S x, F f) -> S { if (f == id) return x;
return S{x1, x0, x0 * x1 - xinv};
};
auto composition = &(F f, F g) -> F { return f ^ g; }; vector<S> V(N);
for (int i = 0; i < N; i++) {
} else {
}
}
LazySegmentTree seg(V, op, mapping, composition, e, id);
while (Q--) {
int T, L, R;
cin >> T >> L >> R, L--;
if (T == 1) {
seg.update(L, R, true);
}
if (T == 2) {
cout << c << '\n';
}
}
}