C++14(g++5.4) 解法, 执行用时: 88ms, 内存消耗: 4796K, 提交时间: 2020-06-23 14:41:04

#include <iostream>
using namespace std;
const int MAXN=400010;
int t[MAXN],n,m;
int lowbit(int x)
{
    return x&(-x);
}

void add(int pos,int val=1)
{
    while(pos<=MAXN)
    {
        t[pos]+=val;
        pos+=lowbit(pos);
    }
}

int ask(int pos)
{
    int ans=0;
    while(pos>=1)
    {
        ans+=t[pos];
        pos-=lowbit(pos);
    }
    return ans;
}

int R[MAXN],no[MAXN];
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        add(i);
        R[i]=no[i]=i;
    }
    for(int i=1;i<=m;i++)
    {
        int x;
        cin>>x;
        R[x]=min(R[x],ask(no[x]));
        add(no[x],-1);
        no[x]=n+i;
        add(no[x]);
    }
    for(int i=1;i<=n;i++)
    {
        R[i]=min(R[i],ask(no[i]));
        cout<<R[i]<<" ";
    }
    
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 122ms, 内存消耗: 7008K, 提交时间: 2020-05-24 16:43:01

#include<iostream>
using namespace std;
int cnt=0;
int a[200005],rem[200005],l[400005],tree[800005],ans[200005];
int N;
int lowbit(int x){
	return x&(-x);
}
void add(int x,int num){
	while(num<=N){
		tree[num]+=x;
		num+=lowbit(num);
	}
}
int ask(int num){
	int ans=0; 
	while(num){
		ans+=tree[num];
		num-=lowbit(num);
	}
	return ans;
}
int main(){
	int n,m;
	cin>>n>>m;
	N=n+m;
	for(int i=1;i<=n;i++){
		a[i]=i;
		rem[i]=i;
		l[i]=i;
		ans[i]=i;
	}
	for(int i=1;i<=m;i++){
		cin>>l[n+i];
		int x=l[n+i];
		add(1,rem[x]+1);
		add(-1,n+i);
		ans[x]=min(ans[x],a[x]-ask(rem[x]));
		a[x]=n;
		add(-9999999,rem[x]);
		add(9999999,rem[x]+1);
		rem[x]=n+i;
	}
	for(int i=1;i<=n;i++){
		ans[i]=min(ans[i],a[i]-ask(rem[i]));
	}
	for(int i=1;i<=n;i++){
		cout<<ans[i]<<" ";
	}
	return 0;
}