テーマ別競プロ勉強会2

set

setは集合を扱うデータ構造で、内部的に平衡二分探索木によって実装されています。実はけっこう凄いデータ構造なのですが、使う側としては内部構造を理解していなくても問題ありません(理解すべきといえばそうですが...)。setは基本便利なのですが、入っている要素が前から何番目かというクエリに答える事はできません。もしオフラインクエリ(つまり前もって情報を知る事ができるなら)座標圧縮とセグメントツリーで実装する事ができます。もしオンラインクエリならば自分で平衡二分探索木を作らないといけないかもです。g++の独自拡張にこれがあって、set+何番目かを高速に求める事ができるそうです(使った事ないですが)。但し、平衡二分探索木の分割とマージや永続クエリを使いたいなら平衡二分探索木を自分で実装する必要がありそうです。

余談はさておき、問題です。

これはオフラインクエリなのでクエリ先読みして座標圧縮をしてセグメントツリーで解くことが可能です。但し今回範囲更新クエリが必要なので遅延評価セグメントツリーが必要になります。そこそこ実装が重いです。

さて、ここでsetが出てきます。範囲内を全て書き換えるという操作は実は行う必要が無く、範囲内の要素を削除→範囲内の個数が奇数の時だけ追加すればいいのは分かりますか？x xor x = 0なので。

さて、範囲内を愚直に全部消すという操作は非常に効率が悪いように思えますが、元々の要素n個に追加される要素は高々q個なので消す操作は合計でO(n+q)回で済む事が分かります。これは余裕そうですね。

L以上の最初の要素を求めるにはsetのlower_boundを使えばいいです。いつも使っているalgorithmの中のlower_boundではなくsetクラスのメソッドを使うのは注意です。

#include<cstdio>
#include<set>
using namespace std;

int n, q, a, l, r, x;

int main() {
  set<int> st;
  scanf("%d%d", &n, &q);
  for (int i = 0; i < n; i++) {
    scanf("%d", &a);
    if (st.count(a) == 0) st.insert(a);
    else st.erase(a);
  }
  for (int i = 0; i < q; i++) {
    scanf("%d%d%d", &l, &r, &x);
    auto it = st.lower_bound(l);
    int counter = 0, ans = 0;
    while (it != st.end() && *it <= r) {
      ans ^= *it;
      auto now = it;
      it++;
      st.erase(now);
      counter++;
    }
    if (counter % 2 == 1) {
      if (st.count(x) == 0) st.insert(x);
      else st.erase(x);
    }
    printf("%d\n", ans);
  }
}

Segment Tree

アリ本P156 Crane(POJ2991)の解説をします。基本的にアリ本に書いている通りなのですが、少し分かりにくい部分があり、どう抽象化すればいいのか最初分からなかったので書きます。

考え方としてベクトルが要素のSegment Treeを作り、2つのベクトルをマージする時、間の角度だけ回転させたものを足せばいいのは分かりますね。しかし、間の角度をSegment Treeの外部に置くと、間の角度が何かを求める処理が煩雑になり、抽象化の観点から見ても微妙です。

そこで、ベクトルを持つのでは無く、P = pair<ベクトル, 角度>をSegment Treeで持つ事にします。Pに対して、二項演算を定義しましょう。数学的にもコードとしても正しくないですが、お気持ちで解釈して下さい。

P f(P a, P b) {
  return P(a.ベクトル+b.ベクトル * a.角度, a.角度+b.角度)
}

角度 (集合P, 演算f)はモノイドです。fは実は結合則を満たします。そもそもですが、ある場所を回転させるとその場所以降の要素に影響を与えます。つまり、Pの角度の方は以降回転しなければならない角度ととらえると分かりやすいのでは無いでしょうか。

今回ベクトルの回転が出てくるためベクトルを複素数クラスを用いて実装するのが楽かと想います。

こういう無茶をさせたい時、Segment Treeに乗る代数構造がモノイドという事を理解していれば、演算の満たす性質がモノイドかどうかを判定するだけで済むので楽ですね。

#include<cstdio>
#include<vector>
#include<cmath>
#include<functional>
#include<complex>
using namespace std;

typedef long long ll;
typedef complex<double> C;
typedef pair<C, ll> P;
#define cx real()
#define cy imag()

template <typename T>
class SegmentTree {
  ll n;
  vector<T> node;
  function<T(T, T)> fun, fun2;
  bool customChange;
  T outValue, initValue;
public:
  void init(ll num, function<T(T, T)> resultFunction, T init, T out, function<T(T, T)> changeFunction = NULL) {
    // changeFunction: (input, beforevalue) => newvalue
    fun = resultFunction;
    fun2 = changeFunction;
    customChange = changeFunction != NULL;
    n = 1;
    while (n < num) n *= 2;
    node.resize(2 * n - 1);
    fill(node.begin(), node.end(), init);
    outValue = out;
    initValue = init;
  }
  void valueChange(ll num, T value) {
    num += n-1;
    if (customChange) node[num] = fun2(value, node[num]);
    else node[num] = value;
    while (num > 0) num = (num - 1) / 2, node[num] = fun(node[num * 2 + 1], node[num * 2 + 2]);
  }
  T rangeQuery(ll a, ll b, ll l = 0, ll r = -1, ll k = 0) { // [a, b)
    if (r == -1) r = n;
    if (a <= l && r <= b) return node[k];
    if (b <= l || r <= a) return outValue;
    ll mid = (l + r) / 2;
    return fun(rangeQuery(a, b, l, mid, 2*k+1), rangeQuery(a, b, mid, r, 2*k+2));
  }
};


C eval(P p) {
  double arg = 2 * M_PI * p.second / 360;
  return p.first * C(cos(arg), sin(arg));
}

P f(P a, P b) {
  return P(a.first + eval(P(b.first, a.second)), a.second + b.second);
}

ll n, c, l, s, a;
C v[10000];
constexpr P e = P(C(0, 0), 0);

int main() {
  scanf("%lld%lld", &n, &c);
  SegmentTree<P> sgt;
  sgt.init(n, f, e, e);
  for (ll i = 0; i < n; i++) {
    scanf("%lld", &l);
    v[i] = C(0, l);
    sgt.valueChange(i, P(v[i], 0));
  }
  for (ll i = 0; i < c; i++) {
    scanf("%lld%lld", &s, &a);
    P temp = P(v[s], a - 180);
    temp.first = eval(temp);
    sgt.valueChange(s, temp);
    C ans = sgt.rangeQuery(0, n).first;
    printf("%lf %lf\n", ans.cx, ans.cy);
  }
}

POJ、C++のバージョンが古いようで、なんかfunctionalとかM_PIとかが無いって怒られたんだが(なのでAC検証できてない)

アリ本の問題、とても難しくていい問題が多いんですが、POJなのがちょっと...

しかし、考察メインでやるのなら価値はあると思います。

二分探索のコツ

二分探索の問題で頭がごちゃごちゃになった事がある人、そこそこいるのでは無いでしょうか？めぐる式二分探索を使えば半開区間の処理が簡単になりますが、問題によっては判定関数を作る際、OK, NGって何？ってなる事が僕はありました。f(x)が同じ値を何個も取り、その中で最小のものを求める時とか特になります。賢い人はならないのかな？

今回天才じゃなくても頭が混乱しないように、できるだけ体系的に解ける方法を提案します。

この記事は二分探索は理解しているが、頭が混乱する事がある方をターゲットに書かれています。もし二分探索を知らないならば他の記事を読む方が良いと思います。

1. 判定関数の作り方

まずは判定関数を作るのですが、そこが最も重要です。二分探索の問題は本質的に数列/関数に対してある数x以上の最初の要素、x以下の最後の要素って問題に帰着させる事ができます。(未満の場合も整数なら-1、実数なら-EPSして以下の問題に帰着できます)

しかし、これをx以上がどうとか考えると判定関数を作る時頭がこんがらがります。ここで、解のボーダーの値がxとして、どこを求めたいかを考えればスッと理解できます。例として以下の数列があり、解のボーダーの値がaで、本当に求めたい地点はどこですか？

...a-1 a-1 a a a a+1 a+1...

例えばxの中で一番左の地点が欲しいとします。それならば判定関数は

...x x o o o o o...

となるように取るべきです。ならば判定関数f(y)はa<=yならばtrue、それ以外でfalseとすればよいですね。逆に一番右の値が欲しい時は

...o o o o o x x...

となればいいのでf(y)はa>=yです。

まずは上のように重複を意識して考えると良いと思います。

2. 区間と初期値の決め方

...x x o o o o o...

の場合を考えます。例えば、ある地点で判定関数がtrueとなったとします。すると、解はそれ以下となるので、半開区間は(a, b]となるようにとればいい事が分かります。よって初期値は

lb = 有り得る最小の値-1

ub = 有り得る最大の値

とすればよいです。つまり、半開区間の開いている方はありえない値にしておくのがポイントです。両方ありえない値にしてうまく行くときもありますが、問題によってはダメな事があります。例えば配列外参照起こしたり、判定関数が壊れたりします。また、

...o o o o o x x...

の場合は逆を考えればよいです。つまり、半開区間は[a, b)で、初期値はubに+1がされている感じ。もし実数に対する二分探索ならば初期値決めはそんなに厳密にする必要が無い事が多いので楽ですね。

もちろんここはめぐる式で考えてもいいですが、oxのイメージが出来ているならスグ書けると思います。

おわりに

最も重要な事はoxの具体例で考える事だと思いました。もちろん言葉のまま理解できるならそれに越した事は無いですが、言葉で考えて頭が混乱すると時間が無限に溶ける事が何度もあったので。