1858: [Scoi2010]序列操作
Time Limit: 10 Sec Memory Limit: 64 MBSubmit: 1011 Solved: 518
[Submit][Status]
Description
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都需要给出回答，聪明的程序员们，你们能帮助他吗？
Input
输入数据第一行包括2个数，n和m，分别表示序列的长度和操作数目 第二行包括n个数，表示序列的初始状态 接下来m行，每行3个数，op, a, b，（0<=op<=4，0<=a<=b
Output
对于每一个询问操作，输出一行，包括1个数，表示其对应的答案
Sample Input
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
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
Sample Output
5
2
6
5
2
6
5
HINT
对于30%的数据，1<=n, m<=1000
对于100%的数据，1<=n, m<=100000
看完题目发现了什么？
线段树基本操作对不对？一眼秒对不对？
感觉不难对不对？
于是默默的写了5kb……
区间覆盖，区间取反，区间1的个数（区间求和），区间最长连续子段……
全部都是线段树基本操作……但是和在一起就呵呵……
对每个节点记11个标记（被8个标记的qiaoranliqu大神鄙视了）
l,r,L0,L1,R0,R1(从左/右有几个0,1),len0,len1（最长连续0，最长连续1）
sum(不解释了),cov(-1为不覆盖，0,1表示覆盖为0,1)
F（取反）
覆盖还是好写的……全变成0/1
取反直接把记录的0,1的信息交换一下
我在想如果正式比赛太弱调不出来怎么办
代码（线段树写的太丑了……）
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <cstdlib>
#include <set>
#define ls(x) x<<1
#define rs(x) x<<1^1
#define maxn 100005
using namespace std;
struct node{int l,r,L0,L1,R0,R1,len0,len1,sum,cov,F;}tree[maxn*4];
int a[maxn],b,c,d,e,f,g,h,i,j,k,l,m,n,v,Ll,Rr;
inline int maxx(const int &a,const int &b){if (a>b)return a;return b;}
inline int minn(const int &a,const int &b){if (a<b)return a;return b;}
inline void Swap(int &a,int &b){int t=a;a=b;b=t;}
inline void down(int x){
int lx=ls(x),rx=rs(x);
if (tree[x].cov>-1){
if (tree[x].cov==0){
tree[lx].cov=0;tree[lx].F=0;
tree[lx].sum=0;
tree[lx].L1=tree[lx].R1=tree[lx].len1=0;
tree[lx].L0=tree[lx].R0=tree[lx].len0=tree[lx].r-tree[lx].l+1;
tree[rx].cov=0;tree[rx].F=0;
tree[rx].sum=0;
tree[rx].L1=tree[rx].R1=tree[rx].len1=0;
tree[rx].L0=tree[rx].R0=tree[rx].len0=tree[rx].r-tree[rx].l+1;
}
else{
tree[lx].cov=1;tree[lx].F=0;
tree[lx].sum=tree[lx].r-tree[lx].l+1;
tree[lx].L1=tree[lx].R1=tree[lx].len1=tree[lx].r-tree[lx].l+1;
tree[lx].L0=tree[lx].R0=tree[lx].len0=0;
tree[rx].cov=1;tree[rx].F=0;
tree[rx].sum=tree[rx].r-tree[rx].l+1;
tree[rx].L1=tree[rx].R1=tree[rx].len1=tree[rx].r-tree[rx].l+1;
tree[rx].L0=tree[rx].R0=tree[rx].len0=0;
}
}
if (tree[x].F){
tree[lx].F^=1;
tree[lx].sum=tree[lx].r-tree[lx].l+1-tree[lx].sum;
Swap(tree[lx].len0,tree[lx].len1);
Swap(tree[lx].L0,tree[lx].L1);
Swap(tree[lx].R0,tree[lx].R1);
tree[rx].F^=1;
tree[rx].sum=tree[rx].r-tree[rx].l+1-tree[rx].sum;
Swap(tree[rx].len0,tree[rx].len1);
Swap(tree[rx].L0,tree[rx].L1);
Swap(tree[rx].R0,tree[rx].R1);
}
tree[x].F=0;tree[x].cov=-1;
}
void getans(int x){
int l=tree[x].l,r=tree[x].r,mid=(l+r)>>1;
tree[x].sum=tree[ls(x)].sum+tree[rs(x)].sum;
tree[x].len1=maxx(tree[ls(x)].len1,tree[rs(x)].len1);
tree[x].len1=maxx(tree[x].len1,tree[ls(x)].R1+tree[rs(x)].L1);
tree[x].len0=maxx(tree[ls(x)].len0,tree[rs(x)].len0);
tree[x].len0=maxx(tree[x].len0,tree[ls(x)].R0+tree[rs(x)].L0);
if (tree[ls(x)].L1==mid-l+1)tree[x].L1=tree[ls(x)].L1+tree[rs(x)].L1; else tree[x].L1=tree[ls(x)].L1;
if (tree[rs(x)].R1==r-mid)tree[x].R1=tree[ls(x)].R1+tree[rs(x)].R1; else tree[x].R1=tree[rs(x)].R1;
if (tree[ls(x)].L0==mid-l+1)tree[x].L0=tree[ls(x)].L0+tree[rs(x)].L0; else tree[x].L0=tree[ls(x)].L0;
if (tree[rs(x)].R0==r-mid)tree[x].R0=tree[ls(x)].R0+tree[rs(x)].R0; else tree[x].R0=tree[rs(x)].R0;
}
void build(int x,int l,int r){
tree[x].l=l;tree[x].r=r;
if (l==r){
tree[x].sum=a[l];
tree[x].L1=a[l]; tree[x].R1=a[l]; tree[x].len1=a[l];
tree[x].L0=1-a[l]; tree[x].R0=1-a[l]; tree[x].len0=1-a[l];
tree[x].cov=-1; tree[x].F=0;
return;
}
int mid=(l+r)>>1;
build(ls(x),l,mid);
build(rs(x),mid+1,r);
tree[x].cov=-1;
getans(x);
}
void cover(int x,int LL,int RR){
if (tree[x].l==LL&&tree[x].r==RR){
if (v==0){
tree[x].cov=v;tree[x].F=0;
tree[x].sum=0;
tree[x].L1=tree[x].R1=tree[x].len1=0;
tree[x].L0=tree[x].R0=tree[x].len0=tree[x].r-tree[x].l+1;
}
else{
tree[x].cov=v;tree[x].F=0;
tree[x].sum=tree[x].r-tree[x].l+1;
tree[x].L1=tree[x].R1=tree[x].len1=tree[x].r-tree[x].l+1;
tree[x].L0=tree[x].R0=tree[x].len0=0;
}
return;
}
int l=tree[x].l,r=tree[x].r,mid=(l+r)>>1;
down(x);
if (RR<=mid)cover(ls(x),LL,RR);
else if (LL>mid)cover(rs(x),LL,RR);
else {cover(ls(x),LL,mid);cover(rs(x),mid+1,RR);}
getans(x);
}
void fan(int x,int LL,int RR){
if (tree[x].l==LL&&tree[x].r==RR){
tree[x].F^=1;
tree[x].sum=RR-LL+1-tree[x].sum;
Swap(tree[x].len0,tree[x].len1);
Swap(tree[x].L0,tree[x].L1);
Swap(tree[x].R0,tree[x].R1);
return;
}
int l=tree[x].l,r=tree[x].r,mid=(l+r)>>1;
down(x);
if (RR<=mid)fan(ls(x),LL,RR);
else if (LL>mid)fan(rs(x),LL,RR);
else {fan(ls(x),LL,mid);fan(rs(x),mid+1,RR);}
getans(x);
}
int ask(int x,int LL,int RR){
if (tree[x].l==LL&&tree[x].r==RR){
return tree[x].sum;
}
down(x);
int l=tree[x].l,r=tree[x].r,mid=(l+r)>>1;
if (RR<=mid)return ask(ls(x),LL,RR);
else if (LL>mid)return ask(rs(x),LL,RR);
else return ask(ls(x),LL,mid)+ask(rs(x),mid+1,RR);
}
int Len(int x,int LL,int RR){
if (tree[x].l==LL&&tree[x].r==RR){
return tree[x].len1;
}
down(x);
int l=tree[x].l,r=tree[x].r,mid=(l+r)>>1;
if (RR<=mid)return Len(ls(x),LL,RR);
else if (LL>mid)return Len(rs(x),LL,RR);
else {
int L=0,R=0,K=0;
K=maxx(Len(ls(x),LL,mid),Len(rs(x),mid+1,RR));
L=minn(tree[ls(x)].R1,mid-LL+1);
R=minn(tree[rs(x)].L1,RR-mid);
return maxx(K,L+R);
}
}
int main(){
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)scanf("%d",&a[i]);
build(1,1,n);
for(;m;m--){
scanf("%d%d%d",&v,&Ll,&Rr);Ll++;Rr++;
if (v==0){
cover(1,Ll,Rr);
}
if (v==1){
cover(1,Ll,Rr);
}
if (v==2){
fan(1,Ll,Rr);
}
if (v==3){
printf("%d\n",ask(1,Ll,Rr));
}
if (v==4){
printf("%d\n",Len(1,Ll,Rr));
}
}
return 0;
}
2014年6月23日 11:44
orzorzorz
2022年9月11日 15:49
Advised to everyone can contact the class teacher to get important questions for all lessons and topics of EVS. Every Telugu Medium, English Medium and Urdu Medium student of the State Board can download the AP 10th Class EVS Model Paper 2023 Pdf with answers for term-1 & term-2 exams of SA-1, SA-2 and other exams of the board. AP SSC Evs Question Paper Environmental Education is one of the most important subjects and it’s a part of Science. School Education Department and various leading private school teaching staff have designed and suggested the practice question paper for all Part-A, Part-B, Part-C, and Part-D questions of SA-1, SA-2, FA-1, FA-2, FA-3, FA-4 and Assignments.
2024年1月13日 22:40
I finally found great post here.I will get back here. I just added your blog to my bookmark sites. thanks.Quality posts is the crucial to invite the visitors to visit the web page, that's what this web page is providing