【线段树】P6492 STEP

深碍√TFBOYSˉ_ 2024-03-17 15:04 85阅读 0赞

[P6492 \[COCI2010-2011\#6\] STEP - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)][P6492 _COCI2010-2011_6_ STEP - _ _ _ _luogu.com.cn]

题意：

![48082ef1c9134be7a674bd2a28e5a38f.png][]

![91489698409c4a719676d670f53a8d05.png][]

思路：

要维护区间最长子串，就需要维护左起最长子串和右起最长子串

区间最长子串可能是左区间最长子串，可能是右区间最长子串，也可能是左起最长子串+右起最长子串，但是这种情况有个条件：左区间右端点和右区间左端点不能一样（类似于分治的感觉）

那么就得维护区间两端的种类

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=2e5+10;
    const int mxe=2e5+10;
    const int mod=1e9+7;
    
    struct info{
    	int lmx=0,rmx=0,mx=0,sz=0,L=0,R=0;
    	info(){}
    	info(int a): lmx(a),rmx(a),mx(a),L(a),R(a){}
    };
    
    info operator+(const info &l,const info &r){
    	info res;
    	res.sz=l.sz+r.sz;
    	res.L=l.L;
    	res.R=r.R;
    	res.lmx=max(res.lmx,l.lmx);
    	if(l.lmx==l.sz&&l.R!=r.L) res.lmx=max(res.lmx,l.sz+r.lmx);
    	res.rmx=max(res.rmx,r.rmx);
    	if(r.rmx==r.sz&&l.R!=r.L) res.rmx=max(res.rmx,r.sz+l.rmx);
    	res.mx=max(l.mx,r.mx);
    	if(l.R!=r.L) res.mx=max(res.mx,l.rmx+r.lmx);
    	return res;
    }
    
    struct Segtree{
    	info val;
    }tree[mxe<<2];
    
    int N,Q,x;
    
    void pushup(int rt){
    	tree[rt].val=tree[rt<<1].val+tree[rt<<1|1].val;
    }
    void build(int rt,int l,int r){
    	if(l==r){
    		tree[rt].val.sz=r-l+1;
    		tree[rt].val.lmx=tree[rt].val.rmx=tree[rt].val.mx=1;
    		tree[rt].val.L=tree[rt].val.R=0;
    		return;
    	}
    	int mid=l+r>>1;
    	build(rt<<1,l,mid);
    	build(rt<<1|1,mid+1,r);
    	pushup(rt);
    }
    void modify(int rt,int l,int r,int x){
    	if(l==r){
    		if(tree[rt].val.L==0){
    			tree[rt].val.L=tree[rt].val.R=1;
    		}else{
    			tree[rt].val.L=tree[rt].val.R=0;
    		}
    		return;
    	}
    	int mid=l+r>>1;
    	if(x<=mid) modify(rt<<1,l,mid,x);
    	else modify(rt<<1|1,mid+1,r,x);
    	pushup(rt);
    }
    info query(int rt,int l,int r,int x,int y){
    	if(x<=l&&r<=y){
    		return tree[rt].val;
    	}
    	int mid=l+r>>1;
    	if(x>mid) return query(rt<<1|1,mid+1,r,x,y);
    	else if(y<=mid) return query(rt<<1,l,mid,x,y);
    	else{
    		return query(rt<<1,l,mid,x,y)+query(rt<<1|1,mid+1,r,x,y);
    	}
    }
    void solve(){
    	cin>>N>>Q;
    	build(1,1,N);
    	while(Q--){ 
    		cin>>x;
    		modify(1,1,N,x);
    		cout<<query(1,1,N,1,N).mx<<'\n';
    	}
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }

[P6492 _COCI2010-2011_6_ STEP - _ _ _ _luogu.com.cn]: https://www.luogu.com.cn/problem/P6492
[48082ef1c9134be7a674bd2a28e5a38f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/e871022433d54844b34641ddad2b7d20.png
[91489698409c4a719676d670f53a8d05.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/8b86753f48fd407fb4bf4c25f4a1cb5b.png