嗨嗨嗨

#include <bits/stdc++.h>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define ll long long
#define file
using namespace std;
struct type
{
int s,x;
} s1,s2;
struct Queue
{
type d[1000001];
int h,t;
void push(type s)
{
d[++t] = s;
}
void pop(bool tp)
{
if (!tp)
{
++h;
}
else
{
--t;
}
}
void clear()
{
h = 1,t = 0;
}
bool empty()
{
return h > t;
}
type head()
{
return d[h];
}
type tail()
{
return d[t];
}
} q[2];
int a[1000001],T,n,i,j,k,l,I,x,y,ans,I1,I2,sum;
bool operator < (type a,type b)
{
return a.s < b.s || a.s == b.s && a.x < b.x;
}
bool operator > (type a,type b)
{
return a.s > b.s || a.s == b.s && a.x > b.x;
}
void swap(int &x,int &y)
{
int z = x;x = y;y = z;
}
int main(void)
{
scanf("%d",&T);
fo(I,1,T)
{
if (I == 1)
{
scanf("%d",&n);
fo(i,1,n) scanf("%d",&a[i]);
}
else
{
scanf("%d",&k);
fo(i,1,k) scanf("%d%d",&x,&y),a[x] = y;
}
q[0].clear(),q[1].clear(),ans = n;
I1 = 0,I2 = 1;
fd(i,n,1) q[I1].push(type{a[i],i});
while (ans > 1)
{
--ans;
if (q[I2].empty() || q[I1].tail() < q[I2].tail())
{
s2 = q[I1].tail(),q[I1].pop(1);
}
else
{
s2 = q[I2].tail(),q[I2].pop(1);
}
if (!s2.s)
{
continue;
}
if (q[I2].empty() || q[I1].head() > q[I2].head())
{
s1 = q[I1].head(),q[I1].pop(0);
}
else
{
s1 = q[I2].head(),q[I2].pop(0);
}
s1.s -= s2.s;
if (q[I1].empty())
{
swap(I1,I2);
}
q[I2].push(s1);
if (q[I1].tail() > s1)
{
break;
}
}
if (ans > 1)
{
sum = 0;
while (sum < ans - 1)
{
if (q[I2].empty() || q[I1].tail() < q[I2].tail())
{
s2 = q[I1].tail(),q[I1].pop(1);
}
else
{
s2 = q[I2].tail(),q[I2].pop(1);
}
if (q[I2].empty() || q[I1].head() > q[I2].head())
{
s1 = q[I1].head(),q[I1].pop(0);
}
else
{
s1 = q[I2].head(),q[I2].pop(0);
}
s1.s -= s2.s;
if (q[I1].empty())
{
swap(I1,I2);
}
if (!q[I1].empty() && q[I1].tail() < s1 || !q[I2].empty() && q[I2].tail() < s1)
{
break;
}
q[I2].push(s1);
++sum;
}
sum += sum == (ans - 1);
ans += !(sum&1);
}
printf("%d\n",ans);
}
fclose(stdin);
fclose(stdout);
}