序文

問題のリンク：洛谷。

問題概要

長さが \(n\) の配列があり、一部の要素はすでに色が塗られています。\(m\) 個の制約が与えられ、それぞれ \(l_i \sim r_i\) の範囲内にちょうど1つの要素が色付きであることを示します。この制約をすべて満たすように、最大で何個の要素を色付けできるかを求めます。

\(n \leq 2 \times 10^5\)，\(m \leq 10^5\)。

問題解析

解法 \(1\)：差分制約

区間に関する問題では、累積和を用いて問題を変形します。各制約 \(l_i \sim r_i\) において、\(v_{r_i} - v_{l_i - 1} = 1\) という関係式を得られます。ここで \(v_i\) は \(1 \sim i\) の間に色が塗られた要素の数を意味します。また、制約として \(v_{i} - v_{i - 1} \in [0, 1]\) が成り立ちます。グラフ構築後、差分制約を用いて最短経路を計算します。

最大値 \(\max v_n\) を求めたいので、最短経路アルゴリズムを用います。

無解は負の閉路が存在することと同義であり、最短経路が存在しない場合です。

しかし、これは計算量的に遅く、最適化が必要です。SPFAアルゴリズムの標準的な高速化として、SLF（Small Label First）を適用します。さらに、ループ回数が一定値を超えると無解と判定する方法もあります。これにより、時間内に解けるようになります。

解法 \(2\)：動的計画法

差分制約は本質的な解法ではありません。配列の問題なので、現在位置が色付きかどうかを決定し、DPで解くことができます。

\(f_i\) を位置 \(i\) が色付きであるとき、\(1 \sim i\) の中で色が塗られた要素数の最大値とします。遷移では、前回の色付き位置 \(j\) を探索し、以下の式で更新します：

[f_i = \max _ {\text{meet given conditions}} { f_j } + 1 ]計算量については一旦置いておき、\(j\) が条件を満たすかの判定方法を考えます。

重要なポイント：「ちょうど」は「少なくとも1つ」と「高々1つ」の組み合わせと同義です。

この問題では、「ある区間内にちょうど1つ色が塗られている」を「少なくとも1つ」かつ「高々1つ」に分解します。

前者について考えると、\((i, j)\) の間に色が塗られていない場合、その区間が制約に含まれる場合は不正解となります。したがって、右端点が \(x\) より左側の区間で左端点が最大になるものを \(mi_x\) とします。\(j\) は \(j \geq mi_i\) を満たす必要があります。

次に後者について。もし区間が \(i\) と \(j\) の両方を含む場合、それは制約に違反します。右端点が \(x\) 以上で左端点が最小となるものを \(mx_x\) とします。\(j\) は \(j \lt mx_i\) を満たす必要があります。

これらの前処理は簡単に行えます。

遷移式は以下のように変更されます：

[\large f_i = \max _ {j = mi_i} ^ {mx_i - 1} { f_j } + 1 ]\(mx\) および \(mi\) は単調非減少であるため、単調キューを使用できます。ただし、無効な \(f_i = -1\) が存在する場合、\(f_j \neq -1\) となる \(j\) から選ぶ必要があり、条件を満たす \(j\) がない場合は \(f_i = -1\) とします。

最終的な答えは \(f\) の最大値ではなく、\(f_{n + 1}\) を用いて求めることで、すべての制約を考慮に入れます。

計算量：\(\Theta(n + m)\)。

2024年11月2日の更新：\(f\) の性質を発見し、単調キューを省略しました。

テーブルを確認すると \(f\) が単調増加であることがわかります。従って、単調キューは二つのポインタで置き換え可能です。\(\lt mx_i\) である \(j\) のうち、最後に \(f_j \neq -1\) となる \(k\) を管理し、\(k \geq mi_i\) であれば遷移を行います。計算量は変わりません。

詳細な証明：第二数学的帰納法を用います。すべての \(j \lt i\) に対して \(f_j\) が単調であると仮定し、\(f_i \geq f_{i - 1}\) が成り立つことを示します。

\(mx_i \geq mx_{i - 1}\) であることから、\(mx_{i - 1} + 1 \sim mx_i\) に \(f_{mx_{i - 1}}\) 以上の \(f\) が存在する可能性があります。\(j \lt i\) に対して \(f_j\) が単調であるため、\(f_i\) はこの範囲から遷移可能であり、\(f_i \geq f_{i - 1}\) が成り立ちます。 コード

解法 \(1\)：差分制約

#include <cstdio>
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

const int N = 200010, M = 100010;

struct Graph {
    struct node {
        int to, len, nxt;
    } edge[N * 2 + M * 2];
    int tot = 1, head[N];
    void add(int u, int v, int w) {
        edge[++tot] = {v, w, head[u]};
        head[u] = tot;
    }
    inline node & operator [] (const int x) {
        return edge[x];
    }
} xym;

void smller(int u, int v, int w) {
    xym.add(v, u, w);
}

void bigger(int u, int v, int w) {
    smller(v, u, -w);
}

void equals(int u, int v, int w) {
    bigger(u, v, w);
    smller(u, v, w);
}

int n, m;

int dis[N], cnt[N];
bool inq[N];

bool SPFA() {
    int yzh_i_love_you = 0;
    memset(dis, 0x3f, sizeof dis);
    deque<int> Q; Q.push_front(0), dis[0] = 0, cnt[0] = 1;
    inq[0] = true;
    while (!Q.empty()) {
        int now = Q.front(); Q.pop_front();
        inq[now] = false;
        for (int i = xym.head[now]; i; i = xym[i].nxt) {
            int to = xym[i].to, w = xym[i].len;
            if (dis[to] > dis[now] + w) {
                dis[to] = dis[now] + w;
                cnt[to] = cnt[now] + 1;
                if (cnt[to] > n + 1 || ++yzh_i_love_you > 1736520) return false;
                if (!inq[to]) {
                    inq[to] = true;
                    if (!Q.empty() && dis[to] < dis[Q.front()]) Q.push_front(to);
                    else Q.push_back(to);
                }
            }
        }
    }
    return true;
}

signed main() {
    #ifndef XuYueming
    freopen("photo.in", "r", stdin);
    freopen("photo.out", "w", stdout);
    #endif
    scanf("%d%d", &n, &m);
    for (int i = 1, l, r; i <= m; ++i) {
        scanf("%d%d", &l, &r);
        equals(r, l - 1, 1);
    }
    for (int i = 1; i <= n; ++i) {
        bigger(i, i - 1, 0);
        smller(i, i - 1, 1);
    }
    if (!SPFA()) return puts("-1"), 0;
    printf("%d", dis[n]);
    return 0;
}

解法 \(2\)：動的計画法

単調キュー

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

const int N = 200010;

int n, m, mx[N], mi[N];
int Q[N], head, tail = -1;
int f[N];

signed main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n + 1; ++i) mx[i] = i;
    for (int i = 1, l, r; i <= m; i++) {
        scanf("%d%d", &l, &r);
        mx[r] = min(mx[r], l);
        mi[r + 1] = max(mi[r + 1], l);
    }
    for (int i = n; i >= 1; --i) mx[i] = min(mx[i], mx[i + 1]);
    for (int i = 2; i <= n + 1; ++i) mi[i] = max(mi[i], mi[i - 1]);
    for (int i = 1, j = 0; i <= n + 1; ++i) {
        while (j < mx[i]) {
            if (f[j] != -1) {
                while (head <= tail && f[Q[tail]] <= f[j]) --tail;
                Q[++tail] = j;
            }
            ++j;
        }
        while (head <= tail && Q[head] < mi[i]) ++head;
        if (head <= tail) f[i] = f[Q[head]] + 1;
        else f[i] = -1;
    }
    if (f[n + 1] == -1) puts("-1");
    else printf("%d\n", f[n + 1] - 1);
    return 0;
}

二重ポインタ

#include <cstdio>

const int MAX = 1 << 23, N = 200001;
int n, m, l, r, mx[N], mi[N], f[N];
char buf[MAX], *p(buf), *e(buf + MAX);

#define getchar() (p == e && fread(p = buf, 1, MAX, stdin), *p++)

[[always_inline]] inline void read(int &x) {
    x = 0; char ch = getchar();
    for (; ch <  48; ch = getchar());
    for (; 48 <= ch; ch = getchar())
        x = (x << 3) + (x << 1) + (ch ^ 48);
}
[[always_inline]] inline void tomin(int& a, int& b) { b < a && (a = b); }
[[always_inline]] inline void tomax(int& a, int& b) { b > a && (a = b); }

main() {
    fread(buf, 1, MAX, stdin), read(n), read(m);
    for (register int i(1); i <= n + 1; ++i) mx[i] = i;
    for (; m--; ) read(l), read(r), tomin(mx[r], l), tomax(mi[r + 1], l);
    for (register int i(n); i; --i) tomin(mx[i], mx[i + 1]);
    for (register int i(1), j(0), k(0); i <= n + 1; ++i, tomax(mi[i], mi[i - 1])) {
        for (; j + 1 < mx[i]; ~f[++j] && (k = j));
        f[i] = k >= mi[i] ? f[k] + 1 : -1;
    }
    ~f[n + 1] ? printf("%d", f[n + 1] - 1) : puts("-1");
}