HDU-3397-Sequence operation
HDU-3397-Sequence operation
http://acm.hdu.edu.cn/showproblem.php?pid=3397
セグメントツリー、区間の複数の操作
http://acm.hdu.edu.cn/showproblem.php?pid=3397
セグメントツリー、区間の複数の操作
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
#define N 100010
struct cam
{
int x;
int y;
int len;
int cover;
}list[N*5];
int num[N];
int maxlen,curlen,r;
void updateinfo(int k)
{
if(list[k<<1].cover==list[k<<1|1].cover)
list[k].cover=list[k<<1].cover;
else
list[k].cover=-1;
}
void build(int k,int x,int y)
{
list[k].x=x;
list[k].y=y;
list[k].len=(y-x+1);
if(x==y)
{
list[k].cover=num[x];
return;
}
int mid=(x+y)/2;
build(k<<1,x,mid);
build(k<<1|1,mid+1,y);
updateinfo(k); //
}
void lazy(int k)
{
list[k<<1].cover=list[k].cover;
list[k<<1|1].cover=list[k].cover;
list[k].cover=-1;
}
void update(int k,int x,int y,int val)
{
if(list[k].cover==val)
return;
if(x==list[k].x&&list[k].y==y)
{
list[k].cover=val;
return;
}
if(list[k].cover!=-1)
lazy(k);
int mid=(list[k].x+list[k].y)/2;
if(x>mid)
update(k<<1|1,x,y,val);
else if(y<=mid)
update(k<<1,x,y,val);
else
{
update(k<<1,x,mid,val);
update(k<<1|1,mid+1,y,val);
}
}
void updatexor(int k,int x,int y)
{
if(x==list[k].x&&list[k].y==y&&list[k].cover!=-1)
{
list[k].cover^=1;
return;
}
if(list[k].cover!=-1)
lazy(k);
int mid=(list[k].x+list[k].y)/2;
if(x>mid)
updatexor(k<<1|1,x,y);
else if(y<=mid)
updatexor(k<<1,x,y);
else
{
updatexor(k<<1,x,mid);
updatexor(k<<1|1,mid+1,y);
}
}
int query(int k,int x,int y)
{
if(list[k].x==x&&list[k].y==y&&list[k].cover!=-1)
{
if(list[k].cover==0)
return 0;
else
return list[k].len;
}
if(list[k].cover!=-1)
lazy(k);
int mid=(list[k].x+list[k].y)/2;
if(x>mid)
return query(k<<1|1,x,y);
else if(y<=mid)
return query(k<<1,x,y);
else
return query(k<<1,x,mid)+query(k<<1|1,mid+1,y);
}
void querymaxlen(int k,int x,int y)
{
if(list[k].cover==0)
return;
if(x==list[k].x&&list[k].y==y&&list[k].cover==1)
{
if(x==r+1)
curlen+=list[k].len;
else
curlen=list[k].len;
if(curlen>maxlen)
maxlen=curlen;
r=list[k].y;
return;
}
if(list[k].cover!=-1)
lazy(k);
int mid=(list[k].x+list[k].y)/2;
if(x>mid)
return querymaxlen(k<<1|1,x,y);
else if(y<=mid)
return querymaxlen(k<<1,x,y);
else
{
querymaxlen(k<<1,x,mid);
querymaxlen(k<<1|1,mid+1,y);
}
}
int main()
{
int i,n,m,t,op,a,b;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(i=0;i<n;i++)
scanf("%d",&num[i]);
build(1,0,n-1);
while(m--)
{
scanf("%d%d%d",&op,&a,&b);
if(op==0)
update(1,a,b,0);
else if(op==1)
update(1,a,b,1);
else if(op==2)
updatexor(1,a,b);
else if(op==3)
printf("%d
",query(1,a,b));
else if(op==4)
{
maxlen=curlen=r=0;
querymaxlen(1,a,b);
printf("%d
",maxlen);
}
}
}
return 0;
}