Binary search, standard 2-SAT, segment tree

There are many blogs about 2-SAT (and Tarjan). Read the next paragraph if you are like me and don't get how to build the graph. You can search up the internet for it.

A good blog in Chinese: link. I read like 4-5 blogs and websites to learn about it but still don't get how the graph is built. The blog provides an excellent description, "A directed edge from A to B means that if we choose A then we must choose B, but when we choose B, we don't necessary choose A."

Lets get back to the problem. A wise man once said: "When you see a problem that maximize minimum ... or minimize maximum ... , it's highly likely that it is binary search."

By observation this problem has a : $$$true, ..., true, false, ..., false$$$ scenario if we choose a function to check if $$$min \geq k$$$. I think this is quite easy to find out this pattern. If you can't see this pattern, try learning binary search from Um_nik first XD.

Now we need to write a check function to check if the graph satisfies a value $$$k$$$ to have $$$min$$$ $$$\geq$$$ $$$k?$$$

From here onwards we will let $$$A$$$ $$$=$$$ we choose node $$$A$$$, $$$A'$$$ $$$=$$$ we don't choose A.

Then, we can observe that we have 2 cases:

We notice that the bottleneck of this solution would be on the $$$2nd$$$ case. What should we do to optimize it? What if we took ranges to represent them into nodes? Then, what is the trick to make as few ranges we can? Then we can notice that we can use ranges in segment tree to represent a node!

Ok, let us define $$$tr_{L,R}$$$ to be the node that represents range $$$[L,R]$$$.

Let us redo $$$2nd$$$ case. We need to build an edge from $$$i$$$ -> $$$tr_{i-k+1,i-1}'$$$ and $$$i$$$ -> $$$tr_{i+1,i+k-1}'$$$. We also need to add edges from $$$tr_{L,R}$$$, $$$tr_{L,R}'$$$ -> $$$tr_{L, mid}'$$$ and $$$tr_{L,R}'$$$ -> $$$tr_{mid+1, R}'$$$. This is because if we don't want to take $$$[L,R]$$$, we also must not take $$$[L, mid]$$$ and $$$[mid+1, R]$$$. If $$$tr'_{i, i}$$$ is satisfied, we must not take $$$i'$$$, meaning we also need to add edge from every $$$tr'_{i, i}$$$ to $$$i'$$$.

After we did this, just run tarjan and compute all SCCs. If an $$$i$$$ and $$$i'$$$ belongs to the same SCC, answer will be NO because it's impossible to take $$$i$$$ and not take $$$i$$$ at the same time.

Otherwise, the answer is YES.

//闲敲棋子落灯花//
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
 
const int NN = 6e5 + 500;
stack<int> s;
int dfn[NN], low[NN], timer, cnt, col[NN];
bool vis[NN];
vector<int> G[NN];
vector<int> Neo[NN];
void tarjan(int u) {
    vis[u] = true;
    low[u] = dfn[u] = ++timer;
    s.push(u);
    for (auto v : Neo[u]) {
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if (vis[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (low[u] == dfn[u]) {
        cnt++;
        while (1) {
            int x = s.top(); s.pop();
            vis[x] = false;
            col[x] = cnt;
            if (x == u) break;
        }
    }
}
 
int N, M;
void add_edge(int x, int y) {
    Neo[x].push_back(y);
    return;
}
void build(int p, int l, int r) {
    if (l == r) {
        add_edge(p + 2 * N, l + N);
        return;
    }
    int mid = (l + r) >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
    add_edge(p + 2 * N, (p << 1) + 2 * N);
    add_edge(p + 2 * N, (p << 1 | 1) + 2 * N);
    return;
}
void add(int p, int l, int r, int ql, int qr, int x) {
    if (ql <= l && r <= qr) {
        add_edge(x, p + 2 * N);
        return;
    }
    int mid = (l + r) >> 1;
    if (ql <= mid) add(p << 1, l, mid, ql, qr, x);
    if (qr >= mid + 1) add(p << 1 | 1, mid + 1, r, ql, qr, x);
    return;
}
bool check(int k) {
    if (k == 1) return true;
    for (int i = 0; i <= 2 * N; i++)
        Neo[i].clear();
    for (int i = 1; i <= N; i++)
        for (auto& v : G[i])
            add_edge(i + N, v);
 
    for (int i = 1; i <= N; i++) {
        int L = max(1, i - k + 1), R = i - 1;
        if (L <= R) add(1, 1, N, L, R, i);
        L = i + 1; R = min(N, i + k - 1);
        if (L <= R) add(1, 1, N, L, R, i);
    }
    while (s.size()) s.pop();
    timer = 0, cnt = 0;
    for (int i = 1; i <= 6 * N; i++)
        low[i] = dfn[i] = vis[i] = 0;
 
    for (int i = 1; i <= 6 * N; i++)
        if (!dfn[i])
            tarjan(i);
 
    for (int i = 1; i <= N; i++)
        if (col[i] == col[i + N])
            return false;
    return true;
}
void solve() {
    cin >> N >> M;
    for (int i = 0; i <= 6 * N; i++) {
        G[i].clear();
        Neo[i].clear();
    }
    for (int i = 0; i < M; i++) {
        int u, v; cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    build(1, 1, N);
    int l = 1, r = N;
    while (l < r) {
        int mid = (l + r + 1) >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    cout << l << '\n';
    return;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
 
    int T; cin >> T;
    while (T--) {
        solve();
    }
}

This is the first time I saw a 2-SAT problem. Bruh I literally spent 1.5 hours to just to read on 2-SAT. But the problem is amazing and interesting. Mixture of ideas (2-SAT, binary search and segment tree) was insane. Also, I submitted like 7 times like a dumbass before ACing.

We can represent $$$i'$$$ as node with index $$$i + N$$$, also $$$tr_{L,R}$$$ with index $$$p$$$ in the segment tree with node with index $$$p+2*N$$$ for simpler implementation. Remember to clear all edges and the edges created from the previous check function (got like 4 WAs for this). At the same time, we also need to make sure that the indexes will not be $$$\leq 0$$$ or $$$\geq N+1$$$ when connecting $$$i$$$ to $$$[i-k+1,i-1]$$$ and $$$[i+1,i+k-1]$$$.