wuhuhuhuhuhuhu @ 2024-10-25 14:55:13
#include<bits/stdc++.h>
using namespace std;
struct kuai {
long long zhi=0;
long long l=0;
long long r=0;
long long llian1=0;
long long rlian1=0;
long long lian1=0;
long long llian0=0;
long long rlian0=0;
long long lian0=0;
};
long long meikuai;
kuai block[1000005];
long long c[1000005];
long long lan[1000005];
vector<long long> lan0(1000005,2);
inline long long getkuai(long long x) {
return (x-1)/meikuai+1;
}
inline void push(long long x) {
for(long long n=block[x].l; n<=block[x].r; n++) {
if(lan0[x]==2) c[n]=(c[n]^lan[x]);
else if(lan0[x]==0) c[n]=(c[n]&0);
else if(lan0[x]==1) c[n]=(c[n]|1);
}
lan0[x]=2;
lan[x]=0;
}
inline void weihu(long long x) {
push(x);
long long cnt=0;
for(long long i=block[x].l; i<=block[x].r; i++) {
if(c[i]==1) {
block[x].lian0=max(block[x].lian0,cnt);
cnt=0;
} else cnt++;
}
block[x].lian0=max(block[x].lian0,cnt);
cnt=0;
for(long long i=block[x].l; i<=block[x].r; i++) {
if(c[i]==0) {
block[x].lian1=max(block[x].lian1,cnt);
cnt=0;
} else cnt++;
}
block[x].lian1=max(block[x].lian1,cnt);
cnt=0;
long long f0=0,f1=0,cnt1=0;
for(long long i=block[x].l; i<=block[x].r; i++) {
if(c[i]==0) {
if(f0==0) cnt++;
block[x].llian1=max(block[x].llian1,cnt1);
cnt1=0;
f1=1;
}
if(c[i]==1) {
if(f1==0) cnt1++;
block[x].llian0=max(block[x].llian0,cnt);
cnt=0;
f0=1;
}
if(f0==1&&f1==1) break;
}
block[x].llian1=max(block[x].llian1,cnt1);
block[x].llian0=max(block[x].llian0,cnt);
f0=0,f1=0,cnt1=0,cnt=0;
for(long long i=block[x].r; i>=block[x].l; i--) {
if(c[i]==0) {
if(f0==0) cnt++;
block[x].rlian1=max(block[x].rlian1,cnt1);
cnt1=0;
f1=1;
}
if(c[i]==1) {
if(f1==0) cnt1++;
block[x].rlian0=max(cnt,block[x].rlian0);
cnt=0;
f0=1;
}
if(f0==1&&f1==1) break;
}
block[x].rlian1=max(block[x].rlian1,cnt1);
block[x].rlian0=max(cnt,block[x].rlian0);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
long long a,b;
cin>>a>>b;
for(long long i=1; i<=a; i++) {
cin>>c[i];
}
meikuai=(long long)sqrt(a);
long long sum=0,cnt=1;
for(long long i=1; i<=a; i++) {
sum+=c[i];
if(i%meikuai==0) {
block[cnt].zhi=sum;
block[cnt].l=block[cnt-1].r+1;
block[cnt].r=i;
sum=0;
weihu(cnt);
cnt++;
}
}
if(a%((long long)sqrt(a))!=0) {
block[cnt].zhi=sum;
block[cnt].l=block[cnt-1].r+1;
block[cnt].r=a;
}
weihu(cnt);
long long ji;
long long quel,quer,lid,rid;
for(long long i=0; i<b; i++) {
cin>>ji;
cin>>quel>>quer;
quel++;
quer++;
lid=getkuai(quel);
rid=getkuai(quer);
if(ji==0) {
if(lid==rid) {
for(long long n=quel; n<=quer; n++) {
if(c[n]==1) {
block[lid].zhi--;
c[n]=0;
}
}
weihu(lid);
} else {
for(long long n=quel; n<=block[lid].r; n++) {
if(c[n]==1) {
block[lid].zhi--;
c[n]=0;
}
}
weihu(lid);
for(long long n=lid+1; n<rid; n++) {
block[n].zhi=0;
block[n].lian0=block[n].r-block[n].l+1;
block[n].llian0=block[n].lian0;
block[n].rlian0=block[n].lian0;
block[n].lian1=0;
block[n].llian1=0;
block[n].rlian1=0;
lan0[n]=0;
lan[n]=0;
}
for(long long n=block[rid].l; n<=quer; n++) {
if(c[n]==1) {
block[rid].zhi--;
c[n]=0;
}
}
weihu(rid);
}
}
if(ji==1) {
if(lid==rid) {
for(long long n=quel; n<=quer; n++) {
if(c[n]==0) {
block[lid].zhi++;
c[n]=1;
}
}
weihu(lid);
} else {
for(long long n=quel; n<=block[lid].r; n++) {
if(c[n]==0) {
block[lid].zhi++;
c[n]=1;
}
}
weihu(lid);
for(long long n=lid+1; n<rid; n++) {
lan0[n]=1;
block[n].zhi=block[n].r-block[n].l+1;
lan[n]=0;
block[n].lian1=block[n].r-block[n].l+1;
block[n].llian1=block[n].lian1;
block[n].rlian1=block[n].lian1;
block[n].lian0=0;
block[n].llian0=0;
block[n].rlian0=0;
}
for(long long n=block[rid].l; n<=quer; n++) {
if(c[n]==0) {
block[rid].zhi++;
c[n]=1;
}
}
weihu(rid);
}
}
if(ji==2) {
if(lid==rid) {
for(long long n=quel; n<=quer; n++) {
if(c[n]==0) {
block[lid].zhi++;
c[n]=1;
} else if(c[n]==1) {
block[lid].zhi--;
c[n]=0;
}
}
weihu(lid);
} else {
for(long long n=quel; n<=block[lid].r; n++) {
if(c[n]==0) {
block[lid].zhi++;
c[n]=1;
} else if(c[n]==1) {
block[lid].zhi--;
c[n]=0;
}
}
weihu(lid);
for(long long n=lid+1; n<rid; n++) {
if(lan0[n]==2) lan[n]=lan[n]^1;
else lan0[n]=lan0[n]^1;
swap(block[n].lian0,block[n].lian1);
swap(block[n].llian0,block[n].llian1);
swap(block[n].rlian0,block[n].rlian1);
}
for(long long n=block[rid].l; n<=quer; n++) {
if(c[n]==0) {
block[rid].zhi++;
c[n]=1;
} else if(c[n]==1) {
block[rid].zhi--;
c[n]=0;
}
}
weihu(rid);
}
}
if(ji==3) {
sum=0;
if(lid==rid) {
for(long long n=quel; n<=quer; n++) {
if(lan0[lid]==2) sum+=(c[n]^lan[lid]);
else if(lan0[lid]==0) sum+=(c[n]&lan0[lid]);
else if(lan0[lid]==1) sum+=(c[n]|lan0[lid]);
}
} else {
for(long long n=quel; n<=block[lid].r; n++) {
if(lan0[lid]==2) sum+=(c[n]^lan[lid]);
else if(lan0[lid]==0) sum+=(c[n]&lan0[lid]);
else if(lan0[lid]==1) sum+=1;
}
for(long long n=lid+1; n<rid; n++) {
if(lan0[n]==2) {
if(lan[n]==1) sum+=block[n].r-block[n].l+1-block[n].zhi;
else sum+=block[n].zhi;
} else {
if(lan0[n]==1) sum+=block[n].r-block[n].l+1;
}
}
for(long long n=block[rid].l; n<=quer; n++) {
if(lan0[rid]==2) sum+=(c[n]^lan[rid]);
else if(lan0[rid]==0) sum+=(c[n]&lan0[rid]);
else if(lan0[rid]==1) sum+=1;
}
}
cout<<sum<<endl;
}
if(ji==4) {
weihu(lid);
sum=0;
cnt=0;
if(lid==rid) {
for(long long n=quel; n<=quer; n++) {
if(c[n]==0) {
sum=max(sum,cnt);
cnt=0;
} else cnt++;
}
sum=max(sum,cnt);
} else {
weihu(rid);
sum=max(min(block[lid].rlian1,block[lid].r-quel+1)+min(block[lid+1].llian1,quer-block[lid+1].l+1),sum);
for(long long n=lid+1; n<rid; n++) {
sum=max(block[n].rlian1+min(quer-block[n+1].l+1,block[n+1].llian1),max(block[n].lian1,sum));
}
}
cout<<sum<<endl;
}
}
return 0;
}by wjr_jok @ 2024-10-25 15:11:01
@wuhuhuhuhuhuhu 思路？
by wuhuhuhuhuhuhu @ 2024-10-25 15:28:51
@wjr_jok 维护每块包含左端点的最长0/1 包含右端点的最长0/1 块内最长0/1
by wjr_jok @ 2024-10-25 15:44:18
@wuhuhuhuhuhuhu 能不能注释一下每一步的操作和变量的作用
by wuhuhuhuhuhuhu @ 2024-10-25 15:49:27
@wjr_jok 稍等
by wuhuhuhuhuhuhu @ 2024-10-25 16:03:30
#include<bits/stdc++.h>
using namespace std;
struct kuai {
long long zhi=0;//每块1的个数
long long l=0;
long long r=0;
long long llian1=0;//包含左端点连续1
long long rlian1=0;//包含右端点连续1
long long lian1=0;//块内最长连续1
long long llian0=0; //包含左端点连续0
long long rlian0=0;//包含右端点连续0
long long lian0=0;//块内最长连续0
};
long long meikuai;//每块长度
kuai block[1000005]; //块
long long c[1000005];//原数组
long long lan[1000005];//反转标记
vector<long long> lan0(1000005,2);//覆盖标记
inline long long getkuai(long long x) {
return (x-1)/meikuai+1;
}
inline void push(long long x) {
for(long long n=block[x].l; n<=block[x].r; n++) { //下放标记
if(lan0[x]==2) c[n]=(c[n]^lan[x]);
else if(lan0[x]==0) c[n]=(c[n]&0);
else if(lan0[x]==1) c[n]=(c[n]|1);
}
lan0[x]=2;
lan[x]=0;
}
inline void weihu(long long x) {
push(x);
long long cnt=0;
for(long long i=block[x].l; i<=block[x].r; i++) { //计算块内最长连续0
if(c[i]==1) {
block[x].lian0=max(block[x].lian0,cnt);
cnt=0;
} else cnt++;
}
block[x].lian0=max(block[x].lian0,cnt);
cnt=0;
for(long long i=block[x].l; i<=block[x].r; i++) { //计算块内最长连续1
if(c[i]==0) {
block[x].lian1=max(block[x].lian1,cnt);
cnt=0;
} else cnt++;
}
block[x].lian1=max(block[x].lian1,cnt);
cnt=0;
long long f0=0,f1=0,cnt1=0;
for(long long i=block[x].l; i<=block[x].r; i++) {//计算包含左端点连续1,0
if(c[i]==0) {
if(f0==0) cnt++;
block[x].llian1=max(block[x].llian1,cnt1);
cnt1=0;
f1=1;
}
if(c[i]==1) {
if(f1==0) cnt1++;
block[x].llian0=max(block[x].llian0,cnt);
cnt=0;
f0=1;
}
if(f0==1&&f1==1) break;
}
block[x].llian1=max(block[x].llian1,cnt1);
block[x].llian0=max(block[x].llian0,cnt);
f0=0,f1=0,cnt1=0,cnt=0;
for(long long i=block[x].r; i>=block[x].l; i--) { //计算包含右端点连续1,0
if(c[i]==0) {
if(f0==0) cnt++;
block[x].rlian1=max(block[x].rlian1,cnt1);
cnt1=0;
f1=1;
}
if(c[i]==1) {
if(f1==0) cnt1++;
block[x].rlian0=max(cnt,block[x].rlian0);
cnt=0;
f0=1;
}
if(f0==1&&f1==1) break;
}
block[x].rlian1=max(block[x].rlian1,cnt1);
block[x].rlian0=max(cnt,block[x].rlian0);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
long long a,b;
cin>>a>>b;
for(long long i=1; i<=a; i++) {
cin>>c[i];
}
meikuai=(long long)sqrt(a);
long long sum=0,cnt=1;
for(long long i=1; i<=a; i++) { //预处理每块
sum+=c[i];
if(i%meikuai==0) {
block[cnt].zhi=sum;
block[cnt].l=block[cnt-1].r+1;
block[cnt].r=i;
sum=0;
weihu(cnt);
cnt++;
}
}
if(a%((long long)sqrt(a))!=0) {
block[cnt].zhi=sum;
block[cnt].l=block[cnt-1].r+1;
block[cnt].r=a;
}
weihu(cnt);
long long ji;
long long quel,quer,lid,rid;
for(long long i=0; i<b; i++) {
cin>>ji;
cin>>quel>>quer;
quel++;
quer++;
lid=getkuai(quel);
rid=getkuai(quer);
if(ji==0) {
if(lid==rid) {
for(long long n=quel; n<=quer; n++) { //在同一块暴力,下同
if(c[n]==1) {
block[lid].zhi--;
c[n]=0;
}
}
weihu(lid);
} else {
for(long long n=quel; n<=block[lid].r; n++) {
if(c[n]==1) {
block[lid].zhi--;
c[n]=0;
}
}
weihu(lid);
for(long long n=lid+1; n<rid; n++) {
block[n].zhi=0;
block[n].lian0=block[n].r-block[n].l+1;//中间块覆盖标记变为0，去掉反转标记
block[n].llian0=block[n].lian0;
block[n].rlian0=block[n].lian0;
block[n].lian1=0;
block[n].llian1=0;
block[n].rlian1=0;
lan0[n]=0;
lan[n]=0;
}
for(long long n=block[rid].l; n<=quer; n++) {
if(c[n]==1) {
block[rid].zhi--;
c[n]=0;
}
}
weihu(rid);
}
}
if(ji==1) {
if(lid==rid) {
for(long long n=quel; n<=quer; n++) {
if(c[n]==0) {
block[lid].zhi++;
c[n]=1;
}
}
weihu(lid);
} else {
for(long long n=quel; n<=block[lid].r; n++) {
if(c[n]==0) {
block[lid].zhi++;
c[n]=1;
}
}
weihu(lid);
for(long long n=lid+1; n<rid; n++) {
lan0[n]=1;
block[n].zhi=block[n].r-block[n].l+1;//中间块覆盖标记变为1，去掉反转标记
lan[n]=0;
block[n].lian1=block[n].r-block[n].l+1;
block[n].llian1=block[n].lian1;
block[n].rlian1=block[n].lian1;
block[n].lian0=0;
block[n].llian0=0;
block[n].rlian0=0;
}
for(long long n=block[rid].l; n<=quer; n++) {
if(c[n]==0) {
block[rid].zhi++;
c[n]=1;
}
}
weihu(rid);
}
}
if(ji==2) {
if(lid==rid) {
for(long long n=quel; n<=quer; n++) {
if(c[n]==0) {
block[lid].zhi++;
c[n]=1;
} else if(c[n]==1) {
block[lid].zhi--;
c[n]=0;
}
}
weihu(lid);
} else {
for(long long n=quel; n<=block[lid].r; n++) {
if(c[n]==0) {
block[lid].zhi++;
c[n]=1;
} else if(c[n]==1) {
block[lid].zhi--;
c[n]=0;
}
}
weihu(lid);
for(long long n=lid+1; n<rid; n++) {
if(lan0[n]==2) lan[n]=lan[n]^1;//中间块覆盖标记反转，无覆盖标记就反转标记反转
else lan0[n]=lan0[n]^1;
swap(block[n].lian0,block[n].lian1);//块内最长连续1与最长连续0交换
swap(block[n].llian0,block[n].llian1);//包含左端点连续1的个数变成了连续0的个数
swap(block[n].rlian0,block[n].rlian1);//右端点同理
}
for(long long n=block[rid].l; n<=quer; n++) {
if(c[n]==0) {
block[rid].zhi++;
c[n]=1;
} else if(c[n]==1) {
block[rid].zhi--;
c[n]=0;
}
}
weihu(rid);
}
}
if(ji==3) {
sum=0;
if(lid==rid) {
for(long long n=quel; n<=quer; n++) {
if(lan0[lid]==2) sum+=(c[n]^lan[lid]);
else if(lan0[lid]==0) sum+=(c[n]&lan0[lid]);
else if(lan0[lid]==1) sum+=(c[n]|lan0[lid]);
}
} else {
for(long long n=quel; n<=block[lid].r; n++) {
if(lan0[lid]==2) sum+=(c[n]^lan[lid]);
else if(lan0[lid]==0) sum+=(c[n]&lan0[lid]);
else if(lan0[lid]==1) sum+=1;
}
for(long long n=lid+1; n<rid; n++) {
if(lan0[n]==2) {
if(lan[n]==1) sum+=block[n].r-block[n].l+1-block[n].zhi;//中间块如果有反转标记0的个数就是1的个数
else sum+=block[n].zhi;//没有直接加上1的个数
} else {
if(lan0[n]==1) sum+=block[n].r-block[n].l+1;//有覆盖标记直接加上块长
}
}
for(long long n=block[rid].l; n<=quer; n++) {
if(lan0[rid]==2) sum+=(c[n]^lan[rid]);
else if(lan0[rid]==0) sum+=(c[n]&lan0[rid]);
else if(lan0[rid]==1) sum+=1;
}
}
cout<<sum<<endl;
}
if(ji==4) {
weihu(lid);
sum=0;
cnt=0;
if(lid==rid) {
for(long long n=quel; n<=quer; n++) {
if(c[n]==0) {
sum=max(sum,cnt);
cnt=0;
} else cnt++;
}
sum=max(sum,cnt);
} else {
weihu(rid);
sum=max(min(block[lid].rlian1,block[lid].r-quel+1)+min(block[lid+1].llian1,quer-block[lid+1].l+1),sum);
for(long long n=lid+1; n<rid; n++) {//不超出询问左块，用包含右端点最长1加上右块包含左端点最长1，，，，与块内最长1取最大
sum=max(block[n].rlian1+min(quer-block[n+1].l+1,block[n+1].llian1),max(block[n].lian1,sum));
}
}
cout<<sum<<endl;
}
}
return 0;
}@wjr_jok