思路与算法

为位置建线段树有向上边，父节点表示该段最大下界。每条要求建虚点，从未选中位置的若干间隔覆盖节点向虚点连0边，再从虚点向所有选中叶子连1边。未知叶初始1，已知叶初始指定值，Kahn拓扑依边权取最大下界；已知点被提高、超过1e9或出现环即无解。

正确性说明

每条要求恰表示每个选中值至少比全部未选中最大值高1，压缩树节点逐层取最大与逐点连边等价。无环图中拓扑最大传播得到所有约束的逐点最小可行下界，因此超过已知值或上界便没有其他解可挽救。任一有向环必须经过至少一条虚点到叶的1边，意味着值严格增加回自身，必矛盾；所以Kahn拒环充分。

复杂度

节点O(n+m)，边O(n+Σk+(m+Σk)logn)。建树初始化及拓扑O(n+m+边数)，空间同阶；输出O(n)。

易错点

未选中部分按相邻选中位置间的空隙连边，不能把整个[l,r]接入而包括选中自身。已知值既是下界也是不可变的上界。多解特判逐项检查原值、1至1e9及全部严格关系。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, s, m;
    cin >> n >> s >> m;
    int V = 4 * n + m + 5;
    vector<vector<pair<int, int>>> g(V);
    vector<int> indeg(V), leaf(n + 1), fix(V), a(V), ord;
    auto edge = [&](int u, int v, int w) {
        g[u].push_back({v, w});
        indeg[v]++;
    };
    int used = 0;
    function<int(int, int)> build = [&](int l, int r) {
        int u = ++used;
        if (l == r) {
            leaf[l] = u;
            a[u] = 1;
            return u;
        }
        int mid = (l + r) / 2;
        int x = build(l, mid), y = build(mid + 1, r);
        edge(x, u, 0);
        edge(y, u, 0);
        return u;
    };
    int rt = build(1, n);
    vector<int> lc(V), rc(V), L(V), R(V);
    function<void(int, int, int)> index = [&](int u, int l, int r) {
        L[u] = l;
        R[u] = r;
        if (l == r)
            return;
        int x = u + 1, mid = (l + r) / 2;
        lc[u] = x;
        rc[u] = x + 2 * (mid - l + 1) - 1;
        index(lc[u], l, mid);
        index(rc[u], mid + 1, r);
    };
    index(rt, 1, n);
    for (int i = 0, p, d; i < s; i++) {
        cin >> p >> d;
        fix[leaf[p]] = d;
        a[leaf[p]] = d;
    }
    function<void(int, int, int, int)> cover = [&](int u, int l, int r, int op) {
        if (l > r || r < L[u] || R[u] < l)
            return;
        if (l <= L[u] && R[u] <= r) {
            edge(u, op, 0);
            return;
        }
        cover(lc[u], l, r, op);
        cover(rc[u], l, r, op);
    };
    for (int i = 0; i < m; i++) {
        int l, r, k;
        cin >> l >> r >> k;
        vector<int> x(k);
        for (int &v : x)
            cin >> v;
        int op = ++used, at = l;
        for (int v : x) {
            cover(rt, at, v - 1, op);
            edge(op, leaf[v], 1);
            at = v + 1;
        }
        cover(rt, at, r, op);
    }
    queue<int> q;
    for (int i = 1; i <= used; i++)
        if (!indeg[i])
            q.push(i);
    bool ok = true;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        ord.push_back(u);
        if (fix[u] && a[u] > fix[u])
            ok = false;
        if (a[u] > 1000000000)
            ok = false;
        for (auto e : g[u]) {
            a[e.first] = max(a[e.first], a[u] + e.second);
            if (!--indeg[e.first])
                q.push(e.first);
        }
    }
    if ((int)ord.size() != used)
        ok = false;
    if (!ok) {
        cout << "NIE\n";
        return 0;
    }
    cout << "TAK\n";
    for (int i = 1; i <= n; i++)
        cout << a[leaf[i]] << (i == n ? '\n' : ' ');
}