题解

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
using namespace std;
const int KL=1e6+10;
int T,n,a[KL],w[KL],q1[KL],q2[KL];
int read()
{
int x=0,f=1;char c=getchar();
while(!isdigit(c))
{
if(c=='-')f=-f;c=getchar();
}
while(isdigit(c))
{
x=(x<<1)+(x<<3)+c-'0';c=getchar();
}
return x*f;
}
bool cmp(int x,int y)
{
return (w[x]w[y])?x<y:w[x]<w[y];
}
void solve()
{
int h1=1,t1=n,h2=1,t2=0,v,p;T--;
for(int i=1;i<=n;i++)w[q1[n-i+1]=i]=a[i];
while(1)
{
if(t1-h1+1+t2-h2+12)
{
printf("%d\n",1);return;
}
if(t2-h2+1<=0||t1-h1+1>0&&cmp(q2[h2],q1[h1]))
{
v=w[p=q1[h1]];p=q1[h1];h1++;
if(t2-h2+1<=0||t1-h1+1>0&&cmp(q1[t1],q2[t2]))v-=w[q1[t1]],t1--;
else v-=w[q2[t2]],t2--;
}
else
{
v=w[p=q2[h2]];h2++;
if(t2-h2+1<=0||t1-h1+1>0&&cmp(q1[t1],q2[t2]))v-=w[q1[t1]],t1--;
else v-=w[q2[t2]],t2--;
}
w[p]=v;
if((t2-h2+1<=0||cmp(p,q2[t2]))&&(t1-h1+1<=0||cmp(p,q1[t1])))
{
q2[t2]=p;break;
}
q2[t2]=p;
}
int cnt=0,f=t2-h2+1+t1-h1+1;
while(1)
{
cnt;
if(t1-h1+1+t2-h2+1==2)
{
printf("%d\n",f+(cnt&1));return;
}
if(t2-h2+1<=0||t1-h1+1>0&&cmp(q2[h2],q1[h1]))
{
v=w[p=q1[h1]];p=q1[h1];h1;
if(t2-h2+1<=0||t1-h1+1>0&&cmp(q1[t1],q2[t2]))v-=w[q1[t1]],t1--;
else v-=w[q2[t2]],t2--;
}
else
{
v=w[p=q2[h2]];h2++;
if(t2-h2+1<=0||t1-h1+1>0&&cmp(q1[t1],q2[t2]))v-=w[q1[t1]],t1--;
else v-=w[q2[t2]],t2--;
}
w[p]=v;
if((t2-h2+1<=0||cmp(p,q2[t2]))&&(t1-h1+1<=0||cmp(p,q1[t1])))
{
q2[t2]=p;continue;
}
printf("%d\n",f+(cnt&1));return;
}
return;
}
int main()
{
T=read();n=read();
for(int cc=1;cc<=n;cc)a[cc]=read();
solve();
while(T)
{
int k=read();
while(k--)
{
int x=read(),w=read();
a[x]=w;
}
solve();
}
return 0;
}