Retribution

申明：本题158分是对Phi定数的致敬，其真实难度并没有那么高。

考虑在线维护,显然适合容器为线段树，需要维护： l,r,ml,mr,tl,tr,lox,rox,sum,bsl,lix,rix

ml,mr: the farthest point on the left/right reachable

tl,tr: when the arrow flips, the farthest point on the left/right reachable

lox: longest chain on the left towards left 

rox: longest chain on the right towards right

lix: longest chain on the left towards right 

rix: longest chain on the right towards left 

bsl: longest chain

下面写出部分重要代码

初始化： ml,mr,tl,tr

举个栗子：1->2->3->4<-5

看到1号点，由于边是一直向右的，所以一直循环。到点4，遇到一条向左的边，停止。所以 1-4 的 mr 都是 4, 其实这时候也能知道 1-4的 tl 都是1，不过保险起见再算一下。

void init(){
    ml[1]=1;
    for(int i=2;i<=n;i++){
        int t=i;
        if(e[i-1]==1)ml[i]=i;
        else{
            while(e[i-1]==0)i++;
            for(int j=t;j<=i;j++)ml[j]=t-1;
            i--;
        }
    }
    mr[n]=n;
    for(int i=n-1;i>0;i--){
        int t=i;
        if(e[i]==0)mr[i]=i;
        else{
            while(e[i]==1)i--;
            for(int j=i;j<=t;j++)mr[j]=t+1;
            i++;
        }
    }
    tl[1]=1;
    for(int i=2;i<=n;i++){
        int t=i;
        if(e[i-1]==0)tl[i]=i;
        else{
            while(e[i-1]==1)i++;
            for(int j=t;j<=i;j++)tl[j]=t-1;
            i--;
        }
    }
    tr[n]=n;
    for(int i=n-1;i>0;i--){
        int t=i;
        if(e[i]==1)tr[i]=i;
        else{
            while(e[i]==0)i--;
            for(int j=i;j<=t;j++)tr[j]=t+1;
            i++; 
        }
    }
} 

build自己写

up，见注释

void up(int p){
    int edge=e[tree[p*2].r];//连接线段树两子树的边 
    tree[p].sum=tree[p*2].sum+tree[p*2+1].sum;//和直接相加 
    if(edge==0&&tree[p*2].lox==tree[p*2].sum)tree[p].lox=tree[p*2].sum+tree[p*2+1].lox;
    else tree[p].lox=tree[p*2].lox;
    //左边向外箭头：如果左子树箭头全部向左且连接边向左，则该点的lox为左子树的和加右子树的lox，其他四个同理 
    if(edge==1&&tree[p*2+1].rox==tree[p*2+1].sum)tree[p].rox=tree[p*2].rox+tree[p*2+1].sum;
    else tree[p].rox=tree[p*2+1].rox;
    if(edge==1&&tree[p*2].lix==tree[p*2].sum)tree[p].lix=tree[p*2].sum+tree[p*2+1].lix;
    else tree[p].lix=tree[p*2].lix;
    if(edge==0&&tree[p*2+1].rix==tree[p*2+1].sum)tree[p].rix=tree[p*2].rix+tree[p*2+1].sum;
    else tree[p].rix=tree[p*2+1].rix;
    tree[p].bsl=max(tree[p*2].bsl,tree[p*2+1].bsl);
    if(edge==1)tree[p].bsl=max(tree[p].bsl,tree[p*2].rox+tree[p*2+1].lix);
    if(edge==0)tree[p].bsl=max(tree[p].bsl,tree[p*2].rix+tree[p*2+1].lox);
    //最长链: 左子树最长链，右子树最长链，连接起来的最长链取max 
}

剩下四个操作中

2操作是普通的单点修改

3操作是直接输出 tree_1 的最长链

4操作查询这个点的 ml,mr 并区间求和

下面最最复杂的1操作

如图，以翻转 x 到 x+1 的一条向右边为例，若它的左侧是一段向右的链，则要将 mr_a 到 mr_x 更新为, 否则将 tr_a 到 tr_x 更新为 b , 实际实现的时候可以两个同时更新。其他同理。

void update1(int x,int p){
    int mid=tree[p].l+tree[p].r>>1;
    if(mid==x){
        if(e[x]==1){
            int ml=fml(x,1),mr=fmr(x+1,1),tl=ftl(x,1),tr=ftr(x+1,1);
            cmr(tl,x,x,1);
            ctl(x+1,mr,x+1,1);
            ctr(ml,x,tr,1);
            cml(x+1,tr,ml,1);
            //fml 代表 find_ml，cml 代表 change_ml
        }
        else{
            int ml=fml(x,1),mr=fmr(x+1,1),tl=ftl(x,1),tr=ftr(x+1,1);
            cml(x+1,tr,x+1,1);
            ctr(ml,x,x,1);
            ctl(x+1,mr,tl,1);
            cmr(tl,x,mr,1);
        }
        e[x]=1-e[x];
        up(p);
        //l belongs to x while r belongs to x+1
        return;
    }
    else if(mid>x)update1(x,p*2);
    else update1(x,p*2+1);
    up(p);
}

还不懂就看std吧，相信你一定能写的更好。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MX=1e5+5;
int n,a[MX],e[MX],ml[MX],mr[MX],tl[MX],tr[MX],q;
struct node{
    int l,r,ml,mr,tl,tr,lox,rox,sum,bsl,lix,rix;
    // ml,mr: the farthest point on the left/right reachable
    // tl,tr: when the arrow flips, the farthest point on the left/right reachable （即最远的能到达该点的点） 
    // lox: longest chain on the left towards left 
    // rox: longest chain on the right towards right
    // lix: longest chain on the left towards right 
    // rix: longest chain on the right towards left 
    // bsl: longest chain
}tree[MX*4]; 
void init(){
    ml[1]=1;
    for(int i=2;i<=n;i++){
        int t=i;
        if(e[i-1]==1)ml[i]=i;
        else{
            while(e[i-1]==0)i++;
            for(int j=t;j<=i;j++)ml[j]=t-1;
            i--;
        }
    }
    mr[n]=n;
    for(int i=n-1;i>0;i--){
        int t=i;
        if(e[i]==0)mr[i]=i;
        else{
            while(e[i]==1)i--;
            for(int j=i;j<=t;j++)mr[j]=t+1;
            i++;
        }
    }
    tl[1]=1;
    for(int i=2;i<=n;i++){
        int t=i;
        if(e[i-1]==0)tl[i]=i;
        else{
            while(e[i-1]==1)i++;
            for(int j=t;j<=i;j++)tl[j]=t-1;
            i--;
        }
    }
    tr[n]=n;
    for(int i=n-1;i>0;i--){
        int t=i;
        if(e[i]==1)tr[i]=i;
        else{
            while(e[i]==0)i--;
            for(int j=i;j<=t;j++)tr[j]=t+1;
            i++; 
        }
    }
} 
void up(int p){
    int edge=e[tree[p*2].r];//连接线段树两子树的边 
    tree[p].sum=tree[p*2].sum+tree[p*2+1].sum;//和直接相加 
    if(edge==0&&tree[p*2].lox==tree[p*2].sum)tree[p].lox=tree[p*2].sum+tree[p*2+1].lox;
    else tree[p].lox=tree[p*2].lox;
    //左边向外箭头：如果左子树箭头全部向左且连接边向左，则该点的lox为左子树的和加右子树的lox，其他四个同理 
    if(edge==1&&tree[p*2+1].rox==tree[p*2+1].sum)tree[p].rox=tree[p*2].rox+tree[p*2+1].sum;
    else tree[p].rox=tree[p*2+1].rox;
    if(edge==1&&tree[p*2].lix==tree[p*2].sum)tree[p].lix=tree[p*2].sum+tree[p*2+1].lix;
    else tree[p].lix=tree[p*2].lix;
    if(edge==0&&tree[p*2+1].rix==tree[p*2+1].sum)tree[p].rix=tree[p*2].rix+tree[p*2+1].sum;
    else tree[p].rix=tree[p*2+1].rix;
    tree[p].bsl=max(tree[p*2].bsl,tree[p*2+1].bsl);
    if(edge==1)tree[p].bsl=max(tree[p].bsl,tree[p*2].rox+tree[p*2+1].lix);
    if(edge==0)tree[p].bsl=max(tree[p].bsl,tree[p*2].rix+tree[p*2+1].lox);
    //最长链: 左子树最长链，右子树最长链，连接起来的最长链取max 
}
void build(int l,int r,int p){
    tree[p].l=l,tree[p].r=r;
    if(l==r){
        tree[p].ml=ml[l];
        tree[p].mr=mr[l];
        tree[p].tl=tl[l];
        tree[p].tr=tr[l];
        tree[p].sum=tree[p].lox=tree[p].rox=tree[p].lix=tree[p].rix=a[l]=tree[p].bsl=a[l];
        return;
    }
    int mid=l+r>>1;
    build(l,mid,p*2);
    build(mid+1,r,p*2+1);
    up(p);
}
void down(int p){
    if(tree[p].ml)tree[p*2].ml=tree[p*2+1].ml=tree[p].ml;
    if(tree[p].mr)tree[p*2].mr=tree[p*2+1].mr=tree[p].mr;
    if(tree[p].tl)tree[p*2].tl=tree[p*2+1].tl=tree[p].tl;
    if(tree[p].tr)tree[p*2].tr=tree[p*2+1].tr=tree[p].tr;
    tree[p].ml=tree[p].mr=tree[p].tl=tree[p].tr=0;
}
void cml(int l,int r,int x,int p){
    if(tree[p].l==l&&tree[p].r==r){
        tree[p].ml=x;
        return;
    }
    down(p);
    int mid=tree[p].l+tree[p].r>>1;
    if(r<=mid)cml(l,r,x,p*2);
    else if(l>mid)cml(l,r,x,p*2+1);
    else cml(l,mid,x,p*2),cml(mid+1,r,x,p*2+1);
}
void cmr(int l,int r,int x,int p){
    if(tree[p].l==l&&tree[p].r==r){
        tree[p].mr=x;
        return;
    }
    down(p);
    int mid=tree[p].l+tree[p].r>>1;
    if(r<=mid)cmr(l,r,x,p*2);
    else if(l>mid)cmr(l,r,x,p*2+1);
    else cmr(l,mid,x,p*2),cmr(mid+1,r,x,p*2+1);
}
void ctl(int l,int r,int x,int p){
    if(tree[p].l==l&&tree[p].r==r){
        tree[p].tl=x;
        return;
    }
    down(p);
    int mid=tree[p].l+tree[p].r>>1;
    if(r<=mid)ctl(l,r,x,p*2);
    else if(l>mid)ctl(l,r,x,p*2+1);
    else ctl(l,mid,x,p*2),ctl(mid+1,r,x,p*2+1);
}
void ctr(int l,int r,int x,int p){
    if(tree[p].l==l&&tree[p].r==r){
        tree[p].tr=x;
        return;
    }
    down(p);
    int mid=tree[p].l+tree[p].r>>1;
    if(r<=mid)ctr(l,r,x,p*2);
    else if(l>mid)ctr(l,r,x,p*2+1);
    else ctr(l,mid,x,p*2),ctr(mid+1,r,x,p*2+1);
}
int fml(int l,int p){
    if(tree[p].ml)return tree[p].ml;
    int mid=tree[p].l+tree[p].r>>1;
    if(l<=mid)return fml(l,p*2);
    else return fml(l,p*2+1);
}
int fmr(int l,int p){
    if(tree[p].mr)return tree[p].mr;
    int mid=tree[p].l+tree[p].r>>1;
    if(l<=mid)return fmr(l,p*2);
    else return fmr(l,p*2+1);
}
int ftl(int l,int p){
    if(tree[p].tl)return tree[p].tl;
    int mid=tree[p].l+tree[p].r>>1;
    if(l<=mid)return ftl(l,p*2);
    else return ftl(l,p*2+1);
}
int ftr(int l,int p){
    if(tree[p].tr)return tree[p].tr;
    int mid=tree[p].l+tree[p].r>>1;
    if(l<=mid)return ftr(l,p*2);
    else return ftr(l,p*2+1);
}
void update1(int x,int p){
    int mid=tree[p].l+tree[p].r>>1;
    if(mid==x){
        if(e[x]==1){
            int ml=fml(x,1),mr=fmr(x+1,1),tl=ftl(x,1),tr=ftr(x+1,1);
            cmr(tl,x,x,1);
            ctl(x+1,mr,x+1,1);
            ctr(ml,x,tr,1);
            cml(x+1,tr,ml,1);
            //fml 代表 find_ml, cml 代表 change_ml 
        }
        else{
            int ml=fml(x,1),mr=fmr(x+1,1),tl=ftl(x,1),tr=ftr(x+1,1);
            cml(x+1,tr,x+1,1);
            ctr(ml,x,x,1);
            ctl(x+1,mr,tl,1);
            cmr(tl,x,mr,1);
        }
        e[x]=1-e[x];
        up(p);
        //l belongs to x while r belongs to x+1
        return;
    }
    else if(mid>x)update1(x,p*2);
    else update1(x,p*2+1);
    up(p);
}
void update2(int l,int x,int p){
    if(tree[p].l==tree[p].r){
        tree[p].sum=tree[p].lox=tree[p].rox=tree[p].lix=tree[p].rix=a[l]=tree[p].bsl=x;
        return;
    }
    int mid=tree[p].l+tree[p].r>>1;
    if(l<=mid)update2(l,x,p*2);
    else update2(l,x,p*2+1);
    up(p);
}
int querysum(int l,int r,int p){ 
    if(tree[p].l==l&&tree[p].r==r)return tree[p].sum;
    int mid=tree[p].l+tree[p].r>>1;
    if(r<=mid)return querysum(l,r,p*2);
    else if(l>mid)return querysum(l,r,p*2+1);
    else return querysum(l,mid,p*2)+querysum(mid+1,r,p*2+1);
}
signed main(){
//  freopen("11.in","r",stdin);
//  freopen("11.out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<n;i++)cin>>e[i];
    e[0]=e[n]=-1; 
    init();
    build(1,n,1);
    cin>>q;
    while(q--){
        int opt,x,y;
        cin>>opt;
        if(opt==1){
            cin>>x;
            update1(x,1);
        }
        if(opt==2){
            cin>>x>>y;
            update2(x,y,1);
        }
        if(opt==3)cout<<tree[1].bsl<<endl;
        if(opt==4){
            cin>>x;
            int ml=fml(x,1),mr=fmr(x,1);
            cout<<querysum(ml,mr,1)<<endl;
        }
    } 
    return 0;
}