我这思路还能救一下吗

刚才比赛t1

代码大致思路是：

用权值线段树处理出每个位置之前的比这个位置的数大的数的个数

然后依次枚举若干次操作过后留下来的单调递增的序列，算出其所需的操作次数（操作最后的序列肯定是一个尾项是n，公差是1的序列）

所以先枚举 n ，再枚举 n-1 n，然后n-2 n-1 n ，…… ，依此类推。

由于每一个序列与上一个枚举的序列就差别在第一项

所以用第一项去与上一个枚举的序列的操作次数去加上之前预处理出来的比这个位置大的数的个数，得到这个序列所需的操作次数

但是最后WA了一个点qwq

qwq有没有哪位神犇能帮忙加个特判啥的让蒟蒻的代码能过这题，（玄关

代码

CPP

#include<bits/stdc++.h>
using namespace std;
#define ls (u<<1)
#define rs (u<<1|1)
const int N=1e5+7;
int n,a[N],p[N],k[N];
struct node
{
	int l,r,w;
}tree[N<<2];
void pushup(int u)
{
	tree[u].w=tree[ls].w+tree[rs].w;
}
void build(int u,int l,int r)
{
	tree[u]=(node){l,r,0};
	if(l==r)
	{
		return;
	}
	int mid=(l+r)>>1;
	build(ls,l,mid),build(rs,mid+1,r);
}
void update(int u,int x)
{
	int l=tree[u].l,r=tree[u].r;
	if(l==r)
	{
		tree[u].w++;
	}
	else
	{
		int mid=(l+r)>>1;
		if(x<=mid)
		{
			update(ls,x);
		}
		else
		{
			update(rs,x);
		}
		pushup(u);
	}
}
bool inrange(int L,int R,int l,int r)
{
	return L<=l&&r<=R;
}
bool outrange(int L,int R,int l,int r)
{
	return R<l||r<L;
}
int query(int u,int L,int R)
{
	int l=tree[u].l,r=tree[u].r;
	if(inrange(L,R,l,r))
	{
		return tree[u].w;
	}
	else if(!outrange(L,R,l,r))
	{
		return query(ls,L,R)+query(rs,L,R);
	}
	else
	{
		return 0;
	}
}
signed main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		p[a[i]]=i;
	}
	build(1,1,n);
	for(int i=1;i<=n;i++)
	{
		k[i]=query(1,a[i]+1,n);
		update(1,a[i]);
	}
	int h=0,ans=1e9;
	for(int i=1;i<=n;i++)
	{
		ans=min(ans,n-i+h);
		h+=k[p[n-i]];
	}
	printf("%d\n",ans);
	return 0;
}

我这思路还能救一下吗

讨论操作

回复

相关推荐

我这思路还能救一下吗