出题人题解 | #小y的序列#

原题解链接：https://ac.nowcoder.com/discuss/181037

对于每种颜色，只要找到出现的最靠右的位置和最靠左的位置输出即可。如果找不到，那就藏在下一种颜色下面。

其实可以做到$O(n)O(n)$数据范围受限于$SPJSPJ$

/*
* @Author: wxyww
* @Date:   2019-04-18 14:30:15
* @Last Modified time: 2019-04-18 14:34:18
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cassert>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
using namespace std;
typedef long long ll;
const int N = 100000 + 100;
ll read() {
	ll x=0,f=1;char c=getchar();
	while(c<'0'||c>'9') {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9') {
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
int a[N],L[N],R[N];
int main() {
	int n = read(),m = read();
    assert(n >= 1 && n <= 100000 && m <= 100000 && m >= 1);
	memset(L,0x3f,sizeof(L));
	for(int i = 1;i <= n;++i) {
		int x = read();
		L[x] = min(L[x],i);
        assert(x <= m && x >= 0);
		R[x] = max(R[x],i);
	}
	for(int i = m;i >= 1;--i) {
		if(!R[i]) L[i] = L[i + 1],R[i] = R[i + 1];
	}

	for(int i = 1;i <= m;++i) printf("%d %d\n",L[i],R[i]);
	return 0;
}