【洛谷P5500】[LnOI2019]真正的OIer从不女装 | Mrsrz's blog

线段树

题目大意：

给定一个序列，支持两个操作：

1. 给定 $l,r,x$，将 $a_l\sim a_r$ 都变为 $x$。
2. 给定 $l,r,k$，每次可以选择一个整数 $p\in[l,r)$ 并翻转区间 $[l,p]$ 和 $[p+1,r]$ 内的数，最多操作 $k$ 次，要求最大化所有值相等的子区间的长度。求最大长度。操作完后区间会复原到操作之前的状态。

题解：

考虑那个翻转的操作。

事实上，当 $k>1$ 的时候，能得到的最大答案和 $k=1$ 的情况相同。

如果一次翻转产生了贡献，那么操作前，区间最左边和最右边都应该是目标数。然后一次翻转使得两个目标数所在区间合并，产生额外贡献。

但是，翻转一次后，区间两边的数就变为了原来分裂位置的两个数，而这两个数我们是不要的。再翻转一次，无论位置在哪里，合并到一起的一定还是这两个数，无法产生更多的贡献。

所以只需要考虑不操作和操作一次的情况即可。

这个就可以用线段树维护区间信息了。每个区间维护三个值 $pre,suf,mx$，分别表示前缀相同区间长度、后缀相同区间长度和区间内最大相同子区间长度。同时记录 $pre,suf,mx$ 分别对应的数值，转移时判断是否能合并。

合并的时候可以根据两段区间的这三个值，$O(1)$ 完成求出合并后的区间的这三个值。

查询时，不操作的就是 $mx$ 的值，操作一次使，如果两边的数相同且整个区间 $[l,r]$ 不止一种值，则合并出来的更大的贡献就是 $pre+suf$。

区间赋值操作直接打标记即可。

时间复杂度 $O((n+m)\log n)$。

Code：

#include<iostream>
#include<utility>
#include<algorithm>
using namespace std;
const int N=2e5+5;
int n,m;
int tag[N<<2];
pair<int,int>pre[N<<2],suf[N<<2],mx[N<<2];
struct data{
    pair<int,int>pre,suf,mx;
    int len;
};
inline data merge(data x,data y){
    data ret;
    ret.pre=x.pre.first==x.len&&x.pre.second==y.pre.second?make_pair(x.len+y.pre.first,x.pre.second):x.pre;
    ret.suf=y.suf.first==y.len&&y.suf.second==x.suf.second?make_pair(y.len+x.suf.first,y.suf.second):y.suf;
    ret.mx=max(x.mx,y.mx);
    if(x.suf.second==y.pre.second&&x.suf.first+y.pre.first>ret.mx.first)
        ret.mx=make_pair(x.suf.first+y.pre.first,x.suf.second);
    ret.len=x.len+y.len;
    return ret;
}
inline void pushdown(int o,int len){
    pre[o<<1]=suf[o<<1]=mx[o<<1]=make_pair(len+1>>1,tag[o]);
    pre[o<<1|1]=suf[o<<1|1]=mx[o<<1|1]=make_pair(len>>1,tag[o]);
    tag[o<<1]=tag[o<<1|1]=tag[o];
    tag[o]=0;
}
inline void update(int o,int len){
    pre[o]=(pre[o<<1].first==(len+1>>1)&&pre[o<<1].second==pre[o<<1|1].second)?
        make_pair((len+1>>1)+pre[o<<1|1].first,pre[o<<1].second):pre[o<<1];
    suf[o]=(suf[o<<1|1].first==(len>>1)&&suf[o<<1].second==suf[o<<1|1].second)?
        make_pair((len>>1)+suf[o<<1].first,suf[o<<1|1].second):suf[o<<1|1];
    mx[o]=max(mx[o<<1],mx[o<<1|1]);
    if(suf[o<<1].second==pre[o<<1|1].second&&suf[o<<1].first+pre[o<<1|1].first>mx[o].first)
        mx[o]=make_pair(suf[o<<1].first+pre[o<<1|1].first,suf[o<<1].second);
}
void modify(int l,int r,int o,const int&L,const int&R,const int&v){
    if(L<=l&&r<=R){
        pre[o]=suf[o]=mx[o]=make_pair(r-l+1,tag[o]=v);
        return;
    }
    if(tag[o])pushdown(o,r-l+1);
    const int mid=l+r>>1;
    if(L<=mid)modify(l,mid,o<<1,L,R,v);
    if(mid<R)modify(mid+1,r,o<<1|1,L,R,v);
    update(o,r-l+1);
}
data query(int l,int r,int o,const int&L,const int&R){
    if(L<=l&&r<=R)return(data){pre[o],suf[o],mx[o],r-l+1};
    if(tag[o])pushdown(o,r-l+1);
    const int mid=l+r>>1;
    if(L<=mid&&mid<R)return merge(query(l,mid,o<<1,L,R),query(mid+1,r,o<<1|1,L,R));
    if(L<=mid)return query(l,mid,o<<1,L,R);return query(mid+1,r,o<<1|1,L,R);
}
void build(int l,int r,int o){
    if(l==r){
        int x;
        cin>>x;
        pre[o]=suf[o]=mx[o]=make_pair(1,x);
        return;
    }
    const int mid=l+r>>1;
    build(l,mid,o<<1),build(mid+1,r,o<<1|1);
    update(o,r-l+1);
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    build(1,n,1);
    while(m--){
        char op[3];
        int l,r,x;
        cin>>op>>l>>r>>x;
        if(*op=='R')
            modify(1,n,1,l,r,x);
        else{
            data g=query(1,n,1,l,r);
            int ans=g.mx.first;
            if(x&&g.pre.second==g.suf.second&&g.pre.first<r-l+1)ans=max(ans,g.pre.first+g.suf.first);
            cout<<ans<<'\n';
        }
    }
    return 0;
}