Description
lxhgww最近收到了一个01序列，序列里面包含了n个数，这些数要么是0，要么是1，现在对于这个序列有五种变换操作和询问操作： 0 a b 把[a, b]区间内的所有数全变成0 1 a b 把[a, b]区间内的所有数全变成1 2 a b 把[a,b]区间内的所有数全部取反，也就是说把所有的0变成1，把所有的1变成0 3 a b 询问[a, b]区间内总共有多少个1 4 a b 询问[a, b]区间内最多有多少个连续的1 对于每一种询问操作，lxhgww都需要给出回答，聪明的程序员们，你们能帮助他吗？
坑爹的线段树。。
对于每个区间，维护：
左右连续串的长度，记录左右两边是0还是1；
记录区间内最长的连续的0,和1的数；
写起来太麻烦，调了一天ORZ；
/**************************************************************
Problem: 1858
User: 1115825064
Language: C++
Result: Accepted
Time:1696 ms
Memory:22468 kb
****************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=100010;
int m,n;
struct tr{
int lz,rz,l,r,sum,sum1,sum0;
bool ll,rr,la[2],lqf;
}t[N*6];
bool AA[N];
void fg(int ,int ,int ,int );
void qf(int ,int ,int );
void build(int wz,int l,int r)
{
t[wz].l=l;
t[wz].r=r;
if(l==r)
{
t[wz].lz=1;
t[wz].rz=1;
t[wz].ll=AA[l];
t[wz].rr=AA[l];
t[wz].sum1=int(AA[l]);
t[wz].sum=t[wz].sum1;
t[wz].sum0=!t[wz].sum1;
return ;
}
int mid=(r+l)/2;
build(wz<<1,l,mid);
build((wz<<1)+1,mid+1,r);
t[wz].sum=t[wz*2].sum+t[wz*2+1].sum;
if(t[wz*2].lz==mid-l+1)
{
t[wz].lz=mid-l+1;
if(t[wz*2].ll==t[wz*2+1].ll)
t[wz].lz+=t[wz*2+1].lz;
}
else
t[wz].lz=t[wz*2].lz;
t[wz].ll=t[wz*2].ll;
if(t[wz*2+1].rz==r-mid)
{
t[wz].rz=r-mid;
if(t[wz*2+1].rr==t[wz*2].rr)
t[wz].rz+=t[wz*2].rz;
}
else
t[wz].rz=t[wz*2+1].rz;
t[wz].rr=t[wz*2+1].rr;
t[wz].sum1=max(t[wz*2].sum1,t[wz*2+1].sum1);
if(t[wz*2].rr&&t[wz*2+1].ll&&t[wz*2].rz+t[wz*2+1].lz>t[wz].sum1)
t[wz].sum1=t[wz*2].rz+t[wz*2+1].lz;
t[wz].sum0=max(t[wz*2].sum0,t[wz*2+1].sum0);
if(!t[wz*2].rr&&!t[wz*2+1].ll&&t[wz*2].rz+t[wz*2+1].lz>t[wz].sum0)
t[wz].sum0=t[wz*2].rz+t[wz*2+1].lz;
return ;
}
void fg(int p,int wz,int l,int r)
{
if(t[wz].l==0||t[wz].r==0) return ;
if(t[wz].l>=l&&t[wz].r<=r)
{
t[wz].la[p]=1,t[wz].la[!p]=0,t[wz].lqf=0;
t[wz].ll=p;
t[wz].rr=p;
t[wz].rz=(t[wz].r-t[wz].l+1);
t[wz].lz=t[wz].rz;
t[wz].sum1=p==1?t[wz].lz:0;
t[wz].sum=t[wz].sum1;
t[wz].sum0=t[wz].lz-t[wz].sum1;
}
else
{
if(t[wz].la[0])
fg(0,wz*2,1,n),fg(0,wz*2+1,1,n);
if(t[wz].la[1])
fg(1,wz*2+1,1,n),fg(1,wz*2,1,n);
if(t[wz].lqf)
qf(wz*2,1,n),qf(wz*2+1,1,n);
t[wz].lqf=0;
t[wz].la[0]=0;
t[wz].la[1]=0;
if(t[wz*2].r>=l) fg(p,wz*2,l,r);
if(t[wz*2+1].l<=r) fg(p,wz*2+1,l,r);
t[wz].sum=t[wz*2].sum+t[wz*2+1].sum;
int mid=(t[wz].l+t[wz].r)/2;
if(t[wz*2].lz==mid-t[wz].l+1)
{
t[wz].lz=mid-t[wz].l+1;
if(t[wz*2].ll==t[wz*2+1].ll)
t[wz].lz+=t[wz*2+1].lz;
}
else
t[wz].lz=t[wz*2].lz;
t[wz].ll=t[wz*2].ll;
if(t[wz*2+1].rz==t[wz].r-mid)
{
t[wz].rz=t[wz].r-mid;
if(t[wz*2+1].rr==t[wz*2].rr)
t[wz].rz+=t[wz*2].rz;
}
else
t[wz].rz=t[wz*2+1].rz;
t[wz].rr=t[wz*2+1].rr;
t[wz].sum1=max(t[wz*2].sum1,t[wz*2+1].sum1);
if(t[wz*2].rr&&t[wz*2+1].ll&&t[wz*2].rz+t[wz*2+1].lz>t[wz].sum1)
t[wz].sum1=t[wz*2].rz+t[wz*2+1].lz;
t[wz].sum0=max(t[wz*2].sum0,t[wz*2+1].sum0);
if(!t[wz*2].rr&&!t[wz*2+1].ll&&t[wz*2].rz+t[wz*2+1].lz>t[wz].sum0)
t[wz].sum0=t[wz*2].rz+t[wz*2+1].lz;
}
}
void qf(int wz,int l,int r)
{
if(t[wz].l==0||t[wz].r==0) return ;
if(t[wz].l>=l&&t[wz].r<=r)
{
t[wz].ll=!t[wz].ll;
t[wz].rr=!t[wz].rr;
if(t[wz].la[0])
t[wz].la[0]=0,t[wz].la[1]=1;
else
if(t[wz].la[1])
t[wz].la[1]=0,t[wz].la[0]=1;
if(!t[wz].la[0]&&!t[wz].la[1])
t[wz].lqf=!t[wz].lqf;
t[wz].sum=t[wz].r-t[wz].l+1-t[wz].sum;
swap(t[wz].sum0,t[wz].sum1);
}
else
{
if(t[wz].la[0])
fg(0,wz*2,1,n),fg(0,wz*2+1,1,n);
if(t[wz].la[1])
fg(1,wz*2+1,1,n),fg(1,wz*2,1,n);
if(t[wz].lqf)
qf(wz*2,1,n),qf(wz*2+1,1,n);
t[wz].lqf=t[wz].la[0]=t[wz].la[1]=0;
if(t[wz*2].r>=l) qf(wz*2,l,r);
if(t[wz*2+1].l<=r) qf(wz*2+1,l,r);
t[wz].sum=t[wz*2].sum+t[wz*2+1].sum;
int mid=(t[wz].l+t[wz].r)/2;
if(t[wz*2].lz==mid-t[wz].l+1)
{
t[wz].lz=mid-t[wz].l+1;
if(t[wz*2].ll==t[wz*2+1].ll)
t[wz].lz+=t[wz*2+1].lz;
}
else
t[wz].lz=t[wz*2].lz;
t[wz].ll=t[wz*2].ll;
if(t[wz*2+1].rz==t[wz].r-mid)
{
t[wz].rz=t[wz].r-mid;
if(t[wz*2+1].rr==t[wz*2].rr)
t[wz].rz+=t[wz*2].rz;
}
else
t[wz].rz=t[wz*2+1].rz;
t[wz].rr=t[wz*2+1].rr;
t[wz].sum1=max(t[wz*2].sum1,t[wz*2+1].sum1);
if(t[wz*2].rr&&t[wz*2+1].ll&&t[wz*2].rz+t[wz*2+1].lz>t[wz].sum1)
t[wz].sum1=t[wz*2].rz+t[wz*2+1].lz;
t[wz].sum0=max(t[wz*2].sum0,t[wz*2+1].sum0);
if(!t[wz*2].rr&&!t[wz*2+1].ll&&t[wz*2].rz+t[wz*2+1].lz>t[wz].sum0)
t[wz].sum0=t[wz*2].rz+t[wz*2+1].lz;
}
}
int findsum(int wz,int l,int r)
{
if(t[wz].la[0])
fg(0,wz*2,1,n),fg(0,wz*2+1,1,n);
if(t[wz].la[1])
fg(1,wz*2+1,1,n),fg(1,wz*2,1,n);
if(t[wz].lqf)
qf(wz*2,1,n),qf(wz*2+1,1,n);
t[wz].lqf=0;
t[wz].la[0]=0;
t[wz].la[1]=0;
if(t[wz].l>=l&&t[wz].r<=r)
return t[wz].sum;
else
{
int ans=0;
if(t[wz*2].r>=l) ans+=findsum(wz*2,l,r);
if(t[wz*2+1].l<=r) ans+=findsum(wz*2+1,l,r);
return ans;
}
}
int findmax(int wz,int l,int r)
{
if(t[wz].la[0])
fg(0,wz*2,1,n),fg(0,wz*2+1,1,n);
if(t[wz].la[1])
fg(1,wz*2+1,1,n),fg(1,wz*2,1,n);
if(t[wz].lqf)
qf(wz*2,1,n),qf(wz*2+1,1,n);
t[wz].lqf=0;
t[wz].la[0]=0;
t[wz].la[1]=0;
if(t[wz].l>=l&&t[wz].r<=r)
return t[wz].sum1;
int ans=0;
if(t[wz*2].r>=l) ans=max(ans,findmax(wz*2,l,r));
if(t[wz*2+1].l<=r) ans=max(ans,findmax(wz*2+1,l,r));
if(t[wz*2].r>=l&&t[wz*2+1].l<=r&&t[wz*2].rr&&t[wz*2+1].ll)
{
int lll=min(t[wz*2].rz,t[wz*2].r-l+1);
int rrr=min(t[wz*2+1].lz,r-t[wz*2+1].l+1);
ans=max(ans,rrr+lll);
}
return ans;
}
int main()
{
//freopen("1.txt","r",stdin);
//freopen("1.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
cin>>AA[i];
build(1,1,n);
while(m--)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
b++;
c++;
if(a<=1)
fg(a,1,b,c);
if(a==2)
qf(1,b,c);
if(a==3)
printf("%d\n",findsum(1,b,c));
if(a==4)
printf("%d\n",findmax(1,b,c));
}
return 0;
}
评论 (0)
