2018多校 hdu-6301 Distinct Values

題目連結：http://acm.hdu.edu.cn/showproblem.php?pid=6301

題意：給你一個長度為n的序列，有m個限制（在【l，r】區間内的所有元素都不同），構造一個字典序最小的序列

思路：用一個set存放目前能用的所有數，用一個數組pre記錄每個位置所屬的區間起點，一個區間指派完後，後面的區間就可用到兩個區間起點之間的所有元素，不斷取出set中最小的數即可。

代碼：

#include <iostream>
#include <set>
#include <cstdio>
#include <algorithm>
using namespace std;
int pre[100010];
int ret[100010];
int n,m;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        for(int i = 1;i <= n;i++)
        {
            pre[i] = i;
        }
        int l,r;
        for(int i = 1;i <= m;i++)
        {
            scanf("%d%d",&l,&r);
            pre[r] = min(pre[r],l);
        }
        for(int i = n - 1;i >= 1;i--)
        {
            pre[i] = min(pre[i],pre[i+1]);
        }
        int id = 1;
        set<int> ans;
        for(int i = 1;i <= n;i++)
        {
            ans.insert(i);
        }
        for(int i = 1;i <= n;i++)
        {
            while(id < pre[i])
            {
                ans.insert(ret[id]);
                id++;
            }
            ret[i] = *ans.begin();
            ans.erase(ret[i]);
        }
        for(int i = 1;i <= n;i++)
        {
            if(i!=n)
            printf("%d ",ret[i]);
            else
            printf("%d\n",ret[i]);
        }
    }
    return 0;
}