题目概述

Cut

解题报告

这题思路是不难的，但是如果没写过类似的就会巨难写（细节比较多）……

把 $[l,r]$ 内的排序其实就是认为 $[l,r]$ 这一块按照权值线段树的顺序进行排列（正序或者倒序），那么每次做完 $[l,r]$ 之后我们就可以用一颗权值线段树来表示这个区间。因此我们可以把整个数组划分为许多权值线段树。

每次排序时，把两边不是整块的区间进行线段树分裂，将需要的区间拆出来，然后把 $[l,r]$ 内所有的权值线段树进行合并。

然后考虑怎么维护这个奇偶交替，根据套路定义 $f_{0/1,0/1}$ 表示 $0/1$ 开头 $0/1$ 结尾的最长序列，以及 $g_{0/1,0/1}$ 表示倒过来考虑时的情况。这样当正序和倒序互相转换时只需要打翻转标记，并交换左右儿子以及 $f$ 和 $g$ 即可。

查询时，由于完全在 $[l,r]$ 中的块答案是已经确定的，因此我们可以在每次更新块的时候就把整个块的贡献记录在左端点上，并维护一棵全局位置线段树，记录块头的 $f$ 数组。这样查询 $[l,r]$ 时完全在区间内的块可以直接通过全局线段树查询，然后边上两个不完全的块，在权值线段树中进行区间查询即可。

分析下复杂度，排序时最多会分裂出两个块，分裂复杂度为 $O(m\log_2n)$ ，所以可以认为所有情况下的块数为 $O(n+m)$ ，则合并复杂度为 $O((n+m)\log_2n)$ ，查询复杂度为 $O(m\log_2n)$ 。因此总复杂度 $O((n+m)\log_2n)$ 。

示例程序

#include<map>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
const int maxn=100000,maxt=5.5e6;

int n,m;
int MAX[(maxn<<2)+5][2][2],res[2][2];
int pl,ls[maxt+5],rs[maxt+5],si[maxt+5],f[maxt+5][2][2][2];bool flip[maxt+5];
int ro[maxn+5];bool vis[maxn+5]; // 0 inc 1 dec
map<int,int> S;map<int,int>::iterator l,r,it;

inline void Clear(int f[2][2]) {f[0][0]=f[0][1]=f[1][0]=f[1][1]=-1e9;}
inline int newnode(){
    int x=++pl;ls[x]=rs[x]=si[x]=0;flip[x]=0;
    Clear(f[x][0]);Clear(f[x][1]);
    return x;
}
void Fix(int f[2][2],int A[2][2],int B[2][2],int tp){
    static int tem[2][2];
    if (tp){
        tem[0][0]=max({A[0][0],B[0][0],B[0][0]+A[1][0],B[0][1]+A[0][0]});
        tem[0][1]=max({A[0][1],B[0][1],B[0][0]+A[1][1],B[0][1]+A[0][1]});
        tem[1][0]=max({A[1][0],B[1][0],B[1][0]+A[1][0],B[1][1]+A[0][0]});
        tem[1][1]=max({A[1][1],B[1][1],B[1][0]+A[1][1],B[1][1]+A[0][1]});
    } else {
        tem[0][0]=max({A[0][0],B[0][0],A[0][0]+B[1][0],A[0][1]+B[0][0]});
        tem[0][1]=max({A[0][1],B[0][1],A[0][0]+B[1][1],A[0][1]+B[0][1]});
        tem[1][0]=max({A[1][0],B[1][0],A[1][0]+B[1][0],A[1][1]+B[0][0]});
        tem[1][1]=max({A[1][1],B[1][1],A[1][0]+B[1][1],A[1][1]+B[0][1]});
    }
    f[0][0]=tem[0][0];f[0][1]=tem[0][1];
    f[1][0]=tem[1][0];f[1][1]=tem[1][1];
}
inline void Pushup(int p){
    si[p]=si[ls[p]]+si[rs[p]];
    Fix(f[p][0],f[ls[p]][0],f[rs[p]][0],0);
    Fix(f[p][1],f[ls[p]][1],f[rs[p]][1],1);
}
void Insert(int &p,int pos,int l=1,int r=n){
    if (!p) p=newnode();
    if (l==r) {si[p]++;f[p][0][l&1][l&1]=f[p][1][l&1][l&1]=1;return;}
    int mid=l+(r-l>>1);
    pos<=mid?Insert(ls[p],pos,l,mid):Insert(rs[p],pos,mid+1,r);
    Pushup(p);
}
void Update(int pos,int id,int l=1,int r=n,int p=1){
    if (l==r) {memcpy(MAX[p],f[id][0],sizeof(MAX[p]));return;}
    int mid=l+(r-l>>1);
    pos<=mid?Update(pos,id,l,mid,p<<1):Update(pos,id,mid+1,r,p<<1|1);
    Fix(MAX[p],MAX[p<<1],MAX[p<<1|1],0);
}
void Ask(int L,int R,int l=1,int r=n,int p=1){
    if (L==l && r==R) return Fix(res,res,MAX[p],0);
    int mid=l+(r-l>>1);
    if (R<=mid) Ask(L,R,l,mid,p<<1); else if (L>mid) Ask(L,R,mid+1,r,p<<1|1);
    else Ask(L,mid,l,mid,p<<1),Ask(mid+1,R,mid+1,r,p<<1|1);
}
inline void Addflip(int p) {if (p) swap(ls[p],rs[p]),swap(f[p][0],f[p][1]),flip[p]^=1;}
void Pushdown(int p) {if (flip[p]) Addflip(ls[p]),Addflip(rs[p]),flip[p]=0;}
void SplitR(int &p,int q,int k){
    if (!p) p=newnode();
    Pushdown(q);
    int now=si[rs[q]];
    if (k>=now){
        rs[p]=rs[q];rs[q]=0;
        if (k-=now) SplitR(ls[p],ls[q],k);
    } else SplitR(rs[p],rs[q],k);
    Pushup(p);Pushup(q);
}
void Split(int fr,int sc,int L,int R,int tp){
    if (R<sc){
        ro[R+1]=0;SplitR(ro[R+1],ro[fr],sc-R);
        vis[R+1]=vis[fr];
        S[fr]=R;Update(fr,ro[fr]);
        S[R+1]=sc;Update(R+1,ro[R+1]);
    }
    if (L>fr){
        ro[L]=0;SplitR(ro[L],ro[fr],R-L+1);
        vis[L]=vis[fr];
        S[fr]=L-1;Update(fr,ro[fr]);
        S[L]=R;Update(L,ro[L]);
    }
    if (vis[L]!=tp) Addflip(ro[L]),vis[L]=tp,Update(L,ro[L]);
}
void Merge(int &x,int y,int l=1,int r=n){
    if (!y) return;if (!x) {x=y;return;}
    Pushdown(x);Pushdown(y);
    int mid=l+(r-l>>1);
    Merge(ls[x],ls[y],l,mid);Merge(rs[x],rs[y],mid+1,r);
    Pushup(x);
}
void AskLR(int p,int L,int R){
    if (!p) return;
    if (L==1 && R==si[p]) return Fix(res,res,f[p][0],0);
    Pushdown(p);
    int now=si[ls[p]];
    if (R<=now) AskLR(ls[p],L,R); else if (L>now) AskLR(rs[p],L-now,R-now);
    else AskLR(ls[p],L,now),AskLR(rs[p],1,R-now);
}
int Max(int f[2][2]) {return max({f[0][0],f[0][1],f[1][0],f[1][1]});}
int main(){
    Clear(f[0][0]);Clear(f[0][1]);
    scanf("%d%d",&n,&m);
    for (int i=1,x;i<=n;i++) scanf("%d",&x),Insert(ro[i],x),Update(i,ro[i]);
    for (int i=1;i<=n;i++) S[i]=i;
    for (int t=1,tp,L,R;t<=m;t++){
        scanf("%d%d%d",&tp,&L,&R);tp--;
        if (tp<2){
            l=prev(S.upper_bound(L));r=prev(S.upper_bound(R));
            int A=l->fr,B=l->sc,C=r->fr,D=r->sc;
            if (A==C) Split(A,B,L,R,tp); else{
                Split(A,B,L,B,tp);
                Split(C,D,C,R,tp);
                for (it=S.lower_bound(L+1);it!=S.end() && it->sc<=R;it=S.erase(it)){
                    if (vis[it->fr]!=tp) Addflip(ro[it->fr]);
                    Merge(ro[L],ro[it->fr]);Update(it->fr,0);
                }
                S[L]=R;Update(L,ro[L]);
            }
        } else {
            l=prev(S.upper_bound(L));r=prev(S.upper_bound(R));
            int A=l->fr,B=l->sc,C=r->fr,D=r->sc;
            Clear(res);
            if (l==r) AskLR(ro[A],L-A+1,R-A+1); else {
                AskLR(ro[A],L-A+1,B-A+1);
                if (B+1<=C-1) Ask(B+1,C-1);
                AskLR(ro[C],1,R-C+1);
            }
            printf("%d\n",Max(res));
        }
    }
    return 0;
}