Wannafly挑战赛10 D 小H的询问（线段树）

题目链接  Problem D

这个题类似 SPOJ GSS3

做过那个题之后其实就可以秒掉这题了。

考虑当前线段树维护的结点

在那道题的基础上，这个题要多维护几个东西，大概就是左端点的奇偶性，右端点的奇偶性。

以及当前结点代表的区间是否是一个有效的子序列。

时间复杂度$O(nlogn)$

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b)	for (int i(a); i <= (b); ++i)

#define dec(i, a, b)	for (int i(a); i >= (b); --i)

#define	ls		i << 1

#define	rs		i << 1 | 1

#define	mid		((l + r) >> 1)

#define	lson		ls, l, mid

#define	rson		rs, mid + 1, r

typedef long long LL;

const int N = 1e5 + 10;

struct node{

	LL c, lc, rc, ret;

	int lo, ro, flag;

} t[N << 2];

int n, m;

void pushup(int i){

	t[i].c = t[ls].c + t[rs].c;

	t[i].ret = max(t[ls].ret, t[rs].ret);

	t[i].flag = 0;

	t[i].lc = t[ls].lc;

	t[i].rc = t[rs].rc;

	t[i].lo = t[ls].lo;

	t[i].ro = t[rs].ro;

	if (t[ls].ro ^ t[rs].lo){

		t[i].ret = max(t[i].ret, t[ls].rc + t[rs].lc);

		if (t[ls].flag) t[i].lc = max(t[i].lc, t[ls].c + t[rs].lc);

		if (t[rs].flag) t[i].rc = max(t[i].rc, t[rs].c + t[ls].rc);

		if (t[ls].flag && t[rs].flag) t[i].flag = 1;

	}

}

void build(int i, int l, int r){

	if (l == r){

		scanf("%lld", &t[i].ret);

		t[i].c = t[i].lc = t[i].rc = t[i].ret;

		t[i].lo = t[i].ro = (t[i].ret & 1);

		t[i].flag = 1;

		return;

	}

	build(lson);

	build(rson);

	pushup(i);

}

void update(int i, int l, int r, int x, LL val){

	if (l == x && l == r){

		t[i].ret = t[i].c = t[i].lc = t[i].rc = val;

		t[i].lo = t[i].ro = (val & 1);

		t[i].flag = 1;

		return;

	}

	if (x <= mid) update(lson, x, val);

	else update(rson, x, val);

	pushup(i);

}

node query(int i, int l, int r, int L, int R){

	if (L <= l && r <= R) return t[i];

	if (R <= mid) return query(lson, L, R);

	if (L >  mid) return query(rson, L, R);

	node ta = query(lson, L, mid);

	node tb = query(rson, mid + 1, R);

	node ans;

	ans.c = ta.c + tb.c;

	ans.ret = max(ta.ret, tb.ret);

	ans.flag = 0;

	ans.lc = ta.lc;

	ans.rc = tb.rc;

	ans.lo = ta.lo;

	ans.ro = tb.ro;

	if (ta.ro ^ tb.lo){

		ans.ret = max(ans.ret, ta.rc + tb.lc);

		if (ta.flag) ans.lc = max(ans.lc, ta.c + tb.lc);

		if (tb.flag) ans.rc = max(ans.rc, tb.c + ta.rc);

		if (ta.flag && tb.flag) ans.flag = 1;

	}

	return ans;

}

int main(){

	scanf("%d%d", &n, &m);

	build(1, 1, n);

	while (m--){

		int op;

		scanf("%d", &op);

		if (op == 0){

			int x, y;

			scanf("%d%d", &x, &y);

			node ans = query(1, 1, n, x, y);

			printf("%lld\n", ans.ret);

		}

		else{

			int x;

			LL y;

			scanf("%d%lld", &x, &y);

			update(1, 1, n, x, y);

		}

	}

	return 0;

}