在 $O(n\log n)$ 的贪心基础上我们发现重点就是模拟每只蛇都要吃的情况，看看谁吃谁。

然后我假定蛇的体力值单调不增（显然是错的），得到了以下代码，它可以通过 UOJ 目前的数据（而且是最短解），请问能否把它 hack 掉。

感谢！link

#include<bits/stdc++.h>
const int N=22e6;
using namespace std;
int T,n,a[N],w[N],c[N],u[N],v[N];
bool ok[N];
bool cmp(int x,int y)
{
    return w[x]==w[y]?x<y:w[x]<w[y];
}
void solve()
{
    int l=1,r=n,x=0,y=-1;
    copy(a,a+n+1,w),fill(ok,ok+n+1,0);
    for(int i=1;i<n;++i)
    {
        v[i]=(l<=r&&(x>y||cmp(l,c[y])))?l++:c[y--],
        u[i]=(l<=r&&(x>y||cmp(c[x],r)))?r--:c[x++],
        w[u[i]]-=w[v[i]],
        c[++y]=u[i];
        if(x<y)if(!cmp(c[y],c[y-1]))swap(c[y],c[y-1]);
    }
    r=0;
    for(int i=n-1;i>=1;--i)
        if(ok[u[i]])
        {
            for(int j=0;j<r;++j)
                ok[c[j]]=0;
            r=0;
        }
        else ok[v[i]]=1,c[r++]=v[i];
    cout<<n-r<<endl;
}
int main()
{
    cin>>T>>n;
    for(int i=1;i<=n;++i)cin>>a[i];
    solve();
    while(--T)
    {
        int k;cin>>k;
        for(int i=1,x,y;i<=k;++i)
            cin>>x>>y,a[x]=y;
        solve();
    }
    return 0;
}