yukicoder No.9138 無向辺 2-SAT
Writerのt98sliderさん、そして解いて下さった皆様にも感謝です。
問題
$${2-SAT}$$ とみて条件付けを行う問題です。
解説
Union-Findを用いて矛盾がないか、情報に対する制約が増えていないかを判定すればよいです。
この問題の場合は、
$$
x=x\\
\neg x=x+N
$$
と見立てて考えると扱いやすいでしょう。
この問題では、クエリ$${3}$$ がおそらくネックとなります。これについて$${2}$$ 通りの解決法を示します。
解法1
RollbackつきUnion Findを用います。ライブラリは以下にあります。「Union Find 復元」とかで調べたら出てきてしまったので載せておきます。
これはそのまますぎるのでプログラムについては省略致します。検索する力は大事なのかもしれません。
解法2
難しいポイントとして、クエリ$${3}$$ でリセットがかかる度にご丁寧にサイズ$${2×N}$$でUnion-Findを作成すると、$${Q}$$回のコンストラクタにより、最悪$${O(NQ)}$$を要し、TLEとなります。
そこで$${1}$$ つのクエリ$${3}$$ が出現するまでに出現するクエリ$${1}$$, クエリ$${2}$$ で用いられる$${u, v}$$ の値を先に抜き出し、座標圧縮することで、クエリ全てにおけるUnion-Findのコンストラクタの計算量の合計も高々$${O(Q)}$$ で収められます。
クエリ$${3}$$ 全てにおける座標圧縮の計算量の合計は高々$${O(Q logQ)}$$です。
また、クエリ$${1, 2}$$ 全てにおける計算量の合計は高々$${O(Q \alpha(Q))}$$です。
従って、この問題は高々$${O(Q logQ)}$$で解くことができました。
おわりに
お読みいただきありがとうございました。分かりづらい箇所、誤りがあれば教えてください。
さよなら。
解法2のプログラム
#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 = modint998244353;
const long double EPS = 1e-18;
const long long INF = 1e18;
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;
}
int main() {
ll N, Q;
cin >> N >> Q;
mint ans = 0;
mint def = mint(2).pow(N);
ans = def;
vll num(4e5 + 100, 0);
vvll queee(2e5 + 100);
rrep(i, Q) {
ll q;
cin >> q;
queee[i].push_back(q);
if (q != 3) {
ll x, y;
cin >> x >> y;
queee[i].push_back(x);
queee[i].push_back(y);
}
}
ll right = 1;
ll left = 1;
while (left <= Q) {
while (queee[right][0] != 3 && right < Q) {
right++;
}
vll za;
reps(i, left, right + 1) {
if (queee[i][0] != 3) {
za.push_back(queee[i][1]);
za.push_back(queee[i][1] + N);
za.push_back(queee[i][2]);
za.push_back(queee[i][2] + N);
}
}
sort(ALL(za));
za.erase(unique(ALL(za)), za.end());
dsu uf(za.size() + 10);
reps(i, left, right + 1) {
if (queee[i][0] == 1) {
ll u = lower_bound(ALL(za), queee[i][1]) - za.begin();
ll v = lower_bound(ALL(za), queee[i][2]) - za.begin();
ll nu = lower_bound(ALL(za), queee[i][1] + N) - za.begin();
ll nv = lower_bound(ALL(za), queee[i][2] + N) - za.begin();
if (!uf.same(u, v)) {
ans /= 2;
}
uf.merge(u, v);
uf.merge(nu, nv);
if (uf.same(u, nu) && uf.same(v, nv)) {
ans = 0;
}
} else if (queee[i][0] == 2) {
ll u = lower_bound(ALL(za), queee[i][1]) - za.begin();
ll v = lower_bound(ALL(za), queee[i][2]) - za.begin();
ll nu = lower_bound(ALL(za), queee[i][1] + N) - za.begin();
ll nv = lower_bound(ALL(za), queee[i][2] + N) - za.begin();
if (!uf.same(u, nv)) {
ans /= 2;
}
uf.merge(u, nv);
uf.merge(nu, v);
if (uf.same(u, nu) && uf.same(v, nv)) {
ans = 0;
}
} else {
ans = def;
}
cout << ans.val() << endl;
}
right++;
left = right;
}
}