本人的（不知道对不对的）解法

RT，目前可以通过所有民间数据。

因为交不了题解，所以不算讨论区题解罢（如果算，会自删）

首先，一个

O(n\log n)

的解法可以很轻易想出（使用set正着维护每次吃完后剩哪些蛇，然后倒着扫一遍，如果到某一时刻，当前的蛇发现吃掉后会导致自己以后也被吃掉，就将结果时刻设到当前时刻。

O(n)

的解法是在维护set的过程中进行优化。通过打表可以发现最大值-最小值的差是递减的（后来发现并不，一组simple的数据7 8 9就能叉掉该结论本身——但是这组数据太水导致输出的答案是错误的），然后另开一个队列维护最大值-最小值，很明显如果上述结论正确，该队列本身即是单调的，就可以直接从队列首尾取得最大最小值了。

以下是本人考场代码，可以通过所有民间数据。尽管如此，该算法成立的前提（刚才提到了）是不正确的。如果您有可以叉掉它的数据，或是可以证明它正确性的证法，请务必指出。如果它是错误的并且有hack数据，请管理员务必加上，不能让错误的解法通过；如果它是正确的，~~那就算是让我安心了罢~~

CPP

#include<bits/stdc++.h>
using namespace std;
int T,n,m,a[1010000],b[1010000],c[1010000];
pair<int,int>q[1010000];
bool on[1010000];
void func(){
	for(int i=1;i<=n;i++)on[i]=true;
	for(int i=n,j=1,l=1,r=0,id=n;id>=2;id--){
		pair<int,int>u=make_pair(-1,-1);
		if(i>=j)u=max(u,make_pair(a[i],i));
		if(l<=r)u=max(u,q[l]);
		pair<int,int>v=make_pair(0x3f3f3f3f,0x3f3f3f3f);
		if(i>=j)v=min(v,make_pair(a[j],j));
		if(l<=r)v=min(v,q[r]);
		b[id]=v.second,c[id]=u.second;
		on[b[id]]=false;
		if(l<=r&&u==q[l])l++;else i--;
		if(l<=r&&v==q[r])r--;else j++;
		q[++r]=make_pair(u.first-v.first,u.second);
	}
//	for(int i=1;i<=n;i++){for(set<int>::iterator it=t[i].begin();it!=t[i].end();it++)printf("%d ",*it);puts("");}
	int las=1;
	for(int i=2;i<=n;i++)if(!on[c[i]])while(las<i)on[b[++las]]=true;
	printf("%d\n",las);
}
void read(int &x){
	x=0;
	char c=getchar();
	while(c>'9'||c<'0')c=getchar();
	while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
}
int main(){
	freopen("snakes.in","r",stdin);
	freopen("snakes.out","w",stdout);
	read(T),read(n);
	for(int i=1;i<=n;i++)read(a[i]);
	func();
	while(--T){
		read(m);
		for(int i=1,x,y;i<=m;i++)read(x),read(y),a[x]=y;
		func();
	}
	return 0;
}

本人的（不知道对不对的）解法

讨论操作

回复

相关推荐

本人的（不知道对不对的）解法