Search for a command to run...
Progressive hints first, then the full explanation and implementation when you're ready to cash out.
Review status
AI-generated and still unreviewed. Double-check the details before internalizing them.
Hints
Open only as much as you need to keep the solve alive.
Start by hunting for an invariant. When you replace by , what happens to the alternating sum ? Also, what happens to the parity of the length?
For length , the operation is possible iff , which is exactly . Thatβs suspiciously neat. Try guessing: maybe an array is good iff its length is odd and its alternating sum is positive.
Now prove the sufficiency. The annoying part is: can you always make some move in a positive array of odd length at least ? Look only at indices and . They cannot both be illegal, because would force nonsense.
So the whole problem collapses to counting subarrays with odd length and Define prefix alternating sums Then
Sweep from left to right over prefix indices . Let . Since the subarray length must be odd, and must have opposite parity.
So maintain two Fenwick trees (or ordered multisets): one for prefix sums at even indices, one for odd indices. After coordinate-compressing all , each query/update is .
Take the alternating sum of an array:
If we reduce a triplet then inside the global alternating sum, those three terms had signs or , and they get replaced by exactly the same signed contribution. So the alternating sum is preserved.
Also, each move decreases the length by , so the parity of the length is preserved.
That already gives a necessary condition:
So if a subarray is good, then:
Nice. But is that also sufficient? Turns out yes. And thatβs the whole damn trick.
We prove this by induction on the odd length.
Look at indices and .
If both were illegal, then
\qquad a_3 \ge a_2+a_4.$$ Substitute the first into the second: $$a_3 \ge (a_1+a_3)+a_4 > a_3,$$ which is impossible. So at least one of $i=2$ or $i=3$ is legal. In other words, for any positive array of length $\ge 5$, you can always reduce it once. ### Induction step Suppose an odd-length array has positive alternating sum. Perform any legal move guaranteed by the lemma. The new array: - is still positive (because legality means the new value is $>0$), - still has odd length, - still has the same alternating sum. So its alternating sum is still positive. By induction, the new array is good, hence the original one is good too. Therefore we get the exact characterization: $$\boxed{\text{A subarray is good iff its length is odd and its alternating sum is positive.}}$$ Thatβs the entire combinatorial part. The rest is counting. ## Observation 3: rewrite subarray alternating sums with prefix sums Define prefix alternating sums on the whole array: $$p_0=0,\qquad p_i=a_1-a_2+a_3-\dots+(-1)^{i-1}a_i.$$ For a subarray $[l,r]$, its alternating sum **starting with plus at $l$** is: $$S(l,r)=a_l-a_{l+1}+a_{l+2}-\dots+(-1)^{r-l}a_r.$$ Using $p$, this becomes: $$S(l,r)=(-1)^{l-1}(p_r-p_{l-1}).$$ We need to count pairs $(l,r)$ such that: 1. $r-l+1$ is odd, i.e. $l$ and $r$ have the same parity; 2. $S(l,r)>0$. Let $i=l-1$ and $j=r$. Then $i<j$, and odd length means $j-i$ is odd, so $i$ and $j$ have opposite parity. Now split by parity of $j$: - If $j$ is odd, then $i$ is even and $$S(l,r)=p_j-p_i,$$ so we need $$p_i<p_j.$$ - If $j$ is even, then $i$ is odd and $$S(l,r)=-(p_j-p_i)=p_i-p_j,$$ so we need $$p_i>p_j.$$ So while sweeping $j$ from left to right, we need: - for odd $j$: count previous **even** prefix indices $i$ with $p_i<p_j$; - for even $j$: count previous **odd** prefix indices $i$ with $p_i>p_j$. This is a textbook Fenwick-tree-after-compression moment. Not glamorous, but brutally effective. ## Data structure The values $p_i$ can be as large as $O(n\cdot 10^9)$, so compress them. Maintain two Fenwick trees: - `even` = counts of prefix sums $p_i$ where $i$ is even, - `odd` = counts of prefix sums $p_i$ where $i$ is odd. Initially, only $p_0=0$ is present in `even`. For each $j=1\dots n$: - let `pos = compressed(p_j)`; - if $j$ is odd, add $$\#\{i<j : i\text{ even},\ p_i<p_j\};$$ - if $j$ is even, add $$\#\{i<j : i\text{ odd},\ p_i>p_j\};$$ - then insert $p_j$ into the Fenwick tree of parity $j$. Each operation is $O(\log n)$, so total complexity is $$O(n\log n)$$ per test case, and across all tests still $$O\left(\sum n \log n\right),$$ which is easily fine for $\sum n\le 2\cdot 10^5$. ## Correctness sketch - By the invariant + induction argument, a subarray is good iff it has odd length and positive alternating sum. - The prefix-sum formula converts that condition into a comparison between $p_{l-1}$ and $p_r$, depending only on parity. - The Fenwick trees count exactly those previous prefix indices with the required parity and inequality. - Every good subarray is counted once when processing its right endpoint $r$, and no bad subarray is counted. Done. No smoke, no mirrors, just one nice invariant and a counting sweep.#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
struct Fenwick {
int n;
vector<int> bit;
Fenwick() : n(0) {}
Fenwick(int n) { init(n); }
void init(int n_) {
n = n_;
bit.assign(n + 1, 0);
}
void add(int idx, int val) {
for (; idx <= n; idx += idx & -idx) bit[idx] += val;
}
int sumPrefix(int idx) const {
int res = 0;
for (; idx > 0; idx -= idx & -idx) res += bit[idx];
return res;
}
int sumRange(int l, int r) const {
if (l > r) return 0;
return sumPrefix(r) - sumPrefix(l - 1);
}
};
int main() {
setIO();
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
vector<ll> a(n + 1), p(n + 1, 0);
for (int i = 1; i <= n; ++i) {
cin >> a[i];
p[i] = p[i - 1] + ((i & 1) ? a[i] : -a[i]);
}
vector<ll> vals = p;
sort(vals.begin(), vals.end());
vals.erase(unique(vals.begin(), vals.end()), vals.end());
auto getId = [&](ll x) {
return int(lower_bound(vals.begin(), vals.end(), x) - vals.begin()) + 1;
};
int m = (int)vals.size();
Fenwick even(m), odd(m);
ll ans = 0;
// p[0] belongs to even parity prefix index.
even.add(getId(p[0]), 1);
for (int j = 1; j <= n; ++j) {
int pos = getId(p[j]);
if (j & 1) {
// j odd: count previous even i with p[i] < p[j]
ans += even.sumPrefix(pos - 1);
odd.add(pos, 1);
} else {
// j even: count previous odd i with p[i] > p[j]
ans += odd.sumRange(pos + 1, m);
even.add(pos, 1);
}
}
cout << ans << '\n';
}
return 0;
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
struct Fenwick {
int n;
vector<int> bit;
Fenwick() : n(0) {}
Fenwick(int n) { init(n); }
void init(int n_) {
n = n_;
bit.assign(n + 1, 0);
}
void add(int idx, int val) {
for (; idx <= n; idx += idx & -idx) bit[idx] += val;
}
int sumPrefix(int idx) const {
int res = 0;
for (; idx > 0; idx -= idx & -idx) res += bit[idx];
return res;
}
int sumRange(int l, int r) const {
if (l > r) return 0;
return sumPrefix(r) - sumPrefix(l - 1);
}
};
int main() {
setIO();
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
vector<ll> a(n + 1), p(n + 1, 0);
for (int i = 1; i <= n; ++i) {
cin >> a[i];
p[i] = p[i - 1] + ((i & 1) ? a[i] : -a[i]);
}
vector<ll> vals = p;
sort(vals.begin(), vals.end());
vals.erase(unique(vals.begin(), vals.end()), vals.end());
auto getId = [&](ll x) {
return int(lower_bound(vals.begin(), vals.end(), x) - vals.begin()) + 1;
};
int m = (int)vals.size();
Fenwick even(m), odd(m);
ll ans = 0;
// p[0] belongs to even parity prefix index.
even.add(getId(p[0]), 1);
for (int j = 1; j <= n; ++j) {
int pos = getId(p[j]);
if (j & 1) {
// j odd: count previous even i with p[i] < p[j]
ans += even.sumPrefix(pos - 1);
odd.add(pos, 1);
} else {
// j even: count previous odd i with p[i] > p[j]
ans += odd.sumRange(pos + 1, m);
even.add(pos, 1);
}
}
cout << ans << '\n';
}
return 0;
}