专栏文章

P2572 [SCOI2010] 序列操作 题解

LLittle_Zyl
P2572题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minxg99l
此快照首次捕获于
2025/12/02 09:56
3 个月前
此快照最后确认于
2025/12/02 09:56
3 个月前
查看原文

题意

用线段树维护一个01序列，完成以下操作：
  1. 0 l r：[l,r]变为0
  2. 1 l r：[l,r]变为1
  3. 2 l r：[l,r]翻转
  4. 3 l r：[l,r]中1的数量
  5. 4 l r：[l,r]中最长的连续1

思路

每一个节点维护8个信息：
CPP
struct tree{
    int z1,z0,l1,l0,r1,r0,m1,m0;
}tr[N<<2];
总共1的个数(z1)，总共0的个数(z0)，从左起最长连续1(l1)，从左起最长连续0(l0)，从右起最长连续1(r1)，从右起最长连续0(r0)，最长连续1(m1)，最长连续0(m0)。每种信息分别维护0和1两种，有利于区间翻转(只需将0和1的信息分别互换)。
并维护两个懒标记，覆盖标记(tg1)，翻转标记(tg2)。

实现

在原来线段树的基础上增加hb函数，利于左右儿子合并：
CPP
tree hb(tree i,tree j){
	return (tree){i.z1+j.z1,i.z0+j.z0,
	i.z0?i.l1:i.m1+j.l1,i.z1?i.l0:i.m0+j.l0,
	j.z0?j.r1:j.m1+i.r1,j.z1?j.r0:j.m0+i.r0,
  max(max(i.m1,j.m1),i.r1+j.l1),max(max(i.m0,j.m0),i.r0+j.l0)};
}
在pushdown(pd)函数中，先进行覆盖，再翻转。下传时，优先处理赋值操作，因为它会覆盖翻转操作。翻转操作在处理时，如果子节点有赋值标记，则直接翻转赋值标记；否则翻转翻转标记：
CPP
void pd(int u,int l,int r){
	if(tg1[u]==1)tr[u]={r-l+1,0,r-l+1,0,r-l+1,0,r-l+1,0};
	if(tg1[u]==0)tr[u]={0,r-l+1,0,r-l+1,0,r-l+1,0,r-l+1};
	if(tg2[u])swap(tr[u].z1,tr[u].z0),swap(tr[u].l1,tr[u].l0),
    		  swap(tr[u].r1,tr[u].r0),swap(tr[u].m1,tr[u].m0);
	if(l^r){
		if(tg1[u]!=-1){
			tg1[u<<1]=tg1[u<<1|1]=tg1[u];
			tg2[u<<1]=tg2[u<<1|1]=0;
		}
		if(tg2[u]){
			if(tg1[u<<1]!=-1)tg1[u<<1]^=1;
			else tg2[u<<1]^=1;
			if(tg1[u<<1|1]!=-1)tg1[u<<1|1]^=1;
			else tg2[u<<1|1]^=1;
		}
	}
	tg1[u]=-1,tg2[u]=0;
}
线段树的其余部分只需稍加修改就行。
完整代码： 以下代码省略了前文的hb与pd部分
CPP
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
struct segment{
	#define mid ((l+r)>>1)
	struct tree{int z1,z0,l1,l0,r1,r0,m1,m0;};
	tree tr[N<<2];int n,tg1[N<<2],tg2[N<<2];
	segment(){memset(tg1,-1,sizeof(tg1));}
	tree hb(tree i,tree j){...}
	void pd(int u,int l,int r){...}
	void pu(int u,int l,int r){
		if(l^r)pd(u<<1,l,mid),pd(u<<1|1,mid+1,r);
		tr[u]=hb(tr[u<<1],tr[u<<1|1]);
	}
	void update(int u,int l,int r,int L,int R,int v){
		pd(u,l,r);
		if(L<=l&&r<=R){
			if(v==0)tg1[u]=0,tg2[u]=0;
			else if(v==1)tg1[u]=1,tg2[u]=0;
			else tg2[u]^=1;
			return ;
		}
		if(L<=mid)update(u<<1,l,mid,L,R,v);
		if(R>mid)update(u<<1|1,mid+1,r,L,R,v);
		pu(u,l,r);
	}void update(int L,int R,int v){update(1,1,n,L,R,v);}
	tree query(int u,int l,int r,int L,int R,tree ans=tree()){
		pd(u,l,r);
		if(L<=l&&r<=R)return tr[u];
		if(L<=mid)ans=hb(ans,query(u<<1,l,mid,L,R));
		if(R>mid)ans=hb(ans,query(u<<1|1,mid+1,r,L,R));
		return ans;
	}tree query(int L,int R){return query(1,1,n,L,R);}
	void write(int u,int l,int r){
		if(l==r){
			cout<<tr[u].z1<<" ";
			return ;
		}
		write(u<<1,l,mid),write(u<<1|1,mid+1,r);
	}void write(){write(1,1,n);}
}tree;
int n,m;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m,tree.n=n;
    for(int i=1,x;i<=n;i++)
    	cin>>x,tree.update(i,i,x);
    for(int op,l,r;m--;){
    	cin>>op>>l>>r;l++,r++;
    	if(op<3)tree.update(l,r,op);
    	else cout<<(op==3?tree.query(l,r).z1:tree.query(l,r).m1)<<"\n";
//		tree.write(),cout<<"**\n";
	}
	return 0;
}
AC记录

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...