只做正品的购物网站,南昌哪里做网站,wordpress andriod,医疗软件公司10强传送门:牛客
题目描述:
lxhgww最近收到了一个01序列#xff0c;序列里面包含了n个数#xff0c;这些数要么是0#xff0c;要么是1#xff0c;现在对于这个序列有五种变换操作和询问操作#xff1a;
0 a b 把[a, b]区间内的所有数全变成0
1 a b 把[a, b]区间内的所有数全…传送门:牛客
题目描述:
lxhgww最近收到了一个01序列序列里面包含了n个数这些数要么是0要么是1现在对于这个序列有五种变换操作和询问操作
0 a b 把[a, b]区间内的所有数全变成0
1 a b 把[a, b]区间内的所有数全变成1
2 a b 把[a,b]区间内的所有数全部取反也就是说把所有的0变成1把所有的1变成0
3 a b 询问[a, b]区间内总共有多少个1
4 a b 询问[a, b]区间内最多有多少个连续的1
对于每一种询问操作lxhgww都需要给出回答聪明的程序员们你们能帮助他吗
输入:
10 10
0 0 0 1 1 0 1 0 1 1
1 0 2
3 0 5
2 2 2
4 0 4
0 3 6
2 3 7
4 2 8
1 0 5
0 5 6
3 3 9
输出:
5
2
6
5此题维护方式较为麻烦,需要考虑多种因素,成功写出此题之后对线段树的理解将会大大上升!!
看完题目,我们会发现显然与区间的01数量有关,并且与连续性有关
考虑用lazy0/1lazy0/1lazy0/1来记录区间是否被置为0/10/10/1,用revrevrev来记录区间是否取反 用sum[0/1]sum[0/1]sum[0/1]来记录区间连续的0/10/10/1的数量,tottottot来记录区间111的数量
然后我们分析一个区间[l,r][l,r][l,r]的连续的1的数量该如何计算,我们发现可以分为3中情况,一种是该连续区间在左区间[l,mid][l,mid][l,mid],一种是该连续区间在[mid1,r][mid1,r][mid1,r],还有一种是该连续区间横跨区间[l,r][l,r][l,r].对于前两种情况,我们发现sum[0/1]sum[0/1]sum[0/1]已经记录下来了.对于最后一种情况,我们发现光靠上述变量无法维护.所以此时我们使用lmax[0/1]lmax[0/1]lmax[0/1]来记录从区间的前缀0/10/10/1的最大连续数量,rmax[0/1]rmax[0/1]rmax[0/1]来记录区间的后缀0/10/10/1的最大连续数量.那么此时对于第三种情况显然就是左子树的lmax[1]lmax[1]lmax[1]右子树的rmax[1]rmax[1]rmax[1]
现在我们来分析如何进行维护.
对于pushuppushuppushup:
tottottot可以直接维护.对于sum[]sum[]sum[],我们则需要枚举上述的三种情况来进行维护 对于lmaxlmaxlmax我们则需要判断连续区间是否能跨区间.也就是说连续的数字能否从左边界一直连续到右边界 对于rmaxrmaxrmax,与lmaxlmaxlmax同理
对于updateupdateupdate:
对[l,r][l,r][l,r]区间置0.此时我们的sum[],lazy,tot,lmax,rmaxsum[],lazy,tot,lmax,rmaxsum[],lazy,tot,lmax,rmax修改方式不难.需要注意的是,此时我们的修改会覆盖掉之前的revrevrev,也就是说无论之前是否进行过取反,此时我们的值都是0对[l,r][l,r][l,r]区间置1.此时我们的方法和上述相同对[l,r]进行取反.注意此时如果我们的区间有lazylazylazy,那就意味着我们的区间是相同的0/10/10/1,此时我们可以直接改lazylazylazy(这样做的好处是,当我们的子区间进行继承时,如果有父亲既有lazylazylazy,又有revrevrev,可以直接对lazylazylazy进行操作,忽略revrevrev).对于sum[],lazy,tot,lmax,rmaxsum[],lazy,tot,lmax,rmaxsum[],lazy,tot,lmax,rmax,我们直接调换0/10/10/1的值即可
对于pushdownpushdownpushdown:
修改的方式和updateupdateupdate相同,由父亲的lazylazylazy控制.需要注意的是如果有父亲既有lazylazylazy,又有revrevrev,可以直接对lazylazylazy进行操作,忽略revrevrev,因为在父亲的updateupdateupdate过程中,我们已经对lazylazylazy进行了相应操作
对于query1query1query1(找1的个数):
直接返回对应区间的tottottot即可
对于query2query2query2(找最长的连续1):
对于一个区间连续的1我们有三种情况(在之前分析过).对三种情况取一个maxmaxmax即可 下面是具体的代码部分:
#include bits/stdc.h
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt1
#define rs rt1|1
#define lson l,mid,rt1
#define rson mid1,r,rt1|1
inline ll read() {ll x0,w1;char chgetchar();for(;ch9||ch0;chgetchar()) if(ch-) w-1;for(;ch0ch9;chgetchar()) xx*10ch-0;return x*w;
}
#define maxn 1000000
const double eps1e-8;
#define int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
struct Segment_tree{int l,r;int rmax[2],lmax[2];//记录01前后缀长度int lazy,rev;//lazy记录是否被置0/1,rev记录是否被取反int sum[2];//sum1/0记录区间内最长的连续1/0的个数int tot;//记录区间内1的个数
}tree[maxn*4];
int n,m;int a[maxn];
void pushup(int rt) {int lenlstree[ls].r-tree[ls].l1;int lenrstree[rs].r-tree[rs].l1;tree[rt].tottree[ls].tottree[rs].tot;for(int i0;i1;i) {tree[rt].sum[i]max(tree[ls].sum[i],tree[rs].sum[i]);tree[rt].sum[i]max(tree[rt].sum[i],tree[ls].rmax[i]tree[rs].lmax[i]);if(tree[ls].lmax[i]lenls) tree[rt].lmax[i]lenlstree[rs].lmax[i];else tree[rt].lmax[i]tree[ls].lmax[i];if(tree[rs].rmax[i]lenrs) tree[rt].rmax[i]lenrstree[ls].rmax[i];else tree[rt].rmax[i]tree[rs].rmax[i];}
}
void build(int l,int r,int rt) {tree[rt].ll;tree[rt].rr;tree[rt].lazy-1;if(lr) {if(a[l]1) {tree[rt].rmax[1]tree[rt].lmax[1]1;tree[rt].sum[1]1;tree[rt].tot1;}else {tree[rt].rmax[0]tree[rt].lmax[0]1;tree[rt].sum[0]1;}return ;}int mid(lr)1;build(lson);build(rson);pushup(rt);
}
void change(int rt,int opt) {int lentree[rt].r-tree[rt].l1;if(opt0) {tree[rt].lazy0;tree[rt].tot0;tree[rt].sum[0]len;tree[rt].sum[1]0;tree[rt].rev0;tree[rt].lmax[0]len;tree[rt].lmax[1]0;tree[rt].rmax[0]len;tree[rt].rmax[1]0;}else if(opt1) {tree[rt].lazy1;tree[rt].totlen;tree[rt].sum[1]len;tree[rt].sum[0]0;tree[rt].rev0;tree[rt].lmax[1]len;tree[rt].lmax[0]0;tree[rt].rmax[1]len;tree[rt].rmax[0]0;}else {if(tree[rt].lazy!-1) {tree[rt].lazy^1;}tree[rt].rev^1;tree[rt].totlen-tree[rt].tot;swap(tree[rt].lmax[0],tree[rt].lmax[1]);swap(tree[rt].rmax[0],tree[rt].rmax[1]);swap(tree[rt].sum[0],tree[rt].sum[1]);}
}
void pushdown(int rt) {if(tree[rt].lazy!-1) {change(ls,tree[rt].lazy);change(rs,tree[rt].lazy);tree[rt].rev0;tree[rt].lazy-1;}else {change(ls,2);change(rs,2);tree[rt].rev0;tree[rt].lazy-1;}
}
void update(int l,int r,int rt,int opt) {if(tree[rt].lltree[rt].rr) {change(rt,opt);return ;}if(tree[rt].lazy!-1||tree[rt].rev) pushdown(rt);int mid(tree[rt].ltree[rt].r)1;if(rmid) update(l,r,ls,opt);else if(lmid) update(l,r,rs,opt);else update(l,mid,ls,opt),update(mid1,r,rs,opt);pushup(rt);
}
int query1(int l,int r,int rt) {if(tree[rt].lltree[rt].rr) {return tree[rt].tot;}if(tree[rt].lazy!-1||tree[rt].rev) pushdown(rt);int mid(tree[rt].ltree[rt].r)1;if(rmid) return query1(l,r,ls);else if(lmid) return query1(l,r,rs);else return query1(l,mid,ls)query1(mid1,r,rs);
}
int query2(int l,int r,int rt) {if(tree[rt].lltree[rt].rr) {return tree[rt].sum[1];} if(tree[rt].lazy!-1||tree[rt].rev) pushdown(rt);int mid(tree[rt].ltree[rt].r)1;if(rmid) return query2(l,r,ls);else if(lmid) return query2(l,r,rs);else {int ansmax(query2(l,mid,ls),query2(mid1,r,rs));int rmmin(tree[ls].rmax[1],mid-l1);int lmmin(tree[rs].lmax[1],r-mid);ansmax(ans,lmrm);return ans;}
}
int main() {nread();mread();for(int i1;in;i) a[i]read();build(1,n10,1);for(int i1;im;i) {int optread(),lread(),rread();l;r;if(opt0) {update(l,r,1,0);}else if(opt1) {update(l,r,1,1);}else if(opt2) {update(l,r,1,2);}else if(opt3) {printf(%d\n,query1(l,r,1));}else {printf(%d\n,query2(l,r,1));}}return 0;
}
