2018 Multi-University Training Contest 1 ：Distinct Values

#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;

const int maxn=100000+100;

struct Node{
  
  int l,r;
}node[maxn];
int ans[maxn];

inline bool cmp(Node a,Node b){
  
  return a.l==b.l?a.r<b.r:a.l<b.l;
}

int main(){
  
  int T;
  scanf("%d",&T);
  while(T--){
    
    priority_queue<int,vector<int>,greater<int> >que;  
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++) scanf("%d%d",&node[i].l,&node[i].r);
    sort(node,node+m,cmp);
    
    for(int i=1;i<=n;i++) que.push(i); //整個區間最多需要n種數，基于貪心，當然是[1,n] 
    for(int i=node[0].l;i<=node[0].r;i++) ans[i]=que.top(),que.pop();
    Node now=node[0]; // 現在所在的區間 
    for(int i=1;i<m;i++){
      
      if(node[i].r<=now.r) continue;  //此時node[i].r<=now.r ,又node[i].l>=now.l ,這個區間就沒有必要了 
      
      for(int j=now.l;j<=now.r && j<node[i].l;j++)  que.push(ans[j]);  //釋放前一個區間不與目前區間相交的區間，注意 j<=now.r && j<node[i].l ，有可能不相交 
      for(int j=max(now.r+1,node[i].l);j<=node[i].r;j++){   //注意 j=max(now.r+1,node[i].l)， 還是因為有可能不相交 
        
        ans[j]=que.top(),que.pop();
      }
      now=node[i];  //更新現在所在的區間 
    }
    for(int i=1;i<=n;ans[i]=0,i++) printf("%d%c",ans[i]?ans[i]:1,i==n?'\n':' ');  //ans[]==0，說明是沒有必要不一樣的，基于貪心，就都為1，記得ans[]要清0 
  }
}