yukicoder No.9177. Interval Union Find
はじめに
初Testerをさせていただきました。不慣れな部分が多かったかと思います。
まず、Writerのt98sliderさんに感謝です。とても面白い問題でした。
そして解いて下さった方にも感謝です。文分かりづらかったらごめんなさい。
なんとなくはてなブログからnoteに移行しました。
手を動かしてクエリ処理を考えてくると見えてくるかと考えております。
問題
解説
Writer解ではsetを用いた解答となっております。
ここではクエリ先読み+座標圧縮+区間変更区間最小値(RUQ+RMQ)を操作する遅延評価付きセグメントツリーによる解法を紹介致します。
(追記):いつのまにやらWriter解説にも上の方針の解説が追加されていました。
あちらに対して新規性はないものの一応公開しておきます。Writer様の解説の方をお先にお読み下さい。
クエリ1, 2
クエリ$${1}$$, $${2}$$ についてはどちらも素直にクエリに従って間の辺を作成、削除すると、クエリ$${1}$$回辺りの操作で計算量$${\Theta (R-L)^{2}}$$となりとても間に合いません。
しかし、これらのクエリ操作をよく観察すると、どちらも閉区間$${[L, R]}$$ の間全てを連結する、あるいは全ての連結を解除する操作となっております。
従って、この操作は自身より頂点番号が$${1}$$ つ右のものと連結であるかという情報を配列に持たせるとよさそうです。
具体的には以下のような配列となります。
hen[i]:=頂点番号iが頂点番号i+1番目と連結かどうか(1/0)
これを用いて、無向グラフの頂点を一直線上に並べ、辺で結ぶ、あるいは削除する操作を半開区間$${[L, R)}$$に含まれる添字を持つ配列の値を全て$${1/0}$$で変更するとすれば$${\Theta (R-L)}$$まで計算量を落とせます。
さらに、区間変更の機能を持たせたセグメントツリーを使うことで、この操作は$${\Theta (log N)}$$まで落とすことができます。
セグメントツリーについては、
等を参照ください。
クエリ3
クエリ$${3}$$ の場合は上の配列を用いて半開区間$${[u, v)}$$に含まれる添字を持つ配列の値の最小値を調べることで連結か否かを判定できます。
最小値が$${1}$$であるならば連結であり、$${0}$$であるならば連結ではありません。
なぜなら、連結である場合、閉区間$${[u, v]}$$の間はすべて辺が結ばれている必要があり、またそれが連結性の確認として十分だからです。
証明に関してはおそらく半開区間$${[u, v)}$$内に$${hen[w]=0}$$が存在すると仮定し、背理法から詰めると良いかもです。寝る前にでも考えてみてください。
話を戻します。
以上の操作は愚直にループを書くと$${\Theta (v-u)}$$かかりますが、区間最小値を扱うセグメントツリーを使い、$${\Theta (log N)}$$で判定が行えます。
頂点番号が同じ場合、常に連結であることに注意してください。
クエリ4
クエリ$${4}$$ は頂点$${v}$$ を起点として左右に探索を行い、それぞれについて配列の値が$${1}$$ から$${0}$$ に切り替わるギリギリの添字を見つけることで解答できます。
実際に、
$$
hen[r]=1\\
hen[r+1]=0\\
hen[l]=1\\
hen[l-1]=0
$$
であれば、答えは、
$$
r-l+1
$$
となります。
これはピュアなループであると$${O(N)}$$かかりますが、二分探索を用いることで$${O(log N)}$$となります。
セグメントツリー上でも二分探索が行えるため、そちらの方が手間が減るでしょう。最後に掲載する解答例ではACLにあるlazy_segtreeを用いて解答しています。
あまりACLを使った事がない人の参考にしていただければ幸いです。
クエリ先読み+座標圧縮
さて、以上の操作をそのまま実装するとどうなるでしょうか？残念ながらTLEとなってしまいます。
これはセグメントツリー(というより配列)のコンストラクタに$${\Theta (N)}$$を要するためです。
これを解消する術を考えます。この問題をよく見ると以上の解き方ではまだムダがあることが分かります。
例えばクエリが、
$$
1\ 1\ 10^{8}\\
2\ 3\ 6\\
$$
と与えられている時、$${6}$$ から先はかなりムダに感じられるでしょう。この感性が大事です。
この問題は端点の情報があれば、間についてはごく簡単な計算で状態が分かります。
$$
1\ 1\ 10^{8}\\
2\ 3\ 6\\
$$
ならば明らかに、
$$
hen[15]=1\\
$$
でしょう。この分のスペースをわざわざ確保しておく必要があるかというと極めて怪しいです。
そこで、与えられるクエリを全て先に読み込み、座標圧縮という手を施します。
座標圧縮については以下を参照してください。
簡単にいえば数字の値でなく、大小関係で数値を振り直すと捉えるというものです。
そうすると、今回与えられるクエリの量は$${Q}$$ 個であるため、座標圧縮の前計算$${\Theta (Q log Q)}$$により、コンストラクタは$${\Theta (Q)}$$となります。
以上を用いてからセグメントツリーを作成した後は、必要に応じて座標圧縮された後の値を二分探索で参照することで実行時間にも間に合いながらACを取る事ができます。
おわりに
noteは直感的に書きやすくてよいですね。
知識の復習がてら計算量の記法をなるべく精確に使おうとしました。書きながらうーんとなっており、正直全部ビッグオーにすれば良かったと軽く後悔です。
読みづらい箇所あればご指摘ください。ばいばい。
プログラム
#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using Graph = vector<vector<ll>>;
using vi = vector<int>;
using vl = vector<long>;
using vll = vector<long long>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using vvll = vector<vll>;
using vs = vector<string>;
using vc = vector<char>;
using vvc = vector<vc>;
using pll = pair<long long, long long>;
using vpll = vector<pll>;
using mint = modint1000000007;
const long double EPS = 1e-18;
const long double PI = acos(-1.0L);
#define reps(i, a, n) for (ll i = (a); i < (ll)(n); i++)
#define rep(i, n) for (ll i = (0); i < (ll)(n); i++)
#define rrep(i, n) for (ll i = (1); i < (ll)(n + 1); i++)
#define repd(i, n) for (ll i = n - 1; i >= 0; i--)
#define rrepd(i, n) for (ll i = n; i >= 1; i--)
#define ALL(n) begin(n), end(n)
#define IN(a, x, b) (a <= x && x < b)
#define INIT \
std::ios::sync_with_stdio(false); \
std::cin.tie(0);
template <class T>
inline T CHMAX(T& a, const T b) {
return a = (a < b) ? b : a;
}
template <class T>
inline T CHMIN(T& a, const T b) {
return a = (a > b) ? b : a;
}
using S = long long;
using F = long long;
const S INF = 8e18;
const F ID = 8e18;
S op(S a, S b) { return std::min(a, b); }
S e() { return INF; }
S mapping(F f, S x) { return (f == ID ? x : f); }
F composition(F f, F g) { return (f == ID ? g : f); }
F id() { return ID; }
ll target = 0;
bool g(S x) { return x > target; }
int main() {
ll N;
cin >> N;
ll Q;
cin >> Q;
vll za;
za.push_back(0);
za.push_back(1e9 + 100);
vvll query(2e5 + 50);
// クエリ先読みパート.
rrep(i, Q) {
ll type;
cin >> type;
query[i].push_back(type);
if (type != 4) {
ll u, v;
cin >> u >> v;
query[i].push_back(u);
query[i].push_back(v);
za.push_back(u);
za.push_back(v);
} else {
ll u;
cin >> u;
query[i].push_back(u);
za.push_back(u);
}
}
// 座標圧縮パート.
sort(ALL(za));
za.erase(unique(ALL(za)), za.end());
ll n = za.size();
vector<S> v(n, 0);
// 遅延評価付きセグメントツリーパート.
lazy_segtree<S, op, e, F, mapping, composition, id> seg(v);
rrep(i, Q) {
if (query[i][0] == 1) {
ll l = lower_bound(ALL(za), query[i][1]) - za.begin();
ll r = lower_bound(ALL(za), query[i][2]) - za.begin();
// 半開区間[l, r)に1を入れる変更.
seg.apply(l, r, 1);
} else if (query[i][0] == 2) {
ll l = lower_bound(ALL(za), query[i][1]) - za.begin();
ll r = lower_bound(ALL(za), query[i][2]) - za.begin();
// 半開区間[l, r)に0を入れる変更.
seg.apply(l, r, 0);
} else if (query[i][0] == 3) {
ll l = lower_bound(ALL(za), query[i][1]) - za.begin();
ll r = lower_bound(ALL(za), query[i][2]) - za.begin();
if (r < l) {
swap(l, r);
}
if (l != r) {
// 半開区間[l, r)までの間の値の最小値を確認.
cout << seg.prod(l, r) << endl;
} else {
// 1頂点である場合、常に連結.
cout << 1 << endl;
}
} else {
ll hei = lower_bound(ALL(za), query[i][1]) - za.begin();
// セグメントツリー上の二分探索.
ll r = seg.max_right<g>(hei);
ll l = seg.min_left<g>(hei);
cout << za[r] - za[l] + 1 << endl;
}
}
}