Tutorial #
A faster way to simulate the process is that instead of moving the hole array, we can add some extra space in front of the array and simply move the element to the extra space. For example, in the sample input:
5 4
3 5 1 4
The process would look like
_ _ _ _ 1 2 3 4 5
_ _ _ 3 1 2 _ 4 5
_ _ 5 3 1 2 _ 4 _
_ 1 5 3 _ 2 _ 4 _
4 1 5 3 _ 2 _ _ _
We can use a fenwick tree to simulate the process: mark a position with 1 if it’s occupied by some number and the prefix sum is how many elements is in front of it (i.e. the real position in the simulator). In the end, don’t forget to update the position of all the elements in case some are not moved.
Code #
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define for1(i, n) for (int i = 1; i <= int(n); ++i)
#define ms(a, x) memset(a, x, sizeof(a))
#define F first
#define S second
#define all(x) (x).begin(),(x).end()
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());
template<typename... Args> void rd(Args&... args) {((cin >> args), ...);}
template<typename... Args> void wr(Args... args) { ((cout << args << " "), ...); cout<<endl;}
struct fenwick{
int n;
vector<ll> t;
fenwick(int n_):n(n_),t(n+1){}
void add(int i,int x){
for(i++;i<=n;i+=i&-i){
t[i]+=x;
}
}
int query(int i){
ll res=0;
for(i++;i>0;i-=i&-i) res+=t[i];
return res;
}
int query(int l,int r){
return query(r)-query(l-1);
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,m;
cin>>n>>m;
vector<int> l(n),r(n);
iota(all(l),0);
r=l;
vector<int> pos(n);
forn(i,n) pos[i]=i+m;
fenwick tree(n+m+1);
forn(i,n) tree.add(i+m,1);
forn(i,m){
int x;
cin>>x;
x--;
l[x]=0;
r[x]=max(r[x],tree.query(pos[x]-1));
tree.add(pos[x],-1);
pos[x]=m-i-1;
tree.add(pos[x],1);
}
forn(i,n) r[i]=max(r[i],tree.query(pos[i]-1));
forn(i,n) wr(l[i]+1,r[i]+1);
return 0;
}