首页 > 代码库 > BZOJ 1858 SCOI2010 序列操作 线段树
BZOJ 1858 SCOI2010 序列操作 线段树
题目大意:给定一个01序列,提供三种操作:
0:把一段区间的所有元素都变成0
1:把一段区间的所有元素都变成1
2:把一段区间内的所有元素全都取反
3:查询一段区间内1的个数
4:查询一段区间内最长的一段连续的1
首先如果没有操作4这就是bitset的水题。。。多了这个,我们考虑线段树
线段树的每一个节点存修改标记和翻转标记,以及该区间的信息
虽然查询的信息都是1 但是我们要连0一起保存 因为翻转后0就变成了1 1就变成了0
区间信息包括:
左端点的元素
右端点的元素
左端点开始的最长的连续元素长度
右端点开始的最长的连续元素长度
最长的连续的1的长度
最长的连续的0的长度
更新时仔细讨论即可
注意当一个点被附加上修改标记的时候 要把翻转标记清零 下传时要先下传修改标记
这题是我写过的最长的线段树。。。树链剖分除外
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define M 100100 #define root 0,1,n #define ls tree[p].lson #define rs tree[p].rson using namespace std; struct seq{ int cnt; bool lflag,rflag; int lmax,rmax; int max[2]; seq(bool flag,int len) { cnt=flag?len:0; lflag=rflag=flag; lmax=rmax=len; max[!flag]=0; max[ flag]=len; } void flip(int x,int y) { lflag^=1; rflag^=1; swap(max[0],max[1]); cnt=(y-x+1)-cnt; } }; seq un(seq*s1,seq*s2,int x,int y) { seq re(0,0); int mid=x+y>>1; re.cnt=s1->cnt+s2->cnt; re.lflag=s1->lflag; re.rflag=s2->rflag; if( s1->lmax==(mid-x+1) && s1->lflag==s2->lflag ) re.lmax=(mid-x+1)+s2->lmax; else re.lmax=s1->lmax; if( s2->rmax==(y-mid) && s2->rflag==s1->rflag ) re.rmax=(y-mid)+s1->rmax; else re.rmax=s2->rmax; re.max[0]=max(s1->max[0],s2->max[0]); re.max[1]=max(s1->max[1],s2->max[1]); if(s1->rflag==s2->lflag) re.max[s1->rflag]=max(re.max[s2->lflag],s1->rmax+s2->lmax); return re; } struct abcd{ int lson,rson; int change_mark; bool flip_mark; seq *s; }tree[M<<1]; int n,m,tot; void Build_Tree(int p,int x,int y) { int mid=x+y>>1; tree[p].change_mark=-1; if(x==y) { scanf("%d",&mid); tree[p].s=new seq(mid,1); return ; } ls=++tot;rs=++tot; Build_Tree(ls,x,mid); Build_Tree(rs,mid+1,y); tree[p].s=new seq(0,0); *tree[p].s=un(tree[ls].s,tree[rs].s,x,y); } void push_down(int p,int x,int y) { int mid=x+y>>1; if(~tree[p].change_mark) { tree[ls].change_mark=tree[p].change_mark; tree[rs].change_mark=tree[p].change_mark; tree[ls].flip_mark=0; tree[rs].flip_mark=0; *tree[ls].s=seq(tree[p].change_mark,mid-x+1); *tree[rs].s=seq(tree[p].change_mark,y-mid); tree[p].change_mark=-1; } if(tree[p].flip_mark) { tree[p].flip_mark=0; tree[ls].flip_mark^=1; tree[rs].flip_mark^=1; tree[ls].s->flip(x,mid); tree[rs].s->flip(mid+1,y); } } void change(int p,int x,int y,int l,int r,int v) { int mid=x+y>>1; if(x==l&&y==r) { tree[p].change_mark=v; tree[p].flip_mark=0; *tree[p].s=seq(v,y-x+1); return ; } push_down(p,x,y); if(r<=mid) change(ls,x,mid,l,r,v); else if(l>mid) change(rs,mid+1,y,l,r,v); else change(ls,x,mid,l,mid,v),change(rs,mid+1,y,mid+1,r,v); *tree[p].s=un(tree[ls].s,tree[rs].s,x,y); } void flip(int p,int x,int y,int l,int r) { int mid=x+y>>1; if(x==l&&y==r) { tree[p].flip_mark^=1; tree[p].s->flip(x,y); return ; } push_down(p,x,y); if(r<=mid) flip(ls,x,mid,l,r); else if(l>mid) flip(rs,mid+1,y,l,r); else flip(ls,x,mid,l,mid),flip(rs,mid+1,y,mid+1,r); *tree[p].s=un(tree[ls].s,tree[rs].s,x,y); } int count(int p,int x,int y,int l,int r) { int mid=x+y>>1; if(x==l&&y==r) return tree[p].s->cnt; push_down(p,x,y); if(r<=mid) return count(ls,x,mid,l,r); if(l>mid) return count(rs,mid+1,y,l,r); return count(ls,x,mid,l,mid)+count(rs,mid+1,y,mid+1,r); } seq sequence(int p,int x,int y,int l,int r) { int mid=x+y>>1; if(x==l&&y==r) return *tree[p].s; push_down(p,x,y); if(r<=mid) return sequence(ls,x,mid,l,r); if(l>mid) return sequence(rs,mid+1,y,l,r); seq s1=sequence(ls,x,mid,l,mid); seq s2=sequence(rs,mid+1,y,mid+1,r); return un(&s1,&s2,x,y); } int main() { int i,p,x,y; cin>>n>>m; Build_Tree(root); for(i=1;i<=m;i++) { scanf("%d%d%d",&p,&x,&y); x++;y++; switch(p) { case 0: case 1:change(root,x,y,p);break; case 2:flip(root,x,y);break; case 3:printf("%d\n", count(root,x,y) );break; case 4:printf("%d\n", sequence(root,x,y).max[1] );break; } } return 0; }
BZOJ 1858 SCOI2010 序列操作 线段树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。