原始题目

Distinct Values

• Time Limit: 4000/2000 MS (Java/Others)
• Memory Limit: 32768/32768 K (Java/Others)
• Total Submission(s): 3168
• Accepted Submission(s): 1017

Problem Description

Chiaki has an array of \(n\) positive integers. You are told some facts about the array: for every two elements \(a\_i\) and \(a\_j\) in the subarray \(a\_{l \cdots r} (l≤i<j≤r)\), \(a\_i≠a\_j\) holds.

Chiaki would like to find a lexicographically minimal array which meets the facts.

Input

There are multiple test cases. The first line of input contains an integer \(T\), indicating the number of test cases. For each test case:

The first line contains two integers \(n\) and \(m (1≤n,m≤105)\) -- the length of the array and the number of facts. Each of the next \(m\) lines contains two integers \(l\_i\) and \(r\_i\) \((1≤li≤ri≤n)\).

It is guaranteed that neither the sum of all \(n\) nor the sum of all \(m\) exceeds 106.

Output

For each test case, output \(n\) integers denoting the lexicographically minimal array. Integers should be separated by a single space, and no extra spaces are allowed at the end of lines.

Sample Input

3
2 1
1 2
4 2
1 2
3 4
5 2
1 3
2 4

Sample Output

1 2
1 2 1 2
1 2 3 1 1

Source

2018 Multi-University Training Contest 1

Recommend

liuyiding

题目大意

对于一个数列，已知其 m 个子区间，每个子区间内数列的项两两不同，求复合条件的字典序最小的数列。

解题思路

• 要求字典序最小，算法就是从前贪心的让每一位都是当前可使用数的最小值（从 1 开始）。

• 那么如何处理出第 i 位可用数字的最小值？

  • 预处理出\(pre[i]\)（包含第 i 位线段的最小左端点，即与第 i 位不相同的最早位置）
  • 用 set 维护当前可使用的数，\(pt\)指向当前可用最小数的位置，
  • 求每一位的\(ans[i]\)时，先检查，当\(pt<pre[i]\)时，说明\(pt\)到\(pre[i]\)位置间使用过的数可以再次使用，所以开始向 set 容器里补充\(pt\)位置的数， 直至\(pt=pre[i]\)，再取 set 容器中的最小值付给\(ans[i]\)

• 如何与处理出\(pre[i]\)（见下图）

解题代码

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define np next_permutation
#define all(x) x.begin(),x.end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> vi;
typedef long long ll;
typedef pair<int,int> pii;
const int mod=1e9+7;
const int maxn=2e5+5;
set <int> s;
int pre[maxn],n,m,ans[maxn];   //预处理出不可相同的区间前端点。
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		s.clear();
		scanf("%d%d",&n,&m);
		rep(i,1,n+1){
			pre[i]=i; //没有限制条件，前端点都是自身
			s.insert(i);
		}
		rep(i,1,m+1){
			int l,r;
			scanf("%d%d",&l,&r);
			pre[r]=min(l,pre[r]); //有可能多个区间右端点相同。
			//易错写成 pre[r]=l;忘记更新
		}
		per(i,1,n) pre[i]=min(pre[i],pre[i+1]);  //易错写成n+1

		//处理完毕
		//初始set均可用
		int pt=1;
		//pt记录当前不可用线段开头
		rep(i,1,n+1){
			//开头更替，则往set里补充可用最小值
//			cout<<"pt="<<pt<<"  pre[i]="<<pre[i]<<endl;
			while(pt<pre[i]){
				s.insert(ans[pt++]);
			}
			ans[i]=*s.begin();
			s.erase(*s.begin());

		}
		rep(i,1,n+1){
			if(i==1) printf("%d",ans[i]);
			else printf(" %d",ans[i]);
		}
		printf("\n");
	}
}

收获与反思

• 预处理出线段的左端点。
• 贪心的考虑每一位的最小值。