| 记录编号 |
601934 |
评测结果 |
WWWWWWWWWWWWWWWWWWWW |
| 题目名称 |
3947.[国家集训队 2011]等差子序列 |
最终得分 |
0 |
| 用户昵称 |
 秋_Water |
是否通过 |
未通过 |
| 代码语言 |
C++ |
运行时间 |
0.937 s |
| 提交时间 |
2025-06-29 17:38:09 |
内存使用 |
3.68 MiB |
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int cnt,block,n,m;
int a[N],pos[N];
struct node{
int sum1,max1,max0,st,ed;
int lmax1,rmax1;
int lmax0,rmax0;
int tag;
}t[N];
void pushdown(int i){
if(t[i].tag==0) return;
int l=t[i].st,r=t[i].ed;
if(t[i].tag==1){
for(int j=l;j<=r;j++) a[j]=0;
}
else if(t[i].tag==2){
for(int j=l;j<=r;j++) a[j]=1;
}
else if(t[i].tag==3){
for(int j=l;j<=r;j++) a[j]^=1;
}
t[i].tag=0;
}
void update_block(int i){
int l=t[i].st,r=t[i].ed;
pushdown(i);
t[i].sum1=0;
for(int j=l;j<=r;j++) t[i].sum1+=a[j];
t[i].max1=0;
int cur=0;
for(int j=l;j<=r;j++){
if(a[j]==1) cur++;
else{
if(cur>t[i].max1) t[i].max1=cur;
cur=0;
}
}
if(cur>t[i].max1) t[i].max1=cur;
cur=0;
for(int j=l;j<=r;j++){
if(a[j]==1) cur++;
else break;
}
t[i].lmax1=cur;
cur=0;
for(int j=r;j>=l;j--){
if(a[j]==1) cur++;
else break;
}
t[i].rmax1=cur;
t[i].max0=0;
cur=0;
for(int j=l;j<=r;j++){
if(a[j]==0) cur++;
else{
if(cur>t[i].max0) t[i].max0=cur;
cur=0;
}
}
if(cur>t[i].max0) t[i].max0=cur;
cur=0;
for(int j=l;j<=r;j++){
if(a[j]==0) cur++;
else break;
}
t[i].lmax0=cur;
cur=0;
for(int j=r;j>=l;j--){
if(a[j]==0) cur++;
else break;
}
t[i].rmax0=cur;
}
void apply_tag(int i, int op) {
if (op == 1 || op == 2) {
t[i].tag = op;
} else if (op == 3) {
if (t[i].tag == 0) t[i].tag = 3;
else if (t[i].tag == 1) t[i].tag = 2;
else if (t[i].tag == 2) t[i].tag = 1;
else if (t[i].tag == 3) t[i].tag = 0;
}
}
void update_by_tag(int i) {
if (t[i].tag == 0) return;
int len = t[i].ed - t[i].st + 1;
if (t[i].tag == 1) {
t[i].sum1 = 0;
t[i].max1 = 0;
t[i].lmax1 = 0;
t[i].rmax1 = 0;
t[i].max0 = len;
t[i].lmax0 = len;
t[i].rmax0 = len;
} else if (t[i].tag == 2) {
t[i].sum1 = len;
t[i].max1 = len;
t[i].lmax1 = len;
t[i].rmax1 = len;
t[i].max0 = 0;
t[i].lmax0 = 0;
t[i].rmax0 = 0;
} else if (t[i].tag == 3) {
t[i].sum1 = len - t[i].sum1;
swap(t[i].max0, t[i].max1);
swap(t[i].lmax0, t[i].lmax1);
swap(t[i].rmax0, t[i].rmax1);
}
}
void init(){
block=sqrt(n);
cnt=n/block;
if(n%block) cnt++;
for(int i=1;i<=cnt;i++){
t[i].st=(i-1)*block+1;
t[i].ed=i*block;
t[i].tag=0;
}
for(int i=1;i<=n;i++){
pos[i]=(i-1)/block+1;
}
t[cnt].ed=n;
for(int i=1;i<=cnt;i++) update_block(i);
}
void change1(int l,int r){
int p=pos[l],q=pos[r];
if(p==q){
pushdown(p);
for(int i=l;i<=r;i++) a[i]=0;
update_block(p);
return;
}
pushdown(p);
for(int i=l;i<=t[p].ed;i++) a[i]=0;
update_block(p);
for(int i=p+1;i<=q-1;i++){
apply_tag(i,1);
update_by_tag(i);
}
pushdown(q);
for(int i=t[q].st;i<=r;i++) a[i]=0;
update_block(q);
}
void change2(int l,int r){
int p=pos[l],q=pos[r];
if(p==q){
pushdown(p);
for(int i=l;i<=r;i++) a[i]=1;
update_block(p);
return;
}
pushdown(p);
for(int i=l;i<=t[p].ed;i++) a[i]=1;
update_block(p);
for(int i=p+1;i<=q-1;i++){
apply_tag(i,2);
update_by_tag(i);
}
pushdown(q);
for(int i=t[q].st;i<=r;i++) a[i]=1;
update_block(q);
}
void change3(int l,int r){
int p=pos[l],q=pos[r];
if(p==q){
pushdown(p);
for(int i=l;i<=r;i++) a[i]^=1;
update_block(p);
return;
}
pushdown(p);
for(int i=l;i<=t[p].ed;i++) a[i]^=1;
update_block(p);
for(int i=p+1;i<=q-1;i++){
apply_tag(i,3);
update_by_tag(i);
}
pushdown(q);
for(int i=t[q].st;i<=r;i++) a[i]^=1;
update_block(q);
}
int query1(int l,int r){
int p=pos[l],q=pos[r];
int ans=0;
if(p==q){
pushdown(p);
for(int i=l;i<=r;i++) ans+=a[i];
update_block(p);
return ans;
}
pushdown(p);
for(int i=l;i<=t[p].ed;i++) ans+=a[i];
for(int i=p+1;i<=q-1;i++) ans+=t[i].sum1;
pushdown(q);
for(int i=t[q].st;i<=r;i++) ans+=a[i];
update_block(q);
return ans;
}
int query2(int l,int r){
int p=pos[l],q=pos[r];
if(p==q){
pushdown(p);
int res=0,cur=0;
for(int i=l;i<=r;i++){
if(a[i]==1) cur++;
else cur=0;
res=max(res,cur);
}
update_block(p);
return res;
}
pushdown(p);
int res=0,cur=0;
for(int i=l;i<=t[p].ed;i++){
if(a[i]==1) cur++;
else cur=0;
res=max(res,cur);
}
int tail=cur;
for(int i=l;i<=t[p].ed;i++){
if(a[i]==1) tail=t[p].ed-i+1;
else break;
}
int mid_cont=tail;
for(int i=p+1;i<q;i++){
res=max(res,t[i].max1);
if(mid_cont==t[p].ed-l+1){
mid_cont+=t[i].lmax1;
res=max(res,mid_cont);
if(t[i].lmax1!=t[i].ed-t[i].st+1){
mid_cont=t[i].rmax1;
}
}
else{
mid_cont=t[i].rmax1;
}
}
pushdown(q);
int head=0;
for(int i=t[q].st;i<=r;i++){
if(a[i]==1) head++;
else break;
}
res=max(res,head);
cur=0;
for(int i=t[q].st;i<=r;i++){
if(a[i]==1) cur++;
else cur=0;
res=max(res,cur);
}
if(mid_cont>0) res=max(res,mid_cont+head);
update_block(p);
update_block(q);
return res;
}
int main(){
freopen("sequence.in","r",stdin);
freopen("sequence.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
init();
while(m--){
int op,l,r;
cin>>op>>l>>r;
l++,r++;
if(op==0){
change1(l,r);
}
else if(op==1){
change2(l,r);
}
else if(op==2){
change3(l,r);
}
else if(op==3){
cout<<query1(l,r)<<"\n";
}
else{
cout<<query2(l,r)<<"\n";
}
}
return 0;
}