實在不行，改了方法。SET 0和SET 1用延遲標記，翻轉不用任何標記，直接更新到底。800+MS AC.
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int const maxn=1000010;
#define Max(a,b) ((a>b?a:b))
#define Min(a,b) ((a<b?a:b))
int LL(int i) 
{return (i*2);}
int RR(int i){return (i*2+1);}
struct node
{
int sum;//統計1的個數
int st;
int cval0,lval0,rval0;//統計最大連續0,左連續0,右連續0
int cval1,lval1,rval1;//統計最大連續1,左連續1,右連續1
int l,r;
void doit()
{
if(st==0)
{
cval1=lval1=rval1=0;
cval0=rval0=lval0=len();
sum=0;
}
else if(st==1)
{
cval1=lval1=rval1=len();
cval0=lval0=rval0=0;
sum=len();
}
}
int len(){return r-l+1;}
}ST[maxn*8];
int a[maxn];//存輸入數據
void reverse(int i)
{
ST[i].sum=ST[i].len()-ST[i].sum;
ST[i].st=!ST[i].st;
swap(ST[i].cval1,ST[i].cval0);
swap(ST[i].rval1,ST[i].rval0);
swap(ST[i].lval1,ST[i].lval0);
}
void Up(int i)
{
if(ST[LL(i)].st!=-1&&ST[RR(i)].st!=-1)
{
if(ST[LL(i)].st==ST[RR(i)].st)
ST[i].st=ST[LL(i)].st;
}
ST[i].cval0=Max(ST[LL(i)].cval0,ST[RR(i)].cval0);
ST[i].cval0=Max(ST[i].cval0,ST[LL(i)].rval0+ST[RR(i)].lval0);
ST[i].lval0=ST[LL(i)].lval0;
ST[i].rval0=ST[RR(i)].rval0;
if(ST[LL(i)].lval0==ST[LL(i)].len())
ST[i].lval0+=ST[RR(i)].lval0;
if(ST[RR(i)].rval0==ST[RR(i)].len())
ST[i].rval0+=ST[LL(i)].rval0;
/**///////////////////////////////////////////////////////////////////////////
ST[i].cval1=Max(ST[LL(i)].cval1,ST[RR(i)].cval1);
ST[i].cval1=Max(ST[i].cval1,ST[LL(i)].rval1+ST[RR(i)].lval1);
ST[i].lval1=ST[LL(i)].lval1;
ST[i].rval1=ST[RR(i)].rval1;
if(ST[LL(i)].lval1==ST[LL(i)].len())
ST[i].lval1+=ST[RR(i)].lval1;
if(ST[RR(i)].rval1==ST[RR(i)].len())
ST[i].rval1+=ST[LL(i)].rval1;
/**///////////////////////////////////////////////////////////////////////////
ST[i].sum=ST[LL(i)].sum+ST[RR(i)].sum;
/**///////////////////////////////////////////////////////////////////////////
}
void Down(int i)
{
if(ST[i].st!=-1)
{
ST[LL(i)].st=ST[RR(i)].st=ST[i].st;
ST[LL(i)].doit();
ST[RR(i)].doit();
ST[i].st=-1;
}
}
void Build(int l,int r,int i)
{
ST[i].l=l;
ST[i].r=r;
ST[i].st=-1;
if(l==r)
{
ST[i].st=a[l];
ST[i].sum=a[l];
if(a[r]==1)
{
ST[i].cval1=ST[i].lval1=ST[i].rval1=1;
ST[i].cval0=ST[i].lval0=ST[i].rval0=0;
}
else
{
ST[i].cval1=ST[i].lval1=ST[i].rval1=0;
ST[i].cval0=ST[i].lval0=ST[i].rval0=1;
}
return ;
}
int mid=(l+r)>>1;
Build(l,mid,LL(i));
Build(mid+1,r,RR(i));
Up(i);
}
void update(int l,int r,int op,int i)
{
if(l==ST[i].l&&r==ST[i].r)
{
ST[i].st=op;
ST[i].doit();
return;
}
Down(i);
int mid=(ST[i].l+ST[i].r)>>1;
if(r<=mid)update(l,r,op,LL(i));
else if(l>mid)update(l,r,op,RR(i));
else
{
update(l,mid,op,LL(i));
update(mid+1,r,op,RR(i));
}
Up(i);
}
void Set_Rev(int l,int r,int i)
{
if(l==ST[i].l&&r==ST[i].r&&ST[i].st!=-1)
{
reverse(i);
return;
}
Down(i);
int mid=(ST[i].l+ST[i].r)>>1;
if(r<=mid)Set_Rev(l,r,LL(i));
else if(l>mid)Set_Rev(l,r,RR(i));
else
{
Set_Rev(l,mid,LL(i));
Set_Rev(mid+1,r,RR(i));
}
Up(i);
}
int Query1(int l,int r,int i)//查詢[l,r]有多少1
{
if(ST[i].l==l&&ST[i].r==r)
return ST[i].sum;
if(ST[i].st!=-1)
{
if(ST[i].st==0)
return 0;
else
return (r-l+1);
}
int mid=(ST[i].l+ST[i].r)>>1;
if(r<=mid)return Query1(l,r,LL(i));
if(l>mid)return Query1(l,r,RR(i));
else{return Query1(l,mid,LL(i))+Query1(mid+1,r,RR(i));}
}
int Query2(int l,int r,int i)//查[l,r]中最大連續1
{
if(ST[i].l==l&&ST[i].r==r)
return ST[i].cval1;
if(ST[i].st!=-1)
{
if(ST[i].st==0)
return 0;
else
return (r-l+1);
}
//
int mid=(ST[i].l+ST[i].r)>>1;
if(r<=mid)return Query2(l,r,LL(i));
if(l>mid)return Query2(l,r,RR(i));
else
{
int maxl=Query2(l,mid,LL(i));
int maxr=Query2(mid+1,r,RR(i));
return Max(Max(maxl,maxr),Min(mid-l+1,ST[LL(i)].rval1)+Min(r-mid,ST[RR(i)].lval1));
}
}
int n,m;
int main()
{
int ca;
int i;
scanf("%d",&ca);
while(ca--)
{
scanf("%d %d",&n,&m);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
Build(1,n,1);
for(i=0;i<m;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
if(b>c)
swap(b,c);
b++;c++;
if(a==0)
update(b,c,0,1);
else if(a==1)
update(b,c,1,1);
else if(a==2)
Set_Rev(b,c,1);
else if(a==3)
printf("%d\n",Query1(b,c,1));
else
{
printf("%d\n",Query2(b,c,1));
}
}
}
return 0;
}
---------------------------------------------------------------------------------------------------------------------------------------------------------------
調了一整天，一般能想到的數據都過了，但就是不得AC...無語了.... 沒測試數據，這題擱淺了...(11月3日)
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int const maxn=1000010;
#define Max(a,b) ((a>b?a:b))
#define Min(a,b) ((a<b?a:b))
int Lchild(int i)
{
return (i*2);
}
int Rchild(int i)
{
return (i*2+1);
}
struct node
{
int sum;//統計1的個數
int rev;
int st;
int cval0,lval0,rval0;//統計最大連續0,左連續0,右連續0
int cval1,lval1,rval1;//統計最大連續1,左連續1,右連續1
int l,r;
void doit()
{
if(st==0)
{
cval1=lval1=rval1=0;
cval0=rval0=lval0=len();
sum=0;
}
else if(st==1)
{
cval1=lval1=rval1=len();
cval0=lval0=rval0=0;
sum=len();
}
}
int len(){return r-l+1;}
}ST[maxn*8];
int a[maxn];//存輸入數據
void qufan(int i)
{
ST[i].sum=ST[i].len()-ST[i].sum;
swap(ST[i].cval1,ST[i].cval0);
swap(ST[i].rval1,ST[i].rval0);
swap(ST[i].lval1,ST[i].lval0);
}
void Build(int l,int r,int i)
{
ST[i].l=l;
ST[i].r=r;
ST[i].rev=0;
ST[i].st=-1;
if(l==r)
{
//ST[i].st=a[l];
ST[i].sum=a[l];
if(a[r]==1)
{
ST[i].cval1=ST[i].lval1=ST[i].rval1=1;
ST[i].cval0=ST[i].lval0=ST[i].rval0=0;
}
else
{
ST[i].cval1=ST[i].lval1=ST[i].rval1=0;
ST[i].cval0=ST[i].lval0=ST[i].rval0=1;
}
return ;
}
int mid=(l+r)>>1;
Build(l,mid,Lchild(i));
Build(mid+1,r,Rchild(i));
ST[i].cval0=Max(ST[Lchild(i)].cval0,ST[Rchild(i)].cval0);
ST[i].cval0=Max(ST[i].cval0,ST[Lchild(i)].rval0+ST[Rchild(i)].lval0);
ST[i].lval0=ST[Lchild(i)].lval0;
ST[i].rval0=ST[Rchild(i)].rval0;
if(ST[Lchild(i)].lval0==ST[Lchild(i)].len())
ST[i].lval0+=ST[Rchild(i)].lval0;
if(ST[Rchild(i)].rval0==ST[Rchild(i)].len())
ST[i].rval0+=ST[Lchild(i)].rval0;
/**///////////////////////////////////////////////////////////////////////////
ST[i].cval1=Max(ST[Lchild(i)].cval1,ST[Rchild(i)].cval1);
ST[i].cval1=Max(ST[i].cval1,ST[Lchild(i)].rval1+ST[Rchild(i)].lval1);
ST[i].lval1=ST[Lchild(i)].lval1;
ST[i].rval1=ST[Rchild(i)].rval1;
if(ST[Lchild(i)].lval1==ST[Lchild(i)].len())
ST[i].lval1+=ST[Rchild(i)].lval1;
if(ST[Rchild(i)].rval1==ST[Rchild(i)].len())
ST[i].rval1+=ST[Lchild(i)].rval1;
/**///////////////////////////////////////////////////////////////////////////
ST[i].sum=ST[Lchild(i)].sum+ST[Rchild(i)].sum;
/**///////////////////////////////////////////////////////////////////////////
}
void push_down(int i)
{
if(ST[i].st!=-1)
{
ST[Lchild(i)].st=ST[Rchild(i)].st=ST[i].st;
//ST[Lchild(i)].rev=0;
//ST[Rchild(i)].rev=0;
}
if(ST[i].rev==1)
{
ST[Lchild(i)].rev^=1;
ST[Rchild(i)].rev^=1;
//qufan(Lchild(i));
//qufan(Rchild(i));
//ST[i].rev=0;
}
}
void update(int l,int r,int op,int i)
{
if(l==ST[i].l&&r==ST[i].r)
{
ST[i].st=op;
ST[i].rev=0;
ST[i].doit();
return;
}
push_down(i);
if(ST[i].st!=-1)
{
ST[Lchild(i)].doit();
}
if(ST[i].rev==1)
qufan(Lchild(i));
if(ST[i].st!=-1)
{
ST[Rchild(i)].doit();
ST[i].st=-1;
}
if(ST[i].rev==1)
{
qufan(Rchild(i));
ST[i].rev=0;
}
int mid=(ST[i].l+ST[i].r)>>1;
if(r<=mid)update(l,r,op,Lchild(i));
else if(l>mid)update(l,r,op,Rchild(i));
else
{
update(l,mid,op,Lchild(i));
update(mid+1,r,op,Rchild(i));
}
ST[i].cval0=Max(ST[Lchild(i)].cval0,ST[Rchild(i)].cval0);
ST[i].cval0=Max(ST[i].cval0,ST[Lchild(i)].rval0+ST[Rchild(i)].lval0);
ST[i].lval0=ST[Lchild(i)].lval0;
ST[i].rval0=ST[Rchild(i)].rval0;
if(ST[Lchild(i)].lval0==ST[Lchild(i)].len())
ST[i].lval0+=ST[Rchild(i)].lval0;
if(ST[Rchild(i)].rval0==ST[Rchild(i)].len())
ST[i].rval0+=ST[Lchild(i)].rval0;
/**///////////////////////////////////////////////////////////////////////////
ST[i].cval1=Max(ST[Lchild(i)].cval1,ST[Rchild(i)].cval1);
ST[i].cval1=Max(ST[i].cval1,ST[Lchild(i)].rval1+ST[Rchild(i)].lval1);
ST[i].lval1=ST[Lchild(i)].lval1;
ST[i].rval1=ST[Rchild(i)].rval1;
if(ST[Lchild(i)].lval1==ST[Lchild(i)].len())
ST[i].lval1+=ST[Rchild(i)].lval1;
if(ST[Rchild(i)].rval1==ST[Rchild(i)].len())
ST[i].rval1+=ST[Lchild(i)].rval1;
/**///////////////////////////////////////////////////////////////////////////
ST[i].sum=ST[Lchild(i)].sum+ST[Rchild(i)].sum;
/**///////////////////////////////////////////////////////////////////////////
}
void Set_Rev(int l,int r,int i)
{
if(l==ST[i].l&&r==ST[i].r)
{
ST[i].rev^=1;
qufan(i);
return;
}
push_down(i);
if(ST[i].st!=-1)
{
ST[Lchild(i)].doit();
}
if(ST[i].rev==1)
qufan(Lchild(i));
if(ST[i].st!=-1)
{
ST[Rchild(i)].doit();
ST[i].st=-1;
}
if(ST[i].rev==1)
{
qufan(Rchild(i));
ST[i].rev=0;
}
int mid=(ST[i].l+ST[i].r)>>1;
if(r<=mid)Set_Rev(l,r,Lchild(i));
else if(l>mid)Set_Rev(l,r,Rchild(i));
else
{
Set_Rev(l,mid,Lchild(i));
Set_Rev(mid+1,r,Rchild(i));
}
ST[i].cval0=Max(ST[Lchild(i)].cval0,ST[Rchild(i)].cval0);
ST[i].cval0=Max(ST[i].cval0,ST[Lchild(i)].rval0+ST[Rchild(i)].lval0);
ST[i].lval0=ST[Lchild(i)].lval0;
ST[i].rval0=ST[Rchild(i)].rval0;
if(ST[Lchild(i)].lval0==ST[Lchild(i)].len())
ST[i].lval0+=ST[Rchild(i)].lval0;
if(ST[Rchild(i)].rval0==ST[Rchild(i)].len())
ST[i].rval0+=ST[Lchild(i)].rval0;
/**///////////////////////////////////////////////////////////////////////////
ST[i].cval1=Max(ST[Lchild(i)].cval1,ST[Rchild(i)].cval1);
ST[i].cval1=Max(ST[i].cval1,ST[Lchild(i)].rval1+ST[Rchild(i)].lval1);
ST[i].lval1=ST[Lchild(i)].lval1;
ST[i].rval1=ST[Rchild(i)].rval1;
if(ST[Lchild(i)].lval1==ST[Lchild(i)].len())
ST[i].lval1+=ST[Rchild(i)].lval1;
if(ST[Rchild(i)].rval1==ST[Rchild(i)].len())
ST[i].rval1+=ST[Lchild(i)].rval1;
/**///////////////////////////////////////////////////////////////////////////
ST[i].sum=ST[Lchild(i)].sum+ST[Rchild(i)].sum;
/**///////////////////////////////////////////////////////////////////////////
}
int Query1(int l,int r,int i)//查詢[l,r]有多少1
{
if(ST[i].l==l&&ST[i].r==r)
return ST[i].sum;
push_down(i);
if(ST[i].st!=-1)
{
ST[Lchild(i)].doit();
}
if(ST[i].rev==1)
qufan(Lchild(i));
if(ST[i].st!=-1)
{
ST[Rchild(i)].doit();
ST[i].st=-1;
}
if(ST[i].rev==1)
{
qufan(Rchild(i));
ST[i].rev=0;
}
int mid=(ST[i].l+ST[i].r)>>1;
if(r<=mid)return Query1(l,r,Lchild(i));
if(l>mid)return Query1(l,r,Rchild(i));
else{return Query1(l,mid,Lchild(i))+Query1(mid+1,r,Rchild(i));}
}
int Query2(int l,int r,int i)//查[l,r]中最大連續1
{
if(ST[i].l==l&&ST[i].r==r)
return ST[i].cval1;
push_down(i);
if(ST[i].st!=-1)
{
ST[Lchild(i)].doit();
}
if(ST[i].rev==1)
qufan(Lchild(i));
if(ST[i].st!=-1)
{
ST[Rchild(i)].doit();
ST[i].st=-1;
}
if(ST[i].rev==1)
{
qufan(Rchild(i));
ST[i].rev=0;
}
//
int mid=(ST[i].l+ST[i].r)>>1;
if(r<=mid)return Query2(l,r,Lchild(i));
if(l>mid)return Query2(l,r,Rchild(i));
else
{
int maxl=Query2(l,mid,Lchild(i));
int maxr=Query2(mid+1,r,Rchild(i));
return Max(Max(maxl,maxr),Min(mid-l+1,ST[Lchild(i)].rval1)+Min(r-mid,ST[Rchild(i)].lval1));
}
}
int n,m;
int main()
{
int ca;
int i;
scanf("%d",&ca);
while(ca--)
{
scanf("%d %d",&n,&m);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
Build(1,n,1);
for(i=0;i<m;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
if(b>c)
swap(b,c);
b++;c++;
if(a==0)
update(b,c,0,1);
else if(a==1)
update(b,c,1,1);
else if(a==2)
Set_Rev(b,c,1);
else if(a==3)
printf("%d\n",Query1(b,c,1));
else
{
printf("%d\n",Query2(b,c,1));
}
}
}
return 0;
}
PS:誰能說明下上面的代碼錯在哪？