首页 > 代码库 > hdu3397 线段树
hdu3397 线段树
这道题关键点在于标记 延时的先后
pre0 pre1为每个节点前驱连续最大的0 1
after0 after1 为每个节点后驱连续最大的0 1
Max0 Max1为每个节点连最大连续0 1
count0 count1为每个节点0 1 个数
flash0 flash1为该节点子节点转换 置0或1 的标记
****应为转换对置01没影响 所以在判断时线判断flash1 再判断flash0 在进行转换操作时 是对是不会对flash1有影响的 而在值01时 是会对flash1有影响的 具体看代码
#include<stdio.h> #include<iostream> #include<string.h> using namespace std; #define LL(x) (x<<1) #define RR(x) ((x<<1)|1) struct node { int pre0,pre1,after0,after1; int Max1,Max0; int count1,count0; int flash1,flash2; }num[4*100000]; int max(int a,int b) { return a>b?a:b; } int min(int a,int b) { return a<b?a:b; } int deal(int L,int R,int mark) { num[mark].pre0=num[mark].after0=num[mark].Max0=num[mark].flash1=num[mark].count0=0; num[mark].pre1=num[mark].after1=num[mark].Max1=num[mark].count1=R-L+1; num[mark].flash2=-1; if(L==R) return 0; int mid=(L+R)/2; deal(L,mid,LL(mark)); deal(mid+1,R,RR(mark)); return 0; } int change1(int a) { int k=num[a].pre0; num[a].pre0=num[a].pre1; num[a].pre1=k; k=num[a].after0; num[a].after0=num[a].after1; num[a].after1=k; k=num[a].count1; num[a].count1=num[a].count0; num[a].count0=k; k=num[a].Max1; num[a].Max1=num[a].Max0; num[a].Max0=k; num[a].flash1=!num[a].flash1; //num[a].flash2=-1; return 0; } int change2(int L,int R,int a,int b) { if(b==0) { num[a].pre0=num[a].after0=num[a].Max0=num[a].count0=R-L+1; num[a].pre1=num[a].after1=num[a].Max1=num[a].count1=0; } else { num[a].pre0=num[a].after0=num[a].Max0=num[a].count0=0; num[a].pre1=num[a].after1=num[a].Max1=num[a].count1=R-L+1; } num[a].flash2=b; num[a].flash1=0; return 0; } int update(int L,int R,int left,int right,int mark,int k) { if(L==left&&R==right) { if(k==2) change1(mark); else change2(L,R,mark,k); return 0; } int mid=(L+R)/2; if(num[mark].flash2>=0) { change2(L,mid,LL(mark),num[mark].flash2); change2(mid+1,R,RR(mark),num[mark].flash2); num[mark].flash2=-1; } if(num[mark].flash1) { change1(LL(mark)); change1(RR(mark)); num[mark].flash1=0; } if(right<=mid) { update(L,mid,left,right,LL(mark),k); } else if(left>mid) { update(mid+1,R,left,right,RR(mark),k); } else { update(L,mid,left,mid,LL(mark),k); update(mid+1,R,mid+1,right,RR(mark),k); } num[mark].Max0=max(num[LL(mark)].Max0,num[RR(mark)].Max0); num[mark].Max0=max(num[LL(mark)].after0+num[RR(mark)].pre0,num[mark].Max0); num[mark].Max1=max(num[LL(mark)].Max1,num[RR(mark)].Max1); num[mark].Max1=max(num[LL(mark)].after1+num[RR(mark)].pre1,num[mark].Max1); num[mark].pre0=num[LL(mark)].pre0; if(num[LL(mark)].pre0==mid-L+1) num[mark].pre0+=num[RR(mark)].pre0; num[mark].pre1=num[LL(mark)].pre1; if(num[LL(mark)].pre1==mid-L+1) num[mark].pre1+=num[RR(mark)].pre1; num[mark].after0=num[RR(mark)].after0; if(num[RR(mark)].after0==R-mid) num[mark].after0+=num[LL(mark)].after0; num[mark].after1=num[RR(mark)].after1; if(num[RR(mark)].after1==R-mid) num[mark].after1+=num[LL(mark)].after1; num[mark].count1=num[LL(mark)].count1+num[RR(mark)].count1; num[mark].count0=num[LL(mark)].count0+num[RR(mark)].count0; return 0; } int find1(int L,int R,int left,int right,int mark) { if(L==left&&R==right) { return num[mark].Max1; } int mid=(R+L)/2; if(num[mark].flash2>=0) { change2(L,mid,LL(mark),num[mark].flash2); change2(mid+1,R,RR(mark),num[mark].flash2); num[mark].flash2=-1; } if(num[mark].flash1) { change1(LL(mark)); change1(RR(mark)); num[mark].flash1=0; } if(right<=mid) { return find1(L,mid,left,right,LL(mark)); } else if(left>mid) { return find1(mid+1,R,left,right,RR(mark)); } else { int t1=find1(L,mid,left,mid,LL(mark)); int t2=find1(mid+1,R,mid+1,right,RR(mark)); return max(max(min(t1,num[LL(mark)].after1)+min(num[RR(mark)].pre1,t2),t1),t2); } } int find2(int L,int R,int left,int right,int mark) { if(L==left&&R==right) { return num[mark].count1; } int mid=(L+R)/2; if(num[mark].flash2>=0) { change2(L,mid,LL(mark),num[mark].flash2); change2(mid+1,R,RR(mark),num[mark].flash2); num[mark].flash2=-1; } if(num[mark].flash1) { change1(LL(mark)); change1(RR(mark)); num[mark].flash1=0; } if(right<=mid) { return find2(L,mid,left,right,LL(mark)); } else if(left>mid) { return find2(mid+1,R,left,right,RR(mark)); } else return find2(L,mid,left,mid,LL(mark))+find2(mid+1,R,mid+1,right,RR(mark)); } int main() { int n,m,i,j,a,b,c,T; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); n-=1; deal(0,n,1); for(i=0;i<=n;i++) { scanf("%d",&a); if(a==0) update(0,n,i,i,1,2); } for(i=1;i<=m;i++) { scanf("%d%d%d",&a,&b,&c); if(a<3) { update(0,n,b,c,1,a); } else { if(a==3) printf("%d\n",find2(0,n,b,c,1)); else printf("%d\n",find1(0,n,b,c,1)); } } } return 0; }
hdu3397 线段树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。