题目
有一个长度为(n)的01数列(a)和一个长度为(n)的数列(b)表示权值
支持单点修改以及区间查询，(0)和(1)可以看作左括号和右括号，
将一段区间所有可匹配的的括号去掉后求剩余位置的权值的最大值
分析
将这个序列看作dfs序，那显然可以将其看作一棵树，
建好树后问题就转换成树上路径查询最大值和单点修改
用两棵线段树维护上行和下行路径最大值即可，细节很多
代码
#include <cstdio>
#include <cctype>
#include <cstdlib>
#define rr register
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<13,stdin)),p1==p2?EOF:*p1++)
using namespace std;
const int N=100011;
struct node{int y,w,flag,next;}e[N]; struct rec{int x,y,flag;}P[N];
int a[2][N],A[2][N],dfn[N],as[N],tot,cnt,top[N]; char buf[1<<13],*p1,*p2;
int dep[N],fat[N],son[N],big[N],n,m,c[N],o[N],root,now,k;
inline signed iut(){
rr int ans=0; rr char c=getchar();
while (!isdigit(c)) c=getchar();
while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
return ans;
}
inline void print(int ans){
if (ans>9) print(ans/10);
putchar(ans%10+48);
}
inline void add(int x,int y,int w,int flag){e[++k]=(node){y,w,flag,as[x]},as[x]=k;}
inline signed max(int a,int b){return a>b?a:b;}
struct zkw{
int w[2][N<<2],bas;
inline void build(int n){
for (bas=1;(bas<<=1)<n+2;);
for (rr int i=bas+1;i<=bas+n;++i)
w[0][i]=a[0][i-bas],w[1][i]=a[1][i-bas];
for (rr int i=bas;i;--i)
w[0][i]=max(w[0][i<<1],w[0][i<<1|1]),
w[1][i]=max(w[1][i<<1],w[1][i<<1|1]);
}
inline void update(int z,int x,int y){
for (w[z][x+=bas]=y,x>>=1;x;x>>=1)
w[z][x]=max(w[z][x<<1],w[z][x<<1|1]);
}
inline signed query(int z,int x,int y){
rr int ans=0;
for (x+=bas-1,y+=bas+1;x^y^1;x>>=1,y>>=1){
if (!(x&1)) ans=max(ans,w[z][x^1]);
if (y&1) ans=max(ans,w[z][y^1]);
}
return ans;
}
}Tre;
inline signed Query(int x,int y){
rr int ans=0,flag=1;
for (;top[x]!=top[y];x=fat[top[x]]){
if (dep[top[x]]<dep[top[y]]) x^=y,y^=x,x^=y,flag^=1;
ans=max(ans,Tre.query(flag,dfn[top[x]],dfn[x]));
}
if (dep[x]>dep[y]) x^=y,y^=x,x^=y; else flag^=1;
if (dfn[x]<dfn[y]) ans=max(ans,Tre.query(flag,dfn[x]+1,dfn[y]));
return ans;
}
inline void dfs1(int x){
dep[x]=dep[fat[x]]+1,son[x]=1;
for (rr int i=as[x],mson=-1;i;i=e[i].next)
if (e[i].y!=fat[x]&&!dep[e[i].y]){
dfs1(e[i].y),son[x]+=son[e[i].y];
if (son[e[i].y]>mson)
big[x]=e[i].y,mson=son[e[i].y];
}
}
inline void dfs2(int x,int linp){
if (dfn[x]) return;
dfn[x]=++tot,a[0][tot]=A[0][x],
a[1][tot]=A[1][x],top[x]=linp;
if (!big[x]) return; dfs2(big[x],linp);
for (rr int i=as[x];i;i=e[i].next)
if (e[i].y!=fat[x]&&e[i].y!=big[x])
dfs2(e[i].y,e[i].y);
}
signed main(){
int size = 256 << 20;
char *p=(char*)malloc(size) + size;
__asm__("movl %0, %%esp
" :: "r"(p) );
n=iut(),m=iut(),root=now=cnt=1;
for (rr int i=1;i<=n;++i) o[i]=iut();
for (rr int i=1;i<=n;++i) c[i]=iut();
for (rr int i=1;i<=n;++i)
if (!o[i]) add(now,++cnt,c[i],0),A[0][cnt]=c[i],P[i]=(rec){now,cnt,0},fat[cnt]=now,now=cnt;
else if (now==root) add(++cnt,now,c[i],1),A[1][now]=c[i],P[i]=(rec){cnt,now,1},fat[now]=cnt,root=now=cnt;
else add(fat[now],now,c[i],1),A[1][now]=c[i],P[i]=(rec){fat[now],now,1},now=fat[now];
dfs1(root),dfs2(root,root),Tre.build(cnt);
for (;m;--m){
rr int z=iut(),x=iut(),y=iut();
if (z==1) Tre.update(P[x].flag,dfn[P[x].y],y),c[x]=y;
else{
if (x==y) {print(c[x]),putchar(10); continue;}
rr int Xx=P[x].x,Yx=P[x].y,flagx=P[x].flag;
rr int Xy=P[y].x,Yy=P[y].y,flagy=P[y].flag;
if (Yx==Yy) {putchar(48),putchar(10); continue;}
print(Query(!flagx?Xx:Yx,flagy?Xy:Yy)),putchar(10);
}
}
return 0;
}