Distinct Values (set思维构造)

Distinct Values

题意

给你一个n，一个q，表示数列中有n个元素，q个区间询问，每次一个[l,r]，表示此区间内的数字不能有重复，要求输出最小字典序的。

思路

先对区间进行排序，按照l从小到大，另外，如果有相同l的，按r从大到小。

然后用set维护可以放在此区间的数字。

看！代码

#include <bits/stdc++.h>
using namespace std;
bool cmp(pair<int,int>a,pair<int,int>b)
{
    if(a.first==b.first)
        return a.second>b.second;
    return a.first<b.first;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,q,l,r;
        scanf("%d%d",&n,&q);
        set<int>val;
        vector<pair<int,int> >p;
        vector<int>x(n+5);
        for(int i = 1 ;i <= n ; i++)
            p.push_back( make_pair(i,i) );
        for(int i=1;i<=n;i++)
            val.insert(i);
        for(int i=1;i<=n;i++)
            x[i]=1;
        for(int i=0;i<q;i++)
        {
            scanf("%d%d",&l,&r);
            p.push_back(make_pair(l,r));
        }
        sort(p.begin(),p.end());
        int left=1,cur=1;
        set<int>::iterator it,bef;
        for(int i=0;i<p.size();i++)
        {
            while(left<p[i].first)
                val.insert(x[left++]);
            for(it=val.begin();it!=val.end()&&cur<=p[i].second;)
            {
                x[cur++]=*it;
                int s=*it;
                it++;
                val.erase(s);
            }
        }
        for(int i=1;i<=n-1;i++)
            printf("%d ",x[i]);
        printf("%d\n",x[n]);
    }
    return 0;
}