_Goodnight @ 2022-01-01 17:44:43
今天把这题搞完再AFO了
#include <bits/stdc++.h>
using namespace std;
#define lk k<<1
#define rk k<<1|1
#define mlr l+r>>1
typedef long long ll;
const int N = 1e5 + 5;
int a[N], num[4 * N], add[4 * N];
struct node {
int l, mid, r;
}mx[4 * N], mx0[4 * N];//储存最长1，最长0
void swap(int& a, int& b) { a = a + b; b = a - b; a = a - b; }
void pushup(int k, int l, int r) {
/*
mx[k].l = mx[lk].l; mx[k].r = mx[rk].r;
mx[k].mid = max(mx[lk].r + mx[rk].l, max(mx[lk].mid, mx[rk].mid));
mx0[k].l = mx0[lk].l; mx0[k].r = mx0[rk].r;
mx0[k].mid = max(mx0[lk].r + mx0[rk].l, max(mx0[lk].mid, mx0[rk].mid));
return;
*/
//但是这部分是错的。
}
void modify(int k, int l, int r, int v) {
//pushup(k, l, r);
if (v == -1) { num[k] = 0; mx[k].l = mx[k].mid = mx[k].r = 0; mx0[k].l = mx0[k].mid = mx0[k].r = (r - l + 1);
}
if (v == 1) { num[k] = (r - l + 1); mx[k].l = mx[k].mid = mx[k].r = (r - l + 1); mx0[k].l = mx0[k].mid = mx0[k].r = 0;
}
if (v == 2) {
num[k] = (r - l + 1) - num[k];
swap(mx[k].l, mx0[k].l);
swap(mx[k].mid, mx0[k].mid);
swap(mx[k].r, mx0[k].r);
}
add[k] = v;
}
void pushdown(int k, int l, int r, int mid) {
if (add[k] != 0) {
modify(lk, l, mid, add[k]);
modify(rk, mid + 1, r, add[k]);
add[k] = 0;
}
}
void build(int k, int l, int r) {
if (l == r) {
num[k] = a[l];
mx[k].l = mx[k].r = mx[k].mid = a[l];
mx0[k].l = mx0[k].r = mx0[k].mid = (1-a[l]);
return;
}
int mid = mlr;
build(lk, l, mid); build(rk, mid + 1, r);
num[k] = num[lk] + num[rk];
pushup(k, l, r);
}
void update(int k, int l, int r, int x, int y, int v) {
if (l > y || r < x) {
return;
}//-1->0 1->1 2->fanzhuan
if (l >= x && r <= y) {
modify(k, l, r, v);
return;
}
int mid = mlr;
pushdown(k, l, r, mid);
update(lk, l, mid, x, y, v); update(rk, mid + 1, r, x, y, v);
num[k] = num[lk] + num[rk];
pushup(k, l, r);
}
ll query(int k,int l,int r,int x,int y){
if (l > y || r < x)return 0;
if (l >= x && r <= y) {
return num[k];
}
int mid = mlr;
pushdown(k, l, r, mid);
return query(lk, l, mid, x, y) + query(rk, mid + 1, r, x, y);
}
node querymx(int k, int l, int r, int x, int y) {
if (l > y || r < x)return {0,0,0};
if (l >= x && r <= y) {
return mx[k];
}
int mid = mlr;
pushdown(k, l, r, mid);
node t1=querymx(lk, l, mid, x, y),t2=querymx(rk, mid + 1, r, x, y);
node tmp;
tmp.l = t1.l, tmp.r = t2.r;
tmp.mid = max(t1.r + t2.l, max(t1.mid, t2.mid));
return tmp;
}
int n, m,l,r,opt;
node t;
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
build(1, 1, n);
while (m--) {
scanf("%d%d%d", &opt, &l, &r);
l++, r++;
switch (opt){
case 0:
update(1, 1, n, l, r, -1);
break;
case 1:
update(1, 1, n, l, r, 1);
break;
case 2:
update(1, 1, n, l, r, 2);
break;
case 3:
printf("%d\n", query(1, 1, n, l, r));
break;
case 4:
t = querymx(1, 1, n, l, r);
printf("%d\n",max(t.mid,max(t.l,t.r)));
break;
default:
break;
}
}
}by zwx2007 @ 2022-01-01 17:53:33
struct Node{int w,b,lw,lb,rw,rb,lenw,lenb,sumw,sumb;}T[N];
inline Node Merge(Node s1,Node s2){
return (Node){max(max(s1.w,s2.w),s1.rw+s2.lw),max(max(s1.b,s2.b),s1.rb+s2.lb),
max(s1.lw,s1.lenw?s1.lenw+s2.lw:0),max(s1.lb,s1.lenb?s1.lenb+s2.lb:0),
max(s2.rw,s2.lenw?s1.rw+s2.lenw:0),max(s2.rb,s2.lenb?s1.rb+s2.lenb:0),
s1.lenw&&s2.lenw?s1.lenw+s2.lenw:0,s1.lenb&&s2.lenb?s1.lenb+s2.lenb:0,
s1.sumw+s2.sumw,s1.sumb+s2.sumb};
}
inline void Push_Up(int rt){T[rt]=Merge(T[rt<<1],T[rt<<1|1]);}你可以把它改成这样
by zwx2007 @ 2022-01-01 17:56:40
@_Goodnight
by _Goodnight @ 2022-01-01 18:10:47
@zwx2007 dalao太会压行了%%%
by _Goodnight @ 2022-01-01 18:14:56
max(s1.lw,s1.lenw?s1.lenw+s2.lw:0),max(s1.lb,s1.lenb?s1.lenb+s2.lb:0),
max(s2.rw,s2.lenw?s1.rw+s2.lenw:0),max(s2.rb,s2.lenb?s1.rb+s2.lenb:0),
s1.lenw&&s2.lenw?s1.lenw+s2.lenw:0,s1.lenb&&s2.lenb?s1.lenb+s2.lenb:0,这三行是什么意思（
by zwx2007 @ 2022-01-01 18:18:54
@_Goodnight 这题跟区间最大字段和模板不同在于此题的 sum 要看这段区间是否都为 1/0
应是：
s1.lw=max(s1.lw,s1.lenw?s1.lenw+s2.lw:0)（此处lenw为原来模板的sum）
而不是这样：
mx[k].l = mx[lk].l; mx[k].r = mx[rk].r;直接赋值
by zwx2007 @ 2022-01-01 18:21:27
w：mid
lw：lmax
rw：rmax
lenw：sum（不连续则为0）
0/1 情况为同理
by __zzy__ @ 2022-01-01 18:21:39
@_Goodnight
void push_up(ll p){
sum1[p]=sum1[p<<1]+sum1[p<<1|1],sum0[p]=sum0[p<<1]+sum0[p<<1|1];
lmax1[p]=(sum1[p<<1]==len[p<<1])?lmax1[p<<1|1]+sum1[p<<1]:lmax1[p<<1];
lmax0[p]=(sum0[p<<1]==len[p<<1])?lmax0[p<<1|1]+sum0[p<<1]:lmax0[p<<1];
rmax1[p]=(sum1[p<<1|1]==len[p<<1|1])?rmax1[p<<1]+sum1[p<<1|1]:rmax1[p<<1|1];
rmax0[p]=(sum0[p<<1|1]==len[p<<1|1])?rmax0[p<<1]+sum0[p<<1|1]:rmax0[p<<1|1];
mmax1[p]=max(max(mmax1[p<<1],mmax1[p<<1|1]),lmax1[p<<1|1]+rmax1[p<<1]);
mmax0[p]=max(max(mmax0[p<<1],mmax0[p<<1|1]),lmax0[p<<1|1]+rmax0[p<<1]);
}sum0，sum1是这段区间0和1的总个数，lmax0,lmax1是以这段区间的左端点为起点的最长的连续0，连续1的长度，rmax同理，以右端点为起点，mmax0,mmax1是这段区间的最长的连续0，连续1的长度
by zwx2007 @ 2022-01-01 18:26:54
@_Goodnight
我还是把全部给你看看吧好看懂 不然我自己都不知道我在写什么了
#include<cstdio>
#include<algorithm>
#define N 400005
using namespace std;
int n,m,a[N],x,y,opt;
struct Node{int w,b,lw,lb,rw,rb,lenw,lenb,sumw,sumb;}T[N];
struct SegmentTree{int lazy[N],rev[N],len[N];
#define mid (l+r>>1)
#define ls l,mid
#define rs mid+1,r
#define lson ls,rt<<1
#define rson rs,rt<<1|1
inline Node Merge(Node s1,Node s2){
return (Node){max(max(s1.w,s2.w),s1.rw+s2.lw),max(max(s1.b,s2.b),s1.rb+s2.lb),
max(s1.lw,s1.lenw?s1.lenw+s2.lw:0),max(s1.lb,s1.lenb?s1.lenb+s2.lb:0),
max(s2.rw,s2.lenw?s1.rw+s2.lenw:0),max(s2.rb,s2.lenb?s1.rb+s2.lenb:0),
s1.lenw&&s2.lenw?s1.lenw+s2.lenw:0,s1.lenb&&s2.lenb?s1.lenb+s2.lenb:0,
s1.sumw+s2.sumw,s1.sumb+s2.sumb};
}
inline void Push_Up(int rt){T[rt]=Merge(T[rt<<1],T[rt<<1|1]);}
void Build(int l=1,int r=n,int rt=1){lazy[rt]=-1,len[rt]=r-l+1;
if(l==r)return T[rt]=(Node){a[l],a[l]^1,a[l],a[l]^1,a[l],a[l]^1,a[l],a[l]^1,a[l],a[l]^1},void();
Build(lson),Build(rson);
Push_Up(rt);
}
inline void push_down(int rt,int opt){
if(!opt){lazy[rt]=0,rev[rt]=0;T[rt]=(Node){0,len[rt],0,len[rt],0,len[rt],0,len[rt],0,len[rt]};}
if(opt==1){lazy[rt]=1,rev[rt]=0;T[rt]=(Node){len[rt],0,len[rt],0,len[rt],0,len[rt],0,len[rt],0};}
if(opt==2){rev[rt]^=1,swap(T[rt].w,T[rt].b),swap(T[rt].lw,T[rt].lb),swap(T[rt].rw,T[rt].rb),
swap(T[rt].lenw,T[rt].lenb),swap(T[rt].sumw,T[rt].sumb);}
}
inline void Push_Down(int rt){
if(lazy[rt]!=-1)push_down(rt<<1,lazy[rt]),push_down(rt<<1|1,lazy[rt]);
if(rev[rt])push_down(rt<<1,2),push_down(rt<<1|1,2);lazy[rt]=-1,rev[rt]=0;
}
void Updata_Range(int L,int R,int k,int l=1,int r=n,int rt=1){
if(L<=l&&r<=R){push_down(rt,k);return;}Push_Down(rt);
if(L<=mid)Updata_Range(L,R,k,lson);
if(mid<R) Updata_Range(L,R,k,rson);
Push_Up(rt);
}
Node Query(int L,int R,int l=1,int r=n,int rt=1){
if(L<=l&&r<=R)return T[rt];Push_Down(rt);
if(L<=mid&&mid>=R)return Query(L,R,lson);
if(L>mid&&mid<R)return Query(L,R,rson);
return Merge(Query(L,R,lson),Query(L,R,rson));
}
#undef mid
#undef ls
#undef rs
#undef lson
#undef rson
}STree;
signed main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",a+i);
STree.Build();
while(m--){
scanf("%d%d%d",&opt,&x,&y);x++,y++;
if(opt<3)STree.Updata_Range(x,y,opt);
else{Node tmp=STree.Query(x,y);printf("%d\n",opt==3?tmp.sumw:tmp.w);}
}
return 0;
} by _Goodnight @ 2022-01-01 18:32:49
@zzy sum0是必要维护的吗
by zwx2007 @ 2022-01-01 18:33:48
sum0是为了判断区间是否全部为0，必要维护