线段树优化建图 + 拓扑排序。

Table of Contents

  1. Description
  2. Solution

Description

给定一个长度为$n$的正整数序列$a$，每个数都在$1$到$10^9$范围内，告诉你其中$s$个数，并给出$m$条信息，每条信息包含三个数$l,r,k$以及接下来$k$个正整数，表示$a[l],a[l+1],\ldots ,a[r-1],a[r]$里这k个数中的任意一个都比任意一个剩下的$r-l+1-k$ 个数大（严格大于，即没有等号）。

请任意构造出一组满足条件的方案，或者判断无解。

Solution

我们用边来表示增量关系. $(u, v, 1)$ 表示$v$比$u$至少大$1$. 我们发现为了满足要求, 就有拓扑关系, 否则就会无限制地增量下去.

由于$\sum{k} \le 300000$, 也就是分割次数不是很多, 所以一定都是一些区间同时满足增量关系, 而且区间数量不大, 那么我们就可以考虑虚拟点+线段树优化的方式.

线段树每个节点向子节点连0边, 剩余区间向每次的虚拟点连1边, 虚拟点向规定位置连0边, 拓扑排序一边跑一遍更新每个位置允许的最小值. 如果加爆了$10^9$或者有环都是无解的.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <queue>

using namespace std;

const int maxn = 1e+5 + 5;
const int inf = int(1e+9);

struct edge
{
  int to, nxt, v;
}e[maxn << 4];
int n, s, m, ls[maxn << 1], rs[maxn << 1], cnt, ptr, lnk[maxn << 2];
int a[maxn << 2], f[maxn << 2], mp[maxn], dgr[maxn << 2];
int vir, q[maxn*3];
queue<int> que;

inline void add(int bgn ,int end, int val) {
  e[++ptr] = (edge){end, lnk[bgn], val};
  lnk[bgn] = ptr; dgr[end]++;
}
int build(int l, int r) {
  int newrt = ++cnt;
  if (l == r) {
    mp[l] = newrt;
    return newrt;
  }
  int mid = (l + r) >> 1;
  ls[newrt] = build(l, mid); add(ls[newrt], newrt, 0);
  rs[newrt] = build(mid + 1, r); add(rs[newrt], newrt, 0);
  return newrt;
}
void update(int cur, int l, int r, int L, int R) {
  if (L > R) return;
  if (L <= l && r <= R) {
    add(cur, vir, 1);
    return;
  }
  int mid = (l + r) >> 1;
  if (L <= mid) update(ls[cur], l, mid, L, R);
  if (R > mid) update(rs[cur], mid + 1, r, L, R);
}
inline int rd() {
  register int x = 0, c = getchar();
  while (!isdigit(c)) c = getchar();
  while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
  return x;
}

int main() {
  n = rd(); s = rd(); m = rd();
  build(1, n);
  for (int i = 1; i <= s; ++i) {
    int x = rd();
    a[mp[x]] = rd();
  }
  int l, r, k;
  vir = cnt;
  for (int i = 1; i <= m; ++i) {
    l = rd(); r = rd(); k = rd();
    ++vir;
    for (int j = 1; j <= k; ++j) {
      q[j] = rd();
      add(vir, mp[q[j]], 0);
    }
    update(1, 1, n, l, q[1] - 1);
    update(1, 1, n, q[k] + 1, r);
    for (int j = 2; j <= k; ++j)
      update(1, 1, n, q[j - 1] + 1, q[j] - 1);
  }
  int count = 0;
  for (int i = 1; i <= vir; ++i)
    if (!dgr[i]) que.push(i), count++, f[i] = 1;
  while (!que.empty()) {
    int u = que.front(); que.pop();
    if (f[u] > inf) {
      puts("NIE"); return 0;
    }
    if (a[u]) {
      if (a[u] < f[u]) {
        puts("NIE"); return 0;
      }
      if (a[u] > f[u]) f[u] = a[u];
    }
    for (int p = lnk[u]; p; p = e[p].nxt) {
      int y = e[p].to;
      f[y] = max(f[y], f[u] + e[p].v);
      if (!--dgr[y]) que.push(y), count++;
    }
  }
  if (count < vir) {
    puts("NIE"); return 0;
  }
  puts("TAK");
  for (int i = 1; i <= n; ++i) printf("%d ", f[mp[i]]);
  return 0;
}