【正经题解】贪吃蛇

引入
首先我们以一道经典的海盗分金问题来做引入，这对这道题有很大启发。

我们有5 个海盗，他们要分 100 个金币，5 个海盗从一号开始一次提出自己的分金方案，然后投票表决。如果第一个海盗的方案得到了半数以上的人的同意，那么按照一号的方案分钱。否则一号会被扔到海里喂鲨鱼。然后再表决二号的方案，以此类推。假设所有海盗足够聪明，请问一号最多获得多少钱？

先说答案，如果没有做过这道题，你肯定会大吃一惊：$97$.
具体海盗问题可自行了解下，会对理解这个题目有很大帮助。

这个题的思路就和贪吃蛇的思路有点类似了，我们现在再来理解 snakes 这道题会好很多。
我们现在考虑解题方法。

现在我们的蛇长度是 $a_1$,$a_2$,……,$a_n$。吃一次会得到一条新的蛇$a_n-a_1$，长度为 因为蛇足够聪明，只要能吃，最长的蛇就一直吃，直到最长的蛇吃了最短的蛇后变成了最短的蛇。这符合贪心的策略。这个贪心思路很简单，一开始我就想到这里，开心打了代码。结果大样例和答案老是差 $1$。大概最后还剩半个小时的时候想到了这种情况：
1
3
3 4 5 6

#include<bits/stdc++.h>
using namespace std;

int read() {
	char ch=getchar();
	int f=1,x=0;
	while(ch<'0'||ch>'9') {
		if(ch=='-')
			f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') {
		x=x*10+ch-'0';
		ch=getchar();
	}
	return f*x;
}

const int maxn=1e6+10;

int n;

struct snakes {
	int id,len;
	
	bool operator <(snakes b) const {
		if(len!=b.len) {
			return len<b.len;
		}
		return id<b.id;
	}
	
	snakes operator -(snakes b) {
		snakes ret;
		ret.len=len-b.len;
		ret.id=id;
		return ret;
	}
}a[maxn];//结构体

typedef set<snakes>::iterator its;
set<snakes> s;

bool eatornot() {//判断是否还能再吃
	if(s.size()==2) {
		return 1;//还剩下两条蛇当然随便吃，返回1
	}
	its ib,ie,ib2;
	ib=s.begin();
	ie=s.end();
	ie--;
	ib2=ib;
	ib2++;
	
	snakes now=(*ie);
	now.len=(*ie).len-(*ib).len;
	if(!(now<(*ib2))) {
		return 1;//如果吃了不是最短的，说明可以吃
	} 
	s.erase(ib);
	s.erase(ie);
	s.insert(now);
	return !eatornot();
	//注意取反操作
	//如果现在能吃，说明上一条蛇不该吃
	//反之亦然
}

signed main() {	
	int t;
	t=read();
	
	for(int Q=1;Q<=t;Q++) {
		if(Q==1) {
			n=read();
			for (int i = 1; i <= n; ++i) {
				a[i].len=read();
				a[i].id=i;
				s.insert(a[i]);
			}
		}
		else {
			int k=read();
			for(int i=1;i<=k;i++) {
				int x=read();
				int y=read();
				a[x].len=y;
			}
			s.clear();
			for (int i=1;i<=n;++i) {
				s.insert(a[i]);
			}
		}//两种输入方式
		
		while(1) {
			its ib,ie,ib2;
			ib=s.begin();
			ie=s.end();
			ie--;
			ib2=ib;
			ib2++;
			
			snakes now=(*ie);
			now.len=(*ie).len-(*ib).len;
			if(now<(*ib2)) {//模拟
				break;
			} 
			s.erase(ib);
			s.erase(ie);
			s.insert(now);
		}
		
		int ans=s.size();
		if(eatornot()) {
			ans--; //如果能吃，就在咬一口咯~
		}
		
		printf("%d\n",ans);
	}
	return 0;
}

以上是 $70pts$ 做法，现在来考虑 $100pts$ 做法。算法肯定没问题，主要是要把时间复杂度降到 $O(n)$。
我们其实可以联想到“蚯蚓”这道题，开两个队列来维护最大最小，吃完后留下的蛇的长度肯定是顺次单调递减的，很好证明，这里不再赘述。我们现在维护两个双端队列，由于有单调性，每个队列中蛇的长度单调递增，这样我们就省去了那个求最大最小值的 $O(logn)$。具体看代码。

#include<bits/stdc++.h>
using namespace std;

int read() {
	char ch=getchar();
	int f=1,x=0;
	while(ch<'0'||ch>'9') {
		if(ch=='-')
			f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') {
		x=x*10+ch-'0';
		ch=getchar();
	}
	return f*x;
}

const int maxn=1e6+10;

int n;

struct snakes {
	int id,len;
	
	bool operator <(snakes b) const {
		if(len!=b.len) {
			return len<b.len;
		}
		return id<b.id;
	}
	
	snakes operator -(snakes b) {
		snakes ret;
		ret.len=len-b.len;
		ret.id=id;
		return ret;
	}
}a[maxn];

deque<snakes> q1,q2,q;

void work() {
	q1.clear();
	q2.clear();//记得多组数据初始化
	q.clear();
	
	for (int i = 1; i <= n; ++i) {
		q1.push_back(a[i]);
	}
	
	while(1) {
		if(q1.size()+q2.size()==2) {
			printf("1\n"); //还剩下 2 条蛇直接输出
			return ;
		}
		
		snakes st=q1.front();
		q1.pop_front();
		snakes ed=q1.back();
		
		if(!q2.empty()&&ed<q2.back()) {
			ed=q2.back();
			q2.pop_back();//如果 q2 中的蛇较长，取 q2 中的蛇
		}
		else {
			q1.pop_back();
		}
		
		snakes tmp;
		tmp.len=ed.len-st.len;
		tmp.id=ed.id;
		if(q1.front()<tmp) {
			q2.push_front(tmp);
		}//将新蛇根据单调性放入队列中
		else {
			q1.push_front(tmp);
			break;
			//现在这条蛇吃了一口，发现变成最短的了
			//那么进入第二阶段
			//注意此时放到 q1 还是 q2 中没有任何区别了
		}
	}
	
	while(!q1.empty()&&!q2.empty()) {
		if(q1.front()<q2.front()) {
			q.push_back(q1.front());
			q1.pop_front();
		}
		else {
			q.push_back(q2.front());
			q2.pop_front();
		}
	}
	while(!q1.empty()) {
		q.push_back(q1.front());
		q1.pop_front();
	}
	while(!q2.empty()) {
		q.push_back(q2.front());
		q2.pop_front();
	}
	//为了操作方便把两个队列合并
	//和归并时 O(n) 合并有序数组的做法一致
	
	int ans=q.size();
	
	int eat=0;
	
	while(q.size()>1) {
		snakes st=q.front();
		q.pop_front();
		snakes ed=q.back();
		q.pop_back();
		
		snakes tmp;
		tmp.len=ed.len-st.len;
		tmp.id=ed.id;
		
		eat++;
		
		if(q.size()==0||q.front()<tmp) {
			break;
		}
		else {
			q.push_front(tmp);//还是可爱的单调性
		}
	}//用 while 模拟递归判断，本质上无差别
	
	printf("%d\n",ans+(eat&1? 1:0));
	//注意我们这份代码中和上一份有所不同
	//上面是假设还没吃，判断是否要吃 -1
	//这里是已经吃了，判断是否要吐出来 +1
} 

signed main() {	
	int t;
	t=read();
	for(int Q=1;Q<=t;Q++) {
		
		if(Q==1) {
			n=read();
			for (int i = 1; i <= n; ++i) {
				a[i].len=read();
				a[i].id=i;
			}
		}
		else {
			int k=read();
			for(int i=1;i<=k;i++) {
				int x=read();
				int y=read();
				a[x].len=y;
			}
		}
		work();//求解
	}
	return 0;
}