P7707 百花齐放的太阳花田：爆标

· · 题解

一些碎碎念

几个月前赛时匆忙写出的代码码量达到了 \text{3.2K}，最近对那份代码进行了一些精简，重构之后码量减少了 \text{1K}，而且去掉了很多冗余的变量和步骤。

下面介绍一种两枚 \log 的做法。这种做法不仅思维、代码难度都很低（比 std 短得多），而且跑得很快（俩 \log 碾标算）。最重要的是完全不会被卡空间（比如就不用 std 的神必 short 卡空间技巧）。

本场比赛应该只有这个 Subtask 算是卡常的

哈哈。

其实赛时墨染空同志写的就是这种做法（见囧女士题解评论区），但是他惨遭 MLE 打击……或许是没有用指针优化空间的缘故？

解法

不知道大家有没有做过 向量集 这道题目。那道题目同样是强制在线末尾插入、区间查询，我们使用线段树来维护凸包。具体地，当向树上某个节点中插入信息时，我们将该信息暂时搁置。等到一个节点被插满之后，我们使用归并排序思想将其对应的凸包建出。

这种思想完全可以套用至本题中。同样是将某个节点插满之后统计子节点的区间信息，下面我们考虑如何较为完整地记录当前节点的信息，并对来自子区间的信息进行合并。

对于信息的记录，如果去掉高度范围的限制，区间颜色段数是一个经典问题，两个区间信息的合并可以 O(1) 完成。现在加上了高度范围的限制，我们不得不保存将节点中的每一个对象作为限度时的答案。具体地，在经典区间颜色段数问题中，我们对每一个区间维护了三个量：cnt,lc,rc，分别表示颜色段数和两端点颜色。在本题中，我们需要对区间 [l,r] 维护 (r-l+1) 个四元组 \{h,cnt,lc,rc\}，h 表示限制的最大高度，其他三个量同经典问题。

合并方式类似向量集一题，考虑对子区间维护的所有信息进行归并。归并过程中，不断寻找两个子节点中记录的 h 中较小的一方，并在另一个子节点中找出 h 不高于当前信息的最大四元组，对这两个区间信息进行 O(1) 合并即可。

如何处理查询？同样套用向量集的做法，对于每一次查询，我们在 O(\log n) 个区间中进行二分，并同样用处理经典区间颜色段数问题的方式合并区间信息。

对于信息的保存，用 \text{vector} 当然是可以的，但是听说会卡空间，所以我采用了另一种（可能会更优秀的）存储方式：开一个大数组存下整棵树上所有节点的信息，并用指针存下每个节点信息在大数组上对应的位置。

至此，本题得到完美解决。

代码：

struct ret{
    int mx,cnt,lc,rc;
    ret(){lc=rc=cnt=0;}
    ret(int mm,int cc,int ll,int rr){mx=mm;cnt=cc;lc=ll;rc=rr;}
    ret operator +(const ret b){
        if(!cnt)return b;
        if(!b.cnt)return *this;
        return ret(Max(mx,b.mx),cnt+b.cnt-(rc==b.lc),lc,b.rc);
    }
    bool operator <=(const ret b)const{return mx<=b.mx;}
    bool operator <(const int x)const{return mx<x;}
};
bool operator <(const int x,const ret y){return x<y.mx;}
bool change(int k,int l,int r,int x,int y,int h){
    if(l==r){
        info[k]=inp;inp++;info[k][0]=ret(h,1,y,y);//inp和info为上文提到过的索引指针
        return true;
    }
    int mid=(l+r)>>1;
    if(x<=mid)change(k<<1,l,mid,x,y,h);
    else change(k<<1|1,mid+1,r,x,y,h);
    if(x!=r)return true;
    int l1=mid-l+1,l2=r-mid;int i=0,j=0,np=0;
    info[k]=inp;inp+=(r-l+1);
    while(i<l1||j<l2){
        if((info[k<<1][i]<=info[k<<1|1][j]&&i<l1&&j<l2)||j>=l2){
            info[k][np]=info[k<<1][i]+(j==0?ret():info[k<<1|1][j-1]);
            i++;np++;
        }
        else{
            info[k][np]=(i==0?ret():info[k<<1][i-1])+info[k<<1|1][j];
            j++;np++;
        }
    }
    return true;
}
ret ask(int k,int l,int r,int x,int y,int h){
    if(l>=x&&r<=y){
        if(info[k][0].mx>h)return ret();
        int pos=std::upper_bound(info[k],info[k]+r-l+1,h)-info[k]-1;
        return info[k][pos];
    }
    int mid=(l+r)>>1;
    if(y<=mid)return ask(k<<1,l,mid,x,y,h);
    if(mid<x)return ask(k<<1|1,mid+1,r,x,y,h);
    ret xx=ask(k<<1,l,mid,x,y,h)+ask(k<<1|1,mid+1,r,x,y,h);
    return xx;
}
int main(){
    n=read();m=read();len=n+m;int k=read();inp=ii;//ii为上文提到过的大数组
    for(int i=1;i<=n;i++)ta[i]=read();
    for(int i=1;i<=n;i++)change(1,1,len,i,read(),ta[i]);
    for(int i=1;i<=m;i++){
        int opt=read();
        if(opt&1){
            int l=read()^(k*lans);int r=read()^(k*lans);int x=read()^(k*lans);
            ret ans=ask(1,1,len,l,r,x);
            printf("%d\n",lans=ans.cnt);
        }
        else{
            int h=read()^(k*lans);int y=read()^(k*lans);
            change(1,1,len,++n,y,h);
        }
    }
}