题解 P2572 【[SCOI2010]序列操作】
Froggy
·
·
题解
线段树??
不要!!
fhq \ Treap 是也!!
线段树维护区间最长连续1很麻烦,平衡树就能很好地减少码量
有一个减少码量的神器:结构体内定义函数!(就是封装起来)
在外部直接疯狂调用即可!
虽说比较慢,但AC是没问题的,这又是省选题,开O2后快到飞起!
细节各位大佬都已说了,这里再点一下:
首先是反转和推平操作的优先级问题,其实谁先谁后都行,但都要注意前一个操作会影响后一个操作
比如我写的是先反转再推平,那么反转操作时别忘了也把推平标记取反
平衡树节点记录信息既要记录关于0的也要记录关于1的,这样子反转操作直接把有关0,1的swap一下即可
说一下变量含义,方便大家理解:
$rmax[0/1]$ 区间最右侧连续0/1的个数
$mx[0/1]$ 区间内最多有连续的0/1的个数
$sum1$ 区间内1的个数
$rev$ 反转标记
$cov$ 推平标记(若值为-1则表示不用推平)
$key$ 键值
$val$ 这个位置的值(0/1)
$siz$ 子树(区间)大小
$ch[0/1]$ 左/右儿子
结构体里的封装(只用封装反转和推平)
```cpp
struct node{
int siz,key,ch[2],val,lmax[2],rmax[2],mx[2],sum1;
int cov;
bool rev;
inline void Rev(){//反转
rev^=1;
swap(lmax[0],lmax[1]);
swap(rmax[0],rmax[1]);
swap(mx[0],mx[1]);
if(cov!=-1)cov^=1;
sum1=siz-sum1;
val^=1;
}
inline void Cov(int d){//推平
val=d;
cov=d;
sum1=(d?siz:0);
for(int i=0;i<=1;i++){
lmax[i]=rmax[i]=mx[i]=((d==i)?siz:0);
}
}
}t[N];
```
这样就能保证代码的简洁啦!o(*￣▽￣\*)ブ
没有一点压行,长度比除珂朵莉树外的题解短多了
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
#define N 100100
inline int read(){
int x=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-')f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=(x<<3)+(x<<1)+c-'0';
c=getchar();
}
return x*f;
}
int n,m,cnt,root;
struct node{
int siz,key,ch[2],val,lmax[2],rmax[2],mx[2],sum1;
int cov;
bool rev;
inline void Rev(){
rev^=1;
swap(lmax[0],lmax[1]);
swap(rmax[0],rmax[1]);
swap(mx[0],mx[1]);
if(cov!=-1)cov^=1;
sum1=siz-sum1;
val^=1;
}
inline void Cov(int d){
val=d;
cov=d;
sum1=(d?siz:0);
for(int i=0;i<=1;i++){
lmax[i]=rmax[i]=mx[i]=((d==i)?siz:0);
}
}
}t[N];
int NewNode(int data){//初始化别漏了东西,否则会出一些奇怪的错误
int k=++cnt;
t[k].val=t[k].sum1=data;
t[k].siz=1;
t[k].key=rand();
t[k].ch[0]=t[k].ch[1]=0;
t[k].rev=0;
t[k].cov=-1;
for(int i=0;i<=1;i++){
t[k].lmax[i]=t[k].rmax[i]=t[k].mx[i]=(data==i);
}
return k;
}
inline void update(int k){
t[k].siz=t[t[k].ch[0]].siz+t[t[k].ch[1]].siz+1;
t[k].sum1=t[t[k].ch[0]].sum1+t[t[k].ch[1]].sum1+t[k].val;
for(int i=0;i<=1;i++){
t[k].lmax[i]=t[t[k].ch[0]].lmax[i];
t[k].rmax[i]=t[t[k].ch[1]].rmax[i];
t[k].mx[i]=max(t[t[k].ch[0]].mx[i],t[t[k].ch[1]].mx[i]);
if(t[k].val==i){//当i等于节点的值时还要再次更新
if(t[t[k].ch[0]].sum1==(i?t[t[k].ch[0]].siz:0)){//判断是否左子树内都是相同的值(并且等于i)
t[k].lmax[i]+=1+t[t[k].ch[1]].lmax[i];
}
if(t[t[k].ch[1]].sum1==(i?t[t[k].ch[1]].siz:0)){//类上
t[k].rmax[i]+=1+t[t[k].ch[0]].rmax[i];
}
t[k].mx[i]=max(t[k].mx[i],t[t[k].ch[0]].rmax[i]+1+t[t[k].ch[1]].lmax[i]);
}
}
}
inline void pushdown(int k){
if(t[k].rev){
t[t[k].ch[0]].Rev();
t[t[k].ch[1]].Rev();
t[k].rev=0;
}
if(t[k].cov!=-1){
t[t[k].ch[0]].Cov(t[k].cov);
t[t[k].ch[1]].Cov(t[k].cov);
t[k].cov=-1;
}
}
int Merge(int l,int r){
if(!l||!r){
return l+r;
}
pushdown(l),pushdown(r);
if(t[l].key<t[r].key){
t[l].ch[1]=Merge(t[l].ch[1],r);
update(l);
return l;
}
else{
t[r].ch[0]=Merge(l,t[r].ch[0]);
update(r);
return r;
}
}
void Split(int k,int data,int &l,int &r){
if(!k){
l=r=0;
return ;
}
pushdown(k);
if(t[t[k].ch[0]].siz+1<=data){
l=k;
Split(t[k].ch[1],data-t[t[k].ch[0]].siz-1,t[k].ch[1],r);
}
else{
r=k;
Split(t[k].ch[0],data,l,t[k].ch[0]);
}
update(k);
}
inline void Change(int x,int y,int d){
int l,p,r;
Split(root,y,l,r);
Split(l,x-1,l,p);
t[p].Cov(d);
root=Merge(Merge(l,p),r);
}
inline void Reverse(int x,int y){
int l,p,r;
Split(root,y,l,r);
Split(l,x-1,l,p);
t[p].Rev();
root=Merge(Merge(l,p),r);
}
inline int Count1(int x,int y){
int l,p,r;
Split(root,y,l,r);
Split(l,x-1,l,p);
int ans=t[p].sum1;
root=Merge(Merge(l,p),r);
return ans;
}
inline int Ask_MX(int x,int y){
int l,p,r;
Split(root,y,l,r);
Split(l,x-1,l,p);
int ans=t[p].mx[1];
root=Merge(Merge(l,p),r);
return ans;
}
int main(){
n=read(),m=read();
for(register int i=1;i<=n;++i){
int x=read();
root=Merge(root,NewNode(x));
}
for(register int i=1;i<=m;++i){
int opt=read(),l=read()+1,r=read()+1;
if(opt==0){
Change(l,r,0);
}
else if(opt==1){
Change(l,r,1);
}
else if(opt==2){
Reverse(l,r);
}
else if(opt==3){
printf("%d\n",Count1(l,r));
}
else{
printf("%d\n",Ask_MX(l,r));
}
}
return 0;
}
```
[*Froggy's blog*](https://www.luogu.org/blog/1445353309froggy/)
#### 呱!!