Magician-区间查询与合并问题

### 题目描述 给定一个区间，支持两种操作： 1. 将位置a的值修改为b。 2. 查询区间[a, b]内的子序列的最大和，其中子序列中相邻的元素必须具有不同的奇偶性。 ### 解题思路 由于子序列中相邻元素的奇偶性不同，因此可以将每个区间分解为四种情况：奇-奇（jj）、奇-偶（jo）、偶-奇（oj）、偶-偶（oo）。通过维护这四种情况，可以在区间合并时进行有效的计算。 在实现过程中，需要注意的是查询时不能直接返回四种情况中的最大值，因为查询的区间可能被分为左右两部分，需要进行合并操作才能得到正确的结果。 ### 代码实现 ```cpp #include #include #include #include using namespace std; #define lson r<<1 #define rson r<<1|1 const int maxn = 100005; const int INF = 1e9 + 7; struct node { int L, R; long long jj, jo, oj, oo; int Mid() { return (L + R) >> 1; } } a[maxn * 4]; long long val[maxn]; struct even_odd { long long jj, oo, jo, oj; }; void pushUp(int r) { a[r].jj = max(a[lson].jj, max(a[rson].jj, max(a[lson].jj + a[rson].oj, a[lson].jo + a[rson].jj))); a[r].oo = max(a[lson].oo, max(a[rson].oo, max(a[lson].oo + a[rson].jo, a[lson].oj + a[rson].oo))); a[r].jo = max(a[lson].jo, max(a[rson].jo, max(a[lson].jj + a[rson].oo, a[lson].jo + a[rson].jo))); a[r].oj = max(a[lson].oj, max(a[rson].oj, max(a[lson].oo + a[rson].jj, a[lson].oj + a[rson].oj))); } void Build(int r, int L, int R) { a[r].L = L, a[r].R = R; a[r].jj = a[r].jo = a[r].oj = a[r].oo = -INF; if (L == R) { if (L % 2 == 0) a[r].oo = val[L]; else a[r].jj = val[L]; return; } Build(lson, L, a[r].Mid()); Build(rson, a[r].Mid() + 1, R); pushUp(r); } void upDate(int r, int k, long long e) { if (a[r].L == a[r].R) { if (k % 2 == 0) { a[r].oo = e; a[r].jj = a[r].oj = a[r].jo = -INF; } else { a[r].jj = e; a[r].oo = a[r].oj = a[r].jo = -INF; } return; } if (k <= a[r].Mid()) upDate(lson, k, e); else upDate(rson, k, e); pushUp(r); } even_odd Query(int r, int L, int R) { if (a[r].L == L && a[r].R == R) { even_odd s; s.jj = a[r].jj, s.oo = a[r].oo, s.jo = a[r].jo, s.oj = a[r].oj; return s; } if (R <= a[r].Mid()) return Query(lson, L, R); else if (L > a[r].Mid()) return Query(rson, L, R); else { even_odd ls = Query(lson, L, a[r].Mid()); even_odd rs = Query(rson, a[r].Mid() + 1, R); even_odd s; s.jj = max(ls.jj, max(rs.jj, max(ls.jj + rs.oj, ls.jo + rs.jj))); s.oo = max(ls.oo, max(rs.oo, max(ls.oo + rs.jo, ls.oj + rs.oo))); s.jo = max(ls.jo, max(rs.jo, max(ls.jj + rs.oo, ls.jo + rs.jo))); s.oj = max(ls.oj, max(rs.oj, max(ls.oo + rs.jj, ls.oj + rs.oj))); return s; } } int main() { int i, T; scanf("%d", &T); while (T--) { int N, M, op, x, y; even_odd s; scanf("%d%d", &N, &M); for (i = 1; i <= N; i++) scanf("%lld", &val[i]); Build(1, 1, N); while (M--) { scanf("%d%d%d", &op, &x, &y); if (op == 0) { s = Query(1, x, y); printf("%lld\n", max(s.jj, max(s.oo, max(s.oj, s.jo)))); } else upDate(1, x, y); } } return 0; } ```