2018HDU多校1-1004-Distinct Values（hdu6299）-区间,set

题意：

构造一个字典序最小的数列，给出m个限定条件，对于每个限定条件，l:r，表示该数列中a[l:r]中各个数不相同

思路：

先将限定条件按最左最长排序，分三种情况讨论
1.若某区间完全被其他区间包含则略过
2.若两区间有重合部分，则重合部分不变，后部分从小到大填入可用数
3.若两区间没有重合部分，则两区间之间不相交部分都填1，后一区间从1开始填入数字
因每区间中满足不重复，且从小到大排列，适用set，每次回收前一区间中可取部分，加入set，后从set中取首元素填入区间

其他方法：

区间mex(莫队)、优先队列

代码：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <set>
using namespace std;

set<int>S;
struct node
{
    int l,r;
    int id;
}a[1000005];

bool cmp(node a,node b)
{
    if(a.l==b.l)
        return a.r>b.r;
    return a.l<b.l;
}
int ans[100005];

int main()
{
    std::ios::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--)
    {
        S.clear();
        int n,m;
        cin>>n>>m;
        for(int i=1;i<=n;i++)
        {
            ans[i]=1;
            S.insert(i);     //初始化将1~n加入set中
        }

        for(int i=0;i<m;i++)
        {
            cin>>a[i].l>>a[i].r;
            a[i].id=i;
        }
        sort(a,a+m,cmp);

        int nl=a[0].l;
        int nr=a[0].r;
        int cnt=1;
        for(int j=nl;j<=nr;j++)
        {
            ans[j]=*S.begin();      //每次取set首元素填入区间
            S.erase(S.begin());
        }

        for(int i=1;i<m;i++)
        {
            if(a[i].l>=nl && a[i].r<=nr) continue;   //完全被包含则略过
            else if(a[i].r>nr && a[i].l<=nr)      //两区间重合时
            {
                int cl=a[i].l;
                int cr=nr;
                for(int j=nl;j<cl;j++)          //将前一区间起点nl到当前区间起点cl之间的数重新加入set，表示这些数可被再次使用
                    S.insert(ans[j]);
                int j=cr+1;
                while(j<=a[i].r)              //重合部分尾cr到当前区间尾a[i].r，取set首元素填入区间
                {
                    ans[j]=*S.begin();
                    S.erase(S.begin());
                    j++;
                }
            }

            else if(a[i].l>nr)       //完全不重合时
            {
                for(int j=nl;j<=nr;j++)       //回收前一区间元素
                    S.insert(ans[j]);
                for(int j=a[i].l;j<=a[i].r;j++)    //从1开始填入当前区间
                {
                    ans[j]=*S.begin();
                    S.erase(S.begin());
                }
            }
            nl=a[i].l;
            nr=a[i].r;
        }
        for(int i=1;i<=n;i++)
        {
            if(i==1) cout<<ans[i];
            else cout<<" "<<ans[i];
        }
        cout<<endl;
    }
    return 0;
}