题目概述

xay loves monotonicity

解题报告

首先我们很自然联想到楼房重建那道题，定义 $Find(p,l,r,i)$​​​ 表示在 $[l,r]$​​​ 的节点 $p$​​​ 前面放 $a_{i}$​​​ 得到的答案以及最终停止的位置（用pair存），如果 $b$​​​ 没有修改的话，单点修改 $a$​​​ 之后的维护是很容易的。

但是这道题还有区间 $01$​ 反转 $b$​ 这个操作，如果考虑在线段树上维护 $b$​​ 的值，会发现一个很严重的问题：每次查询右儿子时，左儿子最大值位置的 $b$​ 有可能还没有更新。这将导致无法顺利求出 $Find$ 。

因此我们考虑在线段树外实时更新 $b$ ，由于是区间 $01$ 反转，将 $b$ 相邻差分之后，$[L,R]$ 的区间反转就变成了 $L$ 和 $R+1$ 两个位置的单点修改，然后我们利用树状数组求出前缀和就可以实时得到 $b$ 的值。

现在考虑 $[L,R]$ 区间反转之后需要更新的信息。首先 $[L,R]$ 中的答案是不变的，因为都同时进行了反转，所以我们只要考虑 $[L,R]$ 左边和右边的情况。对于左边，我们需要更新所有包含 $L$ 的节点（ $b_L$ 改变了）。对于右边，我们需要更新所有包含 $R+1$ 的节点（ $R+1$​ 之前的位置改变了）。这样就更新完成了。

复杂度 $O(n\log_2^2n)$ ，要注意树状数组和 $Find$ 其实是独立的，因此复杂度不是 $O(n\log_2^3n)$ 。

示例程序

#include<cstdio>
#include<cctype>
#include<algorithm>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
const int maxn=200000,maxt=maxn<<2;

int te,n,a[maxn+5],b[maxn+5],c[maxn+5],lst;
int MAX[maxt+5];pair<int,int> res[maxt+5];

#define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r && (r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    lst=='-'?x=-tot:x=tot;return EOLN(ch);
}
void Add(int x,int y) {for (;x<=n;x+=x&-x) c[x]^=y;}
int Sum(int x) {int sum=0;for (;x;x-=x&-x) sum^=c[x];return sum;}
inline int Maxer(int x,int y) {return a[x]>a[y] || a[x]==a[y] && x>y?x:y;}
pair<int,int> Find(int L,int R,int p,int who){
    if (L==R) return a[L]>=a[who]?mp(Sum(L)^Sum(who),L):mp(0,who);
    int mid=L+(R-L>>1);
    if (a[who]>a[MAX[p<<1]]) return Find(mid+1,R,p<<1|1,who); else {
        pair<int,int> ls=Find(L,mid,p<<1,who);
        return mp(ls.fr+res[p].fr,res[p].sc);
    }
}
void Build(int L,int R,int p=1){
    if (L==R) {MAX[p]=L;return;}
    int mid=L+(R-L>>1);
    Build(L,mid,p<<1);Build(mid+1,R,p<<1|1);
    MAX[p]=Maxer(MAX[p<<1],MAX[p<<1|1]);
    res[p]=Find(mid+1,R,p<<1|1,MAX[p<<1]);
}
void Update(int pos,int l=1,int r=n,int p=1){
    if (l==r) return;
    int mid=l+(r-l>>1);
    pos<=mid?Update(pos,l,mid,p<<1):Update(pos,mid+1,r,p<<1|1);
    MAX[p]=Maxer(MAX[p<<1],MAX[p<<1|1]);
    res[p]=Find(mid+1,r,p<<1|1,MAX[p<<1]);
}
int Ask(int L,int R,int l=1,int r=n,int p=1){
    if (L==l && r==R){
        pair<int,int> now=Find(l,r,p,lst);lst=now.sc;
        return now.fr;
    }
    int mid=l+(r-l>>1);
    if (R<=mid) return Ask(L,R,l,mid,p<<1); else if (L>mid) return Ask(L,R,mid+1,r,p<<1|1);
    int ls=Ask(L,mid,l,mid,p<<1);
    int rs=Ask(mid+1,R,mid+1,r,p<<1|1);
    return ls+rs;
}
int main(){
    readi(n);
    for (int i=1;i<=n;i++) readi(a[i]);
    for (int i=1;i<=n;i++) readi(b[i]),Add(i,b[i]^b[i-1]);
    Build(1,n);
    for (readi(te);te;te--){
        int tp,x,y;readi(tp);readi(x);readi(y);
        if (tp==1) a[x]=y,Update(x); else
        if (tp==2){
            Add(x,1);Add(y+1,1);
            Update(x);Update(y+1);
        } else lst=x,printf("%d\n",Ask(x,y));
    }
    return 0;
}