问题分析

我们需要为 $n$ 个点分配水深值 $1$ 到 $10^9$，满足：

1. $s$ 个固定点的已知水深
2. $m$ 个区间约束：区间内 $k$ 个指定点的水深严格大于其他点

问题可以建模为差分约束系统，但约束是严格大于关系。

核心思想：图论建模 + 拓扑排序

1. 关键转化

将"严格大于"关系转化为：

• 如果 $a > b$，则 $a \geq b + 1$

这样就把严格大于变成了差分约束，可以用有向图表示。

2. 区间优化

约束涉及区间，朴素建图需要 $O(n^2)$ 条边，不可行。 使用倍增/ST表技巧优化建图，将区间拆分成 $O(\log n)$ 个节点。

算法详解

数据结构

const int N = 1e5 + 1e3 + 7;
int tot;                     // 总节点数
vector<int> g[N * 18];       // 邻接表，最多约180万节点
int p[N][18];                // 倍增节点映射
int n, s, m, f[N * 18], o[N * 18];  // f:水深，o:固定水深
int deg[N * 18];             // 入度

算法步骤

步骤1：初始化

cin >> n >> s >> m;
fill(f + 1, f + n + 1, 1);  // 初始水深至少为1

for (int i = 1; i <= s; i++) {
    int x, y;
    cin >> x >> y;
    f[x] = y;      // 当前水深
    o[x] = y;      // 固定水深（用于验证）
}

步骤2：倍增建图（ST表结构）

tot = n;  // 前n个节点是原始点

// 第0层：每个点对应一个倍增节点
for (int i = 1; i <= n; i++) {
    p[i][0] = ++tot;
    // 添加边：i -> p[i][0]，权重1（表示i≥p[i][0]+1）
    g[i].push_back(p[i][0] << 1 | 1);
}

// 构建倍增层
for (int j = 1; j <= 18; j++)
    for (int i = 1; i + (1 << j) - 1 <= n; i++) {
        p[i][j] = ++tot;
        // 添加边：p[i][j-1] -> p[i][j]，权重0
        g[p[i][j - 1]].push_back(tot << 1);
        // 添加边：p[i+(1<<(j-1))][j-1] -> p[i][j]，权重0
        g[p[i + (1 << (j - 1))][j - 1]].push_back(tot << 1);
    }

边的编码：

• v << 1：权重为0的边
• v << 1 | 1：权重为1的边
• 解码时：v >> 1 得到节点编号，v & 1 得到权重

步骤3：区间连接函数

auto add = [&](int x, int l, int r) {
    int k = __lg(r - l + 1);  // 2^k ≤ 区间长度
    // 从区间[l,r]的代表节点到x添加权重0的边
    g[p[l][k]].push_back(x << 1);
    g[p[r - (1 << k) + 1][k]].push_back(x << 1);
};

这个函数实现了区间到点的连接，只需要 $O(\log n)$ 条边。

步骤4：处理卫星测量

while (m--) {
    int l, r, k;
    cin >> l >> r >> k;
    int u = ++tot;  // 创建新节点u
    
    int last = l - 1;
    while (k--) {
        int x;
        cin >> x;
        // 从u到x添加权重0的边：u ≥ x
        g[u].push_back(x << 1);
        
        // 处理[x_i-1, x_{i+1}-1]区间（普通点）
        if (last + 1 <= x - 1)
            add(u, last + 1, x - 1);
        
        last = x;
    }
    
    // 处理最后一段
    if (last + 1 <= r)
        add(u, last + 1, r);
}

约束表示：

• 对于区间 $[l, r]$，有 $k$ 个"大"点 $x_1, \ldots, x_k$
• 这些"大"点水深 > 其他点
• 建图：创建节点 $u$，表示这些"大"点的最小值
  • $u$ 到每个"大"点：权重0（$u \leq x_i$）
  • 每个普通点到 $u$：权重1（$x_j \geq u + 1$）

步骤5：拓扑排序计算水深

// 计算入度
for (int i = 1; i <= tot; i++)
    for (auto v : g[i])
        ++deg[v >> 1];

// 拓扑排序
queue<int> q;
for (int i = 1; i <= tot; i++)
    if (!deg[i]) q.push(i);

int cc = 0;  // 计数访问的节点
while (!q.empty()) {
    auto x = q.front(); q.pop();
    ++cc;
    
    for (auto v : g[x]) {
        int w = v & 1;    // 权重
        v >>= 1;          // 节点编号
        // 更新：f[v] ≥ f[x] + w
        f[v] = max(f[v], f[x] + w);
        
        if (!--deg[v]) q.push(v);
    }
}

步骤6：验证输出

if (cc != tot) {  // 有环，矛盾
    cout << "NIE\n";
    return 0;
}

// 检查固定点是否符合
for (int i = 1; i <= n; i++)
    if (o[i] && f[i] != o[i]) {
        cout << "NIE\n";
        return 0;
    }

// 检查是否超过10^9
for (int i = 1; i <= n; i++)
    if (f[i] > (int)1e9) {
        cout << "NIE\n";
        return 0;
    }

cout << "TAK\n";
for (int i = 1; i <= n; i++)
    cout << f[i] << " \n"[i == n];

图模型解释

节点类型

1. 原始点（1~n）：对应每个位置的水深
2. 倍增点（p[i][j]）：表示区间的最小值
3. 约束点（u）：表示一组"大"点的最小值

边类型

1. 权重0：a ≥ b 关系
2. 权重1：a ≥ b + 1 关系

为什么正确？

• 拓扑排序确保无环（有环则矛盾）
• f[v] = max(f[v], f[x] + w) 计算最小可行解
• 倍增优化将区间边数从 $O(n^2)$ 降到 $O(n \log n)$

复杂度分析

时间复杂度

• 建图：$O((n+m) \log n + \sum k_i)$
• 拓扑排序：$O(n \log n + m \log n + \sum k_i)$
• 总复杂度：$O((n+m) \log n)$

空间复杂度

• 节点数：约 $n \log n + m$ ≤ 180万
• 边数：约 $O((n+m) \log n)$

示例分析

样例1

5 2 2
2 7      # 点2水深7
5 3      # 点5水深3
1 4 2 2 3  # [1,4]中，点2,3水深>其他
4 5 1 4    # [4,5]中，点4水深>其他

执行过程：

1. 初始：f[1]=1, f[2]=7, f[3]=1, f[4]=1, f[5]=3
2. 处理约束1：点2,3 > 点1,4
3. 处理约束2：点4 > 点5
4. 拓扑排序计算得到：6 7 1000000000 6 3

样例2

3 2 1
2 3
3 5
1 3 1 2  # [1,3]中点2>其他

矛盾：点2>点3，但已知点2=3, 点3=5

算法优势

1. 高效：$O((n+m) \log n)$ 处理大数据
2. 巧妙：倍增优化区间建图
3. 正确：严格的图论模型
4. 通用：可处理各种约束

总结

本题的核心技巧：

1. 差分约束转化：严格大于 → 大于等于+1
2. 倍增优化建图：ST表结构减少边数
3. 拓扑排序计算：DAG上求最长路

通过将约束系统转化为有向图，利用拓扑排序求解，是处理此类区间约束问题的经典方法。