ai题解

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>

using namespace std;

const int N = 1e6 + 10;
int T, n, a[N], w[N], q1[N], q2[N];

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 + 1 == 2) {
printf("%d\n", 1);
return;
}
if (t2 - h2 + 1 <= 0 || (t1 - h1 + 1 > 0 && cmp(q2[h2], q1[h1]))) {
v = w[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]];
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;
}
}

int main() {
T = read();
n = read();
for (int i = 1; i <= n; i++) a[i] = read();
solve();
while (T) {
int k = read();
while (k--) {
int x = read(), w = read();
a[x] = w;
}
solve();
}
return 0;
}