传送门

题目背景

闪烁的光，是什么？
晶莹的水晶石板，闪烁着不同的光泽呢。
“要不，我们用这些闪光的水晶石板玩个游戏？”
“好啊，怎么玩呢？”

题目描述

现在有 $n$ 块水晶石板形成一个序列，每块水晶石板有一个权值 。
第 $i$ 块水晶石板的大小是 $a_i\times b_i$的，也就是有 $a_i\times b_i$个格子。
A和B要拿这些石板玩游戏。
每次玩游戏，A都会先选择一个区间 $[l,r]$，B只能选择这个区间的一个子区间。
对于这个子区间中的每个石板，A可以任意指定一个点作为起点，B需要从这个起点出发不重不漏地经过每一个格子并回到这个点（每次移动只能向上下左右中的一个方向），那么B可以获得这块石板的权值，否则A获得这块石板的权值。B每次都想最大化自己的得分减去A的得分。注意，B不可以选择一个空集。
现在有 $q$ 次操作，每次操作是三种之一：
$1xab$：修改第 $x$ 块水晶石板的大小为 $a\times b$
$2xw$：修改第 $x$ 块水晶石板的权值为 $w$
$3lr$：A和B玩游戏，A选择了区间$[l,r]$，B需要选择一个 $[l,r]$ 中的子区间，最大化(B的得分-A的得分)
为了避免石板的长或宽为 $1$ 时回到起始点存在问题，始终保证 $a_i>1,b_i>1$。

输入格式

第一行一个 $n$，表示石板个数。
第二行 $n$ 个数字，表示权值 $w_i$。
下面 $n$ 行每行两个数字，表示 $a_i,b_i$。
下面一行一个 $q$，表示操作次数。
下面 $q$ 行，每行为一种操作，格式见题目描述。

输出格式

对于每个询问，每行一个数表示答案。

样例输入

4
1 1 1 1
2 2
3 2
3 3
2 2
1
3 1 4

样例输出

2

数据范围与提示

对于100%的数据, $0<w\le 1000,2\le a,b\le 1000000$

测试点编号	$n$	$q$	特殊限制
1-5	$\le 5$	$\le 5$	$a_i\le 3,b_i\le 3$
6-11	$\le 1000$	$\le 1000$	$a_i\le 3,b_i\le 3$
12-17	$\le 100000$	$\le 100000$	$a_i\le 3,b_i\le 3$
18-19	$\le 1000$	$\le 1000$	无
20-25	$\le 100000$	$\le 100000$	无

题解

一道线段树板子题 我又水了一篇题解
不难看出（用手画画，可以从起点在左上角推导到所有情况，我画图不方便就不证了），只要石板的长和宽中有一个为偶数（即积为偶数），则无论起点在哪B都可以得分，否则无论起点在哪B都不能得分。
既然如此，把A得分的权设为负值，B得分的权设为正值，线段树维护最大区间子段和即可。
主要是我想给自己复习一下线段树求最大区间子段和
代码：

#include<iostream>
#include<cstdio>
#include<cmath> 
#include<cstring>
typedef long long ll;
using namespace std;
struct node{ll sum,mxl,mxr,mxv;node(){sum=mxl=mxr=mxv=0;}
}tree[400005];
int n,w[100005],a,b,q;
bool zf[100005];
void build(int nd,int l,int r){if(l==r){tree[nd].sum=w[l];tree[nd].mxl=tree[nd].mxr=tree[nd].mxv=w[l];return;}int mid=(l+r)>>1;build(nd*2,l,mid);build(nd*2+1,mid+1,r);tree[nd].sum=tree[nd*2].sum+tree[nd*2+1].sum;tree[nd].mxl=max(tree[nd*2].mxl,tree[nd*2].sum+tree[nd*2+1].mxl);tree[nd].mxr=max(tree[nd*2+1].mxr,tree[nd*2+1].sum+tree[nd*2].mxr);tree[nd].mxv=max(max(tree[nd*2].mxv,tree[nd*2+1].mxv),tree[nd*2].mxr+tree[nd*2+1].mxl);
}
void cg(int nd,int l,int r,int tar,int tarz){if(l==r){tree[nd].sum=tarz;tree[nd].mxl=tree[nd].mxr=tree[nd].mxv=tarz;return;}int mid=(l+r)>>1;if(tar<=mid) cg(nd*2,l,mid,tar,tarz);if(tar>=mid+1) cg(nd*2+1,mid+1,r,tar,tarz);tree[nd].sum=tree[nd*2].sum+tree[nd*2+1].sum;tree[nd].mxl=max(tree[nd*2].mxl,tree[nd*2].sum+tree[nd*2+1].mxl);tree[nd].mxr=max(tree[nd*2+1].mxr,tree[nd*2+1].sum+tree[nd*2].mxr);tree[nd].mxv=max(max(tree[nd*2].mxv,tree[nd*2+1].mxv),tree[nd*2].mxr+tree[nd*2+1].mxl);
}
node check(int nd,int l,int r,int L,int R){if(L<=l&&r<=R) return tree[nd];int mid=(l+r)>>1;if(R<=mid) return check(nd*2,l,mid,L,R);if(L>=mid+1) return check(nd*2+1,mid+1,r,L,R);node lft=check(nd*2,l,mid,L,R),rgt=check(nd*2+1,mid+1,r,L,R),res;res.mxl=max(lft.mxl,lft.sum+rgt.mxl);res.mxr=max(rgt.mxr,rgt.sum+lft.mxr);res.mxv=max(max(lft.mxv,rgt.mxv),lft.mxr+rgt.mxl);return res;
}
int main(){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&w[i]);} for(int i=1;i<=n;i++){scanf("%d%d",&a,&b);if((a*b)&1) zf[i]=1,w[i]=-w[i]; } build(1,1,n);scanf("%d",&q);for(int i=1;i<=q;i++){int ope;scanf("%d",&ope);if(ope==1){int x;scanf("%d%d%d",&x,&a,&b);if(((a*b)&1)&&!zf[x]) { cg(1,1,n,x,-w[x]);w[x]=-w[x];zf[x]=1; }if(!((a*b)&1)&&zf[x]) { cg(1,1,n,x,-w[x]);w[x]=-w[x];zf[x]=0; }}if(ope==2){int x,wt;scanf("%d%d",&x,&wt);if(zf[x]) cg(1,1,n,x,-wt),w[x]=-wt;else cg(1,1,n,x,wt),w[x]=wt;}if(ope==3){int L,R,ans;scanf("%d%d",&L,&R);printf("%lld\n",check(1,1,n,L,R).mxv); }} return 0;
}

Thanks!