2018 Multi-University Training Contest 1 Distinct Values（set）

题意：

t组数据，每组数据给定n，m，

表示有m个约束，每个约束包含 x,y ，代表区间 [x, y] 里的数字不能相同。

让你用所有的正整数构成一个长度为 n 的区间，使得这个区间元素顺序的字典序最小。

这个题场上的思路是把所有的约束区间排序，然后再用优先队列维护当前可用的最小值。

后来看了dls的代码。发现我们真是弱爆了。

用suc[i]表示每一个左边界为 i 的限制最右可以向右延伸到哪里。

刚开始suc[i] = i; 表示每一个[i, i] 也是一个限制。

例如第三个样例：n = 5, m = 2: [1, 3] [2, 4] 中，suc[i] = { , 3, 4, 3, 4, 5]

用set维护当前可用的数字。开始时加入1~n。

用一个指针 r 代表当前填数到的位置。若 r <= suc[i] ， 代表当前这个限制还没有填完数，继续向下执行，把用过的数字从set中删掉。

用一个L指针记录上一个处理过的区间的起始位置，填好的数组中[L，i-1]内的数值，是可以再次使用的，重新加入set中。

巧妙的是，若r < suc[i] ，代表着有一个新的限制从i 开始。

#include <iostream>

#include <cstdlib>

#include <cstdio>

#include <set>

using namespace std;

#define maxn 100000 + 100

int main()

{

    int t;

    scanf("%d", &t);

    for (int i = ; i <= t; i++)

    {

        int n, m, a[maxn], suc[maxn];

        scanf("%d%d", &n, &m);

        for (int i = ; i <= n; i++)

            suc[i] = i;

        for (int i = ; i <= m; i++)

        {

            int u, v;

            scanf("%d%d", &u, &v);

            suc[u] = max(suc[u], v);

        }

        set<int> st;

        for (int i = ; i <= n; i++)

            st.insert(i);

        int l = , r = ;

        for (int i = ; i <= n; i++)

        {

            if (suc[i] < r) continue;

            while(l < i) st.insert(a[l++]);

            while(r <= suc[i])

            {

                a[r] = *st.begin();

                st.erase(a[r++]);

            }

        }

        for (int i = ; i < n; i++)

            printf("%d ", a[i]);

        printf("%d\n", a[n]);

    }

}