hdu 3397セグメントツリーセグメント更新
19214 ワード
この問題は本当にほほほとした.長い間叩いて、バグをたくさん調整して、0 1を出力して、解決しました.最後に逆を取ろうとすると、どうやってもバグがあり、
最後に大牛たちのブログを見ました.しかし、この問題は本当にさっぱりしていて、バグを調整するときに基本的に線分の木の過程を全部しました.
最後に大牛たちのブログを見ました.しかし、この問題は本当にさっぱりしていて、バグを調整するときに基本的に線分の木の過程を全部しました.
#include<stdio.h>
#include<string.h>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define maxn 100010
int mark[maxn<<2];//
int rsum[maxn<<2],lsum[maxn<<2],msum[maxn<<2];// 1
int numone[maxn<<2];// 1
int num[maxn<<2];//
int max(int x,int y)
{
return x>y?x:y;
}
int min(int x,int y)
{
return x<y?x:y;
}
void pushup(int l,int r,int rt)
{
int len=r-l+1;
int m=(l+r)/2;
if(mark[rt<<1]==mark[rt<<1|1])
mark[rt]=mark[rt<<1];// mark
else mark[rt]=-1;
if(mark[rt]==1)
{
msum[rt]=lsum[rt]=rsum[rt]=numone[rt]=len;// mark 1，
}
else if(mark[rt]==0)
{
numone[rt]=lsum[rt]=msum[rt]=rsum[rt]=0;//
}
else// mark -1
{
lsum[rt]=lsum[rt<<1];
rsum[rt]=rsum[rt<<1|1];
msum[rt]=max(msum[rt<<1],msum[rt<<1|1]);
numone[rt]=numone[rt<<1]+numone[rt<<1|1];
if(lsum[rt<<1]==m-l+1)lsum[rt]=lsum[rt<<1]+lsum[rt<<1|1];
if(rsum[rt<<1|1]==r-m)rsum[rt]=rsum[rt<<1|1]+rsum[rt<<1];
msum[rt]=max(msum[rt],lsum[rt<<1|1]+rsum[rt<<1]);
}
}
void pushdown(int l,int r,int rt)
{
if(mark[rt]!=-1)
{
mark[rt<<1]=mark[rt<<1|1]=mark[rt];
if(mark[rt]==1)
{
int len=r-l+1;
numone[rt<<1]=lsum[rt<<1]=rsum[rt<<1]=msum[rt<<1]=len-len/2;
numone[rt<<1|1]=lsum[rt<<1|1]=rsum[rt<<1|1]=msum[rt<<1|1]=len/2;
}
else
{
lsum[rt<<1]=rsum[rt<<1]=msum[rt<<1]=numone[rt<<1]=0;
lsum[rt<<1|1]=rsum[rt<<1|1]=msum[rt<<1|1]=numone[rt<<1|1]=0;
}
mark[rt]=-1;
}
}
void build(int l,int r,int rt)
{
if(l==r)
{
numone[rt]=lsum[rt]=rsum[rt]=msum[rt]=mark[rt]=num[l];
return;
}
int m=(l+r)/2;
build(lson);
build(rson);
pushup(l,r,rt);
}
void updata(int L,int R,int c,int l,int r,int rt)// 0 1
{
if(l>=L&&R>=r)
{
mark[rt]=c;
if(c==0)
{
lsum[rt]=rsum[rt]=msum[rt]=0;
numone[rt]=0;
}
else if(c==1)
{
lsum[rt]=rsum[rt]=msum[rt]=r-l+1;
numone[rt]=r-l+1;
}
return ;
}
pushdown(l,r,rt);
int m=(l+r)/2;
if(m>=L)
updata(L,R,c,lson);
if(R>m)
updata(L,R,c,rson);
pushup(l,r,rt);
}
void change(int L,int R,int l,int r,int rt)//
{
if(l>=L&&R>=r&&mark[rt]!=-1)
{
if(mark[rt]==1)
lsum[rt]=msum[rt]=rsum[rt]=numone[rt]=0;
else if(mark[rt]==0)
lsum[rt]=msum[rt]=rsum[rt]=numone[rt]=r-l+1;
mark[rt]^=1;
return;
}
pushdown(l,r,rt);
int m=(l+r)/2;
if(m>=L)
change(L,R,lson);
if(R>m)
change(L,R,rson);
pushup(l,r,rt);
}
int query(int L,int R,int l,int r,int rt)// 1
{
if(l>=L&&R>=r)
{
return numone[rt];
}
pushdown(l,r,rt);
int ret=0;
int m=(l+r)/2;
if(m>=L)
ret+=query(L,R,lson);
if(R>m)
ret+=query(L,R,rson);
return ret;
}
int queryone(int L,int R,int l,int r,int rt)// 1
{
if(L<=l&&R>=r)
{
return msum[rt];
}
pushdown(l,r,rt);
int ret=-99999999;
int m=(l+r)/2;
if(m>=L)
ret=max(ret,queryone(L,R,lson));
if(R>m)
ret=max(ret,queryone(L,R,rson));
ret=max(ret,min(m-L+1,rsum[rt<<1])+min(R-m,lsum[rt<<1|1]));//
return ret;
}
int main()
{
int i,n,m,t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
scanf("%d",&num[i]);
build(1,n,1);
int x,y,z;
while(m--)
{
scanf("%d%d%d",&x,&y,&z);
if(x==0)
updata(y+1,z+1,0,1,n,1);
else if(x==1)
updata(y+1,z+1,1,1,n,1);
else if(x==2)
change(y+1,z+1,1,n,1);
else if(x==3)
printf("%d
",query(y+1,z+1,1,n,1));
else if(x==4)
printf("%d
",queryone(y+1,z+1,1,n,1));
}
}
}