题目传送门

作者: BJpers2 更新时间: 2018-07-31 20:25  在Ta的博客查看

我们在做题之前,先要知道这是一道图论题

题意描述有些绕,我在这里再阐述一遍:

  • 给出一个部分未知的数列的,以及数列已知的部分
  • 再给出一些区间。对于每一个区间,在它的内部钦定一些位置,并要求这些位置上的数最后的值,都严格大于区间内其他未钦定的位置上的数。
  • 要求给出任意一种可行的满足条件的数列。

大于关系可以看做是一条边,由较大的数指向较小的数。对于每一个询问,我们考虑让这k个位置上的数与区间内其他的位置两两连有向边。这样一来,问题就转化到图上了。

首先,图上若有环则一定无解,因为它意味着x>xx>x

那么问题变为DAG上问题,只要我们从入读为0的位置开始DP即可。贪心的想,最大的数越大,留给下面的空间就越大(注意数列中的数大于0!),所以每个数的可能值全部设置为1e9。DP时假如遇到了已经确定的数,却发现它撑死了也打不到他预设的值(否则与其他单调关系矛盾),那么问题无解。

最后若有解,输出答案即可。

好完美啊,在你看到k300000\sum k\leq 300000之前还以为是提高组水题。

假如按之前说的那样建图,一次操作就要加入k(rl+1k)k(r-l+1-k)条边,最坏情况下加入的边数在N3N^3级别,空间直接爆炸。

也许你会说,我们可以采用“电话交换机”的建图思想,不再两两连边 而是新拉出一个超级节点,然后只需要k个点向它连边,它向区间内其余点连边即可,只要k+(rl+1k)=rl+1k+(r-l+1-k)=r-l+1条边即可

然而这还是不行。因为如果每个操作区间都是上十万的大区间,而k每次只有1,最多还是要连NkN\sum k条边,仍然爆炸。

注意到,每次我们的空间浪费在,有大量位置连续的点,超级节点却向它们一一连了边。发挥想象力,有什么东西能提高区间操作的效率呢?

线段树!!!

没错,我们把数列建成一棵线段树,然后对于每个操作区间,它会被k个点割成最多k+1个子区间,对于每个区间,可以化成线段树上的最多log(n)log(n)个已知区间,对于超级节点连出的边,一次操作要加klog(n)klog(n)条,算上连向超级节点的,总共是k+klog(n)k+klog(n)。于是总共的边数在(k)log(n)(\sum k)log(n)级别,完全可以接受。

这样连边以后,要注意线段树自身的边只是形式,要赋权为0。

之后按照之前所说的,按拓扑序DP就行了。

Code

/*
 * @Name: 110728
 * @Author: Lovely_XianShen
 * @Date: 2019-10-30 11:07:41
 * @Aqours!Sunshine!!
 */
#include<iostream>
#include<cstdio>
#define N 600010
#define M 2000010
using namespace std;
int a[N], l[N], r[N], ch[N][2], cn;
int sit[N];
int to[M], w[M], nxt[M], pre[N], cnt;
int du[N];
bool done[N];
void ae(int ff, int tt, int ww) {
    cnt++;
    du[tt]++;
    to[cnt] = tt;
    nxt[cnt] = pre[ff];
    pre[ff] = cnt;
    w[cnt] = ww;
}
int build(int ll, int rr) {
    cn++;
    int x = cn;
    l[cn] = ll; r[cn] = rr;
    if (ll == rr) {
        sit[ll] = cn;
        return x;
    }
    int mid = (ll + rr) >> 1;
    ch[x][0] = build(ll, mid);
    ch[x][1] = build(mid + 1, rr);
    ae(x, ch[x][0], 0);
    ae(x, ch[x][1], 0);
    return x;
}
void add(int x, int now, int L, int R) {
    if (l[now] == L && r[now] == R) {
        ae(x, now, 0);
        return;
    }
    int mid = (l[now] + r[now]) >> 1;
    if (R <= mid) add(x, ch[now][0], L, R);
    else if (L > mid) add(x, ch[now][1], L, R);
    else add(x, ch[now][0], L, mid), add(x, ch[now][1], mid + 1, R);
}
void dfs(int x) {
    done[x] = true;
    int i, j;
    for (i = pre[x]; i; i = nxt[i]) {
        j = to[i];
        a[j] = min(a[j], a[x] - w[i]);
        du[j]--;
        if (!du[j]) dfs(j);
    }
}
int c[N], d[N];
int main() {
    int n, s, m;
    scanf("%d%d%d", &n, &s, &m);
    int i, j, k, x, y;
    build(1, n);
    int tmp = cn;
    for (i = 1; i <= cn; i++) a[i] = 1e9;
    for (i = 1; i <= s; i++) {
        scanf("%d%d", &c[i], &d[i]);
        a[sit[c[i]]] = d[i];
    }
    int L, R;
    while (m--) {
        scanf("%d%d%d", &L, &R, &k);
        y = L; cn++;
        for (i = 1; i <= k; i++) {
            scanf("%d", &x);
            ae(sit[x], cn, 1);
            if (x > y) add(cn, 1, y, x - 1);
            y = x + 1;
        }
        if (R >= y) add(cn, 1, y, R);
    }
    for (i = tmp + 1; i <= cn; i++)
        a[i] = 1e9;
    dfs(1);
    for (i = 1; i <= n; i++)
        if (!done[sit[i]] || a[sit[i]] < 1) {
            puts("NIE");
            return 0;
        }
    for (i = 1; i <= s; i++)
        if (a[sit[c[i]]] != d[i]) {
            puts("NIE");
            return 0;
        }
    puts("TAK");
    for (i = 1; i <= n; i++)
        printf("%d ", a[sit[i]]);
    return 0;
}