「GYM102059D」Dumae

发表于 | 更新于 | 分类于 | 阅读次数：

题意简述

GYM102059D

构造一个 $n$ 的排列 $p$，要求 $p_i\in[l_i, r_i]$ 且满足 $m$ 个限制 $(u, v)$，表示 $p_{u} < p_{v}$。
$n\le 3\times 10^5, m\le 10^6$，需判断无解。

主要思路

首先如果没有 $(u, v)$ 的限制，直接从左到右贪心选择右端点最小的即可。
假设有限制 $(u, v)$，可以令 $l_v\gets max\{l_v, l_u + 1\}, r_u\gets \{r_u, r_v - 1\}$。容易发现在这样操作后，$u$ 必定在 $v$ 之前被选择。如果有多个限制，按拓扑序处理即可。
时间复杂度 $O(n\log n + m)$。

参考代码

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
102
103
104
105
#include <bits/stdc++.h>
namespace my_std {
using namespace std;
#define reg register
#define Rint register int
#define FOR(i, a, b) for (register int i = (a), ed_##i = (b); i <= ed_##i; ++i)
#define ROF(i, a, b) for (register int i = (a), ed_##i = (b); i >= ed_##i; --i)
#define Templ(T) template <typename T>
Templ(_Tp) inline int chkmin(_Tp &x, _Tp y) { return x > y ? x = y, 1 : 0; }
Templ(_Tp) inline int chkmax(_Tp &x, _Tp y) { return x < y ? x = y, 1 : 0; }
} // namespace my_std
using namespace my_std;

#define MMR (1 << 23)
struct INPUT{
    char buf[MMR], *s, *t;
    INPUT(){ t = (s = buf) + fread(buf, 1, MMR, stdin); }
    #define gc() (s == t ? \
    (t = (s = buf) + fread(buf, 1, MMR, stdin), \
    s == t ? -1 : *s++) : *s++)
    inline INPUT& operator >>(int &x){
        x = 0;
        reg char c(gc());
        while(c < 48) c = gc();
        while(c > 47) x = x * 10 + c - 48, c = gc();
        return *this;
    }
}fin;
struct OUTPUT{
    char buf[MMR], *s;
    OUTPUT(){ s = buf; }
    inline OUTPUT& operator <<(int x){
        static int tmp[10];
        Rint *top = tmp;
        do{
            *++top = (x % 10) ^ 48, x /= 10;
        }while(x);
        while(top != tmp) *s++ = *top--;
        *s++ = 10;
        return *this;
    }
    ~OUTPUT(){ fwrite(buf, 1, s - buf, stdout); }
}fout;

#define N 300010
#define M 1000010
struct segment{
    int l, r, i;
    inline segment(): l(0), r(0), i(0){}
    inline segment(const int &_l, const int &_r, const int &_i)
        : l(_l), r(_r), i(_i){}
    inline bool operator <(const segment &x)const{
        return r > x.r;
    }
}s[N];
int n, m;
int ind[N], ans[N];
vector<int> E[N];
int Q[N];
priority_queue<segment> P;

inline void topo(){
    Rint *ql(Q), *qr(Q);
    FOR(i, 1, n) !ind[i] && (*qr++ = i);
    while(ql != qr){
        Rint u = *ql++;
        for(Rint v: E[u]) !--ind[v] && (*qr++ = v);
    }
    Rint *t(Q);
    while(t != qr){
        Rint u = *t++;
        for(Rint v: E[u]) chkmax(s[v].l, s[u].l + 1);
    }
    while(t != Q){
        Rint u = *--t;
        for(Rint v: E[u]) chkmin(s[u].r, s[v].r - 1);
    }
}

int main() {
    fin >> n >> m;
    FOR(i, 1, n) fin >> s[i].l >> s[i].r, s[i].i = i;
    Rint u, v;
    FOR(i, 1, m){
        fin >> u >> v;
        E[u].push_back(v);
        ++ind[v];
    }
    topo();
    FOR(i, 1, n) if(ind[i] || s[i].l > s[i].r) return puts("-1"), 0;
    sort(s + 1, s + n + 1, [&](const segment &lhs, const segment &rhs){
        return lhs.l == rhs.l ? lhs.i < rhs.i: lhs.l < rhs.l;
    });
    reg segment *t(s + 1), res;
    const segment *ed_t(s + n + 1);
    FOR(i, 1, n){
        while(t != ed_t && t->l <= i) P.push(*t++);
        if(P.empty()) return puts("-1"), 0;
        res = P.top(), P.pop();
        if(res.r < i) return puts("-1"), 0;
        ans[i] = res.i;
    }
    FOR(i, 1, n) fout << ans[i];
    return 0;
}