那必然是这个标题了。

模拟赛的题。

正解是比较合理的线段树。但是@te_bie_zhi_chu 大神想到了乱搞做法，求分析复杂度/努力卡掉他的玄学乱搞。

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m,a[300000],ge[300000],pand,l[300000],r[300000],wei1,wei2,wei3,wei4;
int gg,ll[300000],rr[300000],lll,rrr,lz[300000],rz[300000],gez,ans,last;
struct edge{
	int zhi;
}tree[800000];
void add(int id,int l,int r,int q,int w,int qw){
	if(q>w){
		return;
	}
	if(q<=l&&r<=w){
		tree[id].zhi+=qw;
		return;
	}
	int mid=(l+r)/2;
	if(q<=mid){
		add(id*2,l,mid,q,w,qw);
	}
	if(w>mid){
		add(id*2+1,mid+1,r,q,w,qw);
	}
	return;
}
int query(int id,int l,int r,int q){
	if(l==r){
		return tree[id].zhi;
	}
	int he=tree[id].zhi;
	int mid=(l+r)/2;
	if(q<=mid){
		he+=query(id*2,l,mid,q);
	}
	else{
		he+=query(id*2+1,mid+1,r,q);
	}
	return he;
}
inline void chong(){
	if(wei1==2&&wei2==1){
		return;
	}
	else if(wei3>wei2||wei1>wei4){
		wei1=2;
		wei2=1;
		return;
	}
	else if(wei1<=wei3&&wei2<=wei4&&wei3<=wei2){
		wei1=wei3;
		return;
	}
	else if(wei1<=wei3&&wei4<=wei2){
		wei1=wei3;
		wei2=wei4;
		return;
	}
	else if(wei3<=wei1&&wei1<=wei4&&wei4<=wei2){
		wei2=wei4;
		return;
	}
	return;
}
signed main(){
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		ge[a[i]]++;
	}
	a[n+1]=a[1];
	for(int i=1;i<=n;i++){
		l[i]=min(a[i],a[i+1])+1;
		r[i]=max(a[i],a[i+1])-1;
		add(1,1,m,l[i],r[i],1);
	}
	l[0]=l[n];
	r[0]=r[n];
	for(int i=1;i<=n;i++){
		wei1=l[i];
		wei2=r[i];
		wei3=l[i-1];
		wei4=r[i-1];
		chong();
		lll=wei1;
		rrr=wei2;
		add(1,1,m,wei1,wei2,-1);
		gez=0;
		for(int j=1;j<=gg;j++){
			wei3=ll[j];
			wei4=rr[j];
			chong();
			if(wei1==2&&wei2==1){
				wei1=lll;
				wei2=rrr;
				continue;
			}
			add(1,1,m,wei1,wei2,1);
			if(wei1==lll){
				lll=wei2+1;
				wei1=lll;
				wei2=rrr;
				continue;
			}
			gez++;
			lz[gez]=lll;
			rz[gez]=wei1-1;
			lll=wei2+1;
			wei1=lll;
			wei2=rrr;
		}
		if(lll<=rrr){
			gez++;
			lz[gez]=lll;
			rz[gez]=rrr;
		}
		gg=gez;
		for(int j=1;j<=gg;j++){
			ll[j]=lz[j];
			rr[j]=rz[j];
		}
	}
	for(int i=1;i<=m;i++){
		if(!ge[i]){
			cout<<-1<<" ";
		}
		else{
			cout<<query(1,1,m,i)+n-ge[i]<<" ";
		}
	}
	return 0;
}

上面是他代码

底下是我敲的正解。。。大家参考一下

#include<bits/stdc++.h>
#define int long long
using namespace std;
long long a[400005],xds[400005],n,m,ans[400005];
vector<int>T[400005];
struct Segment_Tree{
	int l,r,left_val,right_val,sum_val,sum;
};
inline Segment_Tree push_up(Segment_Tree l,Segment_Tree r){
	Segment_Tree ans;
	ans.l=l.l;
	ans.r=r.r;
	ans.left_val=ans.right_val=ans.sum_val=ans.sum=0;
	ans.sum_val=l.sum_val+r.sum_val;
	if(l.sum&&r.sum){
		if(xds[l.r]!=xds[r.l]){
			ans.sum=l.sum+r.sum;
		}
		else{
			ans.left_val=l.sum;
			ans.right_val=r.sum;
		}
		return ans;
	}
	if(l.sum){
		if(xds[l.r]!=xds[r.l]){
			ans.left_val=l.sum+r.left_val;
		}
		else{
			ans.left_val=l.sum;
			ans.sum_val+=r.left_val/2;
		}
	}
	else{
		ans.left_val=l.left_val;
	}
	if(r.sum){
		if(xds[r.l]!=xds[l.r]){
			ans.right_val=r.sum+l.right_val;
		}
		else{
			ans.right_val=r.sum;
			ans.sum_val+=l.right_val/2;
		}
	}
	else{
		ans.right_val=r.right_val;
	}
	if(!l.sum&&!r.sum){
		if(xds[l.r]!=xds[r.l]){
			ans.sum_val+=(l.right_val+r.left_val)/2;
		}
		else{
			ans.sum_val+=l.right_val/2+r.left_val/2;
		}
	}
	return ans;
}
Segment_Tree tree[1600005];
inline void build(int l,int r,int p){
	if(l==r){
		tree[p].l=l;
		tree[p].r=l;
		tree[p].sum=1;
		return;
	}
	int mid=(l+r)/2;
	build(l,mid,p*2);
	build(mid+1,r,p*2+1);
	tree[p]=push_up(tree[p*2],tree[p*2+1]);
	return;
}
inline void update(int l,int r,int p,int pos){
	if(l==r){
		tree[p].l=l;
		tree[p].r=l;
		tree[p].sum=1;
		return;
	}
	int mid=(l+r)/2;
	if(pos<=mid){
		update(l,mid,p*2,pos);
	}
	else{
		update(mid+1,r,p*2+1,pos);
	}
	tree[p]=push_up(tree[p*2],tree[p*2+1]);
	return;
}
inline Segment_Tree query(int nl,int nr,int l,int r,int p){
	if(nl>nr){
		Segment_Tree ans;
		ans.l=0;
		ans.r=-1;
		ans.left_val=0;
		ans.right_val=0;
		ans.sum=0;
		ans.sum_val=0;
		return ans;
	}
	if(nl<=l&&nr>=r){
		return tree[p];
	}
	int mid=(l+r)/2;
	if(mid>=nl&&mid<nr){
		return push_up(query(nl,nr,l,mid,p*2),query(nl,nr,mid+1,r,p*2+1));
	}
	else if(mid>=nl){
		return query(nl,nr,l,mid,p*2);
	}
	else{
		return query(nl,nr,mid+1,r,p*2+1);
	}
}
signed main(){
//	system("fc my.out ring2.out");
//	freopen("ring2.in","r",stdin);
//  freopen("data.in","r",stdin);
//	freopen("my.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		a[i+n]=a[i];
	}
	for(int i=1;i<=(n<<1);i++){
		T[a[i]].push_back(i);
	}
	build(1,2*n,1);
	for(int i=1;i<=m;i++){
		if(T[i].empty()){
			ans[i]=-1;
			continue;
		}
		int sum=0;
		for(int j=0;j<T[i].size();j++){
			if(T[i][j]>n){
				break;
			}
			Segment_Tree ans;
			ans.l=0;
			ans.r=0;
			ans.left_val=0;
			ans.right_val=0;
			ans.sum=0;
			ans.sum_val=0;
			ans=query(T[i][j]+1,T[i][j+1]-1,1,n*2,1);
			sum+=ans.r-ans.l+1+ans.sum_val;
			if(ans.sum){
				sum+=ans.sum/2;
			}
			else{
				sum+=ans.left_val/2+ans.right_val/2;
			}
		}
		ans[i]=sum;
		for(int j=0;j<T[i].size();j++){
			xds[T[i][j]]=1; 
			update(1,n*2,1,T[i][j]);
		}
	}
	for(int i=1;i<=m;i++){
		cout<<ans[i]<<" ";
	}
	return 0;
}