题目链接：https://codeforces.com/contest/1288/problem/E
题目大意：
#include <bits/stdc++.h>
#define LL long long
using namespace std;
#define id(x) ((x-1)*Len+1)
struct node{
int L, R, k;
}q[1000005];
int pos[1000005];
int a[1000005];
int flag[1000005];//保存当前区间前缀和的个数
int n, m, cut=0;//询问个数
int ans=0, l=1, r=0;
vector<int> v[1000005];
int L[1000005], R[1000005];//桶
bool cmp(node a, node b){
return pos[a.L]==pos[b.L]?(pos[a.L]&1)?a.R<b.R:a.R>b.R:pos[a.L]<pos[b.L];
}
void add(int x){
ans+=(++flag[a[x]]==1);
}
void del(int x){
ans-=(--flag[a[x]]==0);
}
int main(){
scanf("%d%d", &n, &m);
int Len=sqrt(n+m);
for(int i=1; i<=n; i++){
a[i]=n-i+1;
v[n-i+1].push_back(i);
L[i]=i;
pos[i]=i/Len;
}
for(int i=n+1; i<=n+m; i++){
scanf("%d", &a[i]);
v[a[i]].push_back(i);
L[a[i]]=1;
pos[i]=i/Len;
}
for(int i=1; i<=n; i++){
v[i].push_back(n+m+1);
for(int j=1; j<v[i].size(); j++){
q[++cut].L=v[i][j-1];
q[cut].R=v[i][j]-1;
q[cut].k=i;
}
}
sort(q+1, q+cut+1, cmp);
for(int i=1; i<=cut; i++){
while(l<q[i].L){
del(l);
l++;
}
while(l>q[i].L){
l--;
add(l);
}
while(r<q[i].R){
r++;
add(r);
}
while(r>q[i].R){
del(r);
r--;
}
R[q[i].k]=max(R[q[i].k], ans);
}
for(int i=1; i<=n; i++){
printf("%d %d\n", L[i], R[i]);
}
return 0;
}