题解（A725.贪吃蛇）

C版：
//FJ-00445
//NOIP2020 RP
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
const int N=1e6+100,INF=1e9;
struct Node
{
int val,num;
#define val(i) a[i].val
#define num(i) a[i].num
bool operator < (const Node y)
{
return valy.val?num<y.num:val<y.val;
}
bool operator == (const Node y)
{
return valy.val && numy.num;
}
}a[N];
int T,n,k,ph,pb;
queue<Node> q;
Node blank={0,0},black={INF,INF};
Node Max(Node x,Node y)
{
return (x<y)?y:x;
}
Node Min(Node x,Node y)
{
return (x<y)?x:y;
}
bool query(Node la)//传入上一次操作后的元素
{
int cnt=0;
Node bk=Min(pb<ph?a[pb+1]:black,q.size()?q.back():black);//次小元素
while(1)
{
Node hd=Max(pb<ph?a[ph]:blank,q.size()?q.front():blank);//最大元素
if(a[ph]hd)
ph--;
else
if(q.size())
q.pop();//维护指针和队列
if(hdbk)
break;//只剩两个元素，即次小元素与最大元素相等
hd.val-=la.val;
if(bk<hd)
break;//当前最大的元素操作后不是最小的元素
la=hd;cnt++;//维护指针
}
return cnt&1;//在第 x 次操作终止，返回 x-1 的奇偶性
}
int main()
{
scanf("%d",&T);
for(int i=1;i<=T;i++)
{
if(i1)
{
scanf("%d",&n);
for(int j=1;j<=n;j++)
scanf("%d",&val(j)),num(j)=j;
}
else
{
scanf("%d",&k);
for(int j=1,x,y;j<=k;j++)
{
scanf("%d%d",&x,&y);
val(x)=y;
}
}
ph=n,pb=1;//分别为原序列最大元素和最小元素的指针
while(q.size())
q.pop();
while(pb<=ph)
{
Node x=Max((ph>pb)?a[ph]:blank,q.size()?q.front():blank);//最大元素
if(a[ph]==x)
ph--;
else
q.pop();//维护指针和队列
x.val-=val(pb);
if(x<a[pb+1] && n-pb>1)//当前最大的元素操作后是最小的元素且剩下的元素不止一个
{
if(query(x))//求解是否进行本次操作
pb++;
break;
}
q.push(x);pb++;//维护指针和队列
}
printf("%d\n",n-pb+1);
}
return 0;
}