首页 > 代码库 > HDU 3397 双lazy标记的问题
HDU 3397 双lazy标记的问题
题目大意
对一个只有0和1的序列，支持以下几种操作
1.将区间所有的值变成1
2.将区间所有的值变为0
3.将区间的0和1翻转（0变成1 1变成0）
4.求区间中1的个数
5.求区间连续最长的1的个数
http://vjudge.net/problem/viewProblem.action?id=14689
整整一下午。。。简直把自己修改的都要哭了
lazy标记有先后关系，如to[]覆盖后，那么rev[]翻转标记就应该重新赋为0
我们在pushdown中，是对孩子节点进行更新，那么更新的也是孩子节点的lazy标记，to[]覆盖的也是孩子节点的标记，对于还没用过的rev[cur]是不用变的，
这是它父亲传下来的，确保了正确性的
而在update函数中，每次给to[cur]进行了赋值，那么rev[cur]就要重置为0，因为我们这是对当前节点传入的标记，覆盖执行在当前节点上
PS：就是这破玩意改了我一下午的时间
void update(int cur,int x,int y,int s,int t,int op)
{
int mid=(x+y)/2,ls=cur<<1,rs=cur<<1|1;
if(x>=s&&y<=t){
if(op==0){
lc[cur][0]=rc[cur][0]=mc[cur][0]=y-x+1;
lc[cur][1]=rc[cur][1]=mc[cur][1]=0;
sum[cur]=0;
to[cur]=0,rev[cur]=0;
}
else if(op==1){
lc[cur][0]=rc[cur][0]=mc[cur][0]=0;
lc[cur][1]=rc[cur][1]=mc[cur][1]=y-x+1;
sum[cur]=y-x+1;
to[cur]=1,rev[cur]=0;
}
else if(op==2){
swap(lc[cur][0],lc[cur][1]);
swap(rc[cur][0],rc[cur][1]);
swap(mc[cur][0],mc[cur][1]);
sum[cur]=y-x+1-sum[cur];
rev[cur]^=1;
}
return;
}
push_down(cur,x,y);
if(mid>=s) update(L,s,t,op);
if(mid+1<=t) update(R,s,t,op);
push_up(cur,x,y);
}
总代码如下：
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 #define L ls,x,mid 6 #define R rs,mid+1,y 7 #define N 100010 8 int to[N<<2],rev[N<<2],lc[N<<2][2],rc[N<<2][2],mc[N<<2][2],sum[N<<2],X[N]; 9 void push_up(int cur,int x,int y) 10 { 11 int mid=(x+y)/2,ls=cur<<1,rs=cur<<1|1; 12 sum[cur]=sum[ls]+sum[rs]; 13 for(int i=0;i<2;i++){ 14 lc[cur][i]=lc[ls][i],rc[cur][i]=rc[rs][i]; 15 mc[cur][i]=max(mc[ls][i],mc[rs][i]); 16 mc[cur][i]=max(mc[cur][i],rc[ls][i]+lc[rs][i]); 17 if(lc[ls][i]==mid-x+1) lc[cur][i]=lc[ls][i]+lc[rs][i]; 18 if(rc[rs][i]==y-mid) rc[cur][i]=rc[ls][i]+rc[rs][i]; 19 } 20 } 21 void push_down(int cur,int x,int y) 22 { 23 int mid=(x+y)/2,ls=cur<<1,rs=cur<<1|1; 24 if(to[cur]!=-1){ 25 to[ls]=to[rs]=to[cur]; 26 rev[ls]=rev[rs]=0; 27 lc[ls][0]=rc[ls][0]=mc[ls][0]=to[cur]?0:mid-x+1; 28 lc[ls][1]=rc[ls][1]=mc[ls][1]=to[cur]?mid-x+1:0; 29 lc[rs][0]=rc[rs][0]=mc[rs][0]=to[cur]?0:y-mid; 30 lc[rs][1]=rc[rs][1]=mc[rs][1]=to[cur]?y-mid:0; 31 sum[ls]=to[cur]*(mid-x+1); 32 sum[rs]=to[cur]*(y-mid); 33 to[cur]=-1; 34 } 35 if(rev[cur]){ 36 rev[ls]^=1,rev[rs]^=1; 37 swap(lc[ls][0],lc[ls][1]); 38 swap(lc[rs][0],lc[rs][1]); 39 40 swap(rc[ls][0],rc[ls][1]); 41 swap(rc[rs][0],rc[rs][1]); 42 43 swap(mc[ls][0],mc[ls][1]); 44 swap(mc[rs][0],mc[rs][1]); 45 46 sum[ls]=mid-x+1-sum[ls]; 47 sum[rs]=y-mid-sum[rs]; 48 49 rev[cur]=0; 50 } 51 } 52 void build(int cur,int x,int y) 53 { 54 int mid=(x+y)/2,ls=cur<<1,rs=cur<<1|1; 55 to[cur]=-1,rev[cur]=0; 56 if(x==y){ 57 lc[cur][1]=rc[cur][1]=mc[cur][1]=sum[cur]=X[x]; 58 lc[cur][0]=rc[cur][0]=mc[cur][0]=X[x]^1; 59 //printf("%d\n",mc[cur][0]); 60 return; 61 } 62 build(L); 63 build(R); 64 push_up(cur,x,y); 65 } 66 void update(int cur,int x,int y,int s,int t,int op) 67 { 68 int mid=(x+y)/2,ls=cur<<1,rs=cur<<1|1; 69 if(x>=s&&y<=t){ 70 if(op==0){ 71 lc[cur][0]=rc[cur][0]=mc[cur][0]=y-x+1; 72 lc[cur][1]=rc[cur][1]=mc[cur][1]=0; 73 sum[cur]=0; 74 to[cur]=0,rev[cur]=0; 75 } 76 else if(op==1){ 77 lc[cur][0]=rc[cur][0]=mc[cur][0]=0; 78 lc[cur][1]=rc[cur][1]=mc[cur][1]=y-x+1; 79 sum[cur]=y-x+1; 80 to[cur]=1,rev[cur]=0; 81 } 82 else if(op==2){ 83 swap(lc[cur][0],lc[cur][1]); 84 swap(rc[cur][0],rc[cur][1]); 85 swap(mc[cur][0],mc[cur][1]); 86 sum[cur]=y-x+1-sum[cur]; 87 rev[cur]^=1; 88 } 89 return; 90 } 91 push_down(cur,x,y); 92 if(mid>=s) update(L,s,t,op); 93 if(mid+1<=t) update(R,s,t,op); 94 push_up(cur,x,y); 95 } 96 void query1(int cur,int x,int y,int s,int t,int &ans) 97 { 98 int mid=(x+y)/2,ls=cur<<1,rs=cur<<1|1; 99 if(x>=s&&y<=t){100 ans+=sum[cur];101 return;102 }103 push_down(cur,x,y);104 if(mid>=s) query1(L,s,t,ans);105 if(mid+1<=t) query1(R,s,t,ans);106 }107 int query2(int cur,int x,int y,int s,int t)108 {109 int mid=(x+y)/2,ls=cur<<1,rs=cur<<1|1;110 if(x>=s&&y<=t){111 return mc[cur][1];112 }113 push_down(cur,x,y);114 int ans=0;115 if(mid>=s) ans=max(ans,query2(L,s,t));116 if(mid+1<=t) ans=max(ans,query2(R,s,t));117 return max(ans,min(mid-s+1,rc[ls][1])+min(t-mid,lc[rs][1]));118 }119 int main()120 {121 int T,n,m,op,a,b;122 scanf("%d",&T);123 while(T--){124 scanf("%d%d",&n,&m);125 for(int i=1;i<=n;i++) scanf("%d",&X[i]);126 build(1,1,n);127 for(int i=0;i<m;i++){128 scanf("%d%d%d",&op,&a,&b);129 if(op==3){130 int ans=0;131 query1(1,1,n,a+1,b+1,ans);132 printf("%d\n",ans);133 }134 else if(op==4){135 printf("%d\n",query2(1,1,n,a+1,b+1));136 }137 else update(1,1,n,a+1,b+1,op);138 }139 }140 return 0;141 }