20分求助(附hack数据+调试代码）
查看原帖
20分求助(附hack数据+调试代码）
362627
frank15楼主2021/3/10 17:35

源码

#include<iostream>
#include<cstdio>
#define int long long
#define ls(p) (p<<1)
#define rs(p) (p<<1)+1
using namespace std;
const int maxn=1e5+5;
int n,m,OP,L,R;
int a[maxn];
struct t{
	int sum,tag1,tag2;
	int lmax[2],rmax[2],midmax[2];
}tree[maxn<<2];
void push_up(int node,int l,int r,int mid){
	tree[node].sum=tree[ls(node)].sum+tree[rs(node)].sum;
	for(int i=0;i<=1;i++){
		tree[node].lmax[i]=tree[ls(node)].lmax[i];
		if(tree[ls(node)].sum==(mid-l+1)*i)
			tree[node].lmax[i]=tree[rs(node)].lmax[i]+mid-l+1;

		tree[node].rmax[i]=tree[rs(node)].rmax[i];
		if(tree[rs(node)].sum==(r-mid)*i)
			tree[node].rmax[i]=tree[ls(node)].rmax[i]+r-mid;
			
		tree[node].midmax[i]=tree[ls(node)].rmax[i]+tree[rs(node)].lmax[i];
		tree[node].midmax[i]=max(tree[node].midmax[i],tree[ls(node)].midmax[i]);
		tree[node].midmax[i]=max(tree[node].midmax[i],tree[rs(node)].midmax[i]);
	}
	return ;
}
void push_down(int node,int l,int r,int mid){
	if(tree[node].tag1!=-1){
		int k=tree[node].tag1;
		tree[ls(node)].sum=(mid-l+1)*k;
		tree[rs(node)].sum=(r-mid)*k;
		
		tree[ls(node)].lmax[k]=tree[ls(node)].rmax[k]=tree[ls(node)].midmax[k]=mid-l+1;
		tree[ls(node)].lmax[!k]=tree[ls(node)].rmax[!k]=tree[ls(node)].midmax[!k]=0;
		
		tree[rs(node)].lmax[k]=tree[rs(node)].rmax[k]=tree[rs(node)].midmax[k]=r-mid;
		tree[rs(node)].lmax[!k]=tree[rs(node)].rmax[!k]=tree[rs(node)].midmax[!k]=0;
		
		tree[node].tag1=-1;
		tree[ls(node)].tag1=tree[rs(node)].tag1=k;
		
		tree[node].tag2=tree[ls(node)].tag2=tree[rs(node)].tag2=0;
	}
	if(tree[node].tag2){
		tree[ls(node)].sum=(mid-l+1)-tree[ls(node)].sum;
		tree[rs(node)].sum=(r-mid)-tree[rs(node)].sum;
		
		if(tree[ls(node)].tag1!=-1)
			tree[ls(node)].tag1^=1;
		else
			tree[ls(node)].tag2^=1;
			
		if(tree[rs(node)].tag1!=-1)
			tree[rs(node)].tag1^=1;
		else
			tree[rs(node)].tag2^=1;
			
		tree[node].tag2=0;
		
		swap(tree[ls(node)].lmax[0],tree[ls(node)].lmax[1]);
		swap(tree[ls(node)].rmax[0],tree[ls(node)].rmax[1]);
		swap(tree[ls(node)].midmax[0],tree[ls(node)].midmax[1]);
		
		swap(tree[rs(node)].lmax[0],tree[rs(node)].lmax[1]);
		swap(tree[rs(node)].rmax[0],tree[rs(node)].rmax[1]);
		swap(tree[rs(node)].midmax[0],tree[rs(node)].midmax[1]);
	}
	return ;
}
void build(int node,int l,int r){
	if(l==r){
		tree[node].sum=a[l];
		tree[node].tag1=-1;
		tree[node].lmax[0]=tree[node].rmax[0]=tree[node].midmax[0]=!a[l];
		tree[node].lmax[1]=tree[node].rmax[1]=tree[node].midmax[1]=a[l];
		return ;
	}
	int mid=(l+r)>>1;
	build(ls(node),l,mid);
	build(rs(node),mid+1,r);
	push_up(node,l,r,mid);
	tree[node].tag1=-1;
	return ;
}
void update(int node,int l,int r,int aim_L,int aim_R,int op){
	if(l>aim_R||r<aim_L)
		return ;
	if(aim_L<=l&&r<=aim_R){
		if(op<=1){
			tree[node].tag1=op;
			tree[node].sum=(r-l+1)*op;
			tree[node].lmax[op]=tree[node].rmax[op]=tree[node].midmax[op]=r-l+1;
			tree[node].lmax[!op]=tree[node].rmax[!op]=tree[node].midmax[!op]=0;
		}
		else{
			tree[node].tag2^=1;
			tree[node].sum=(r-l+1)-tree[node].sum;
			swap(tree[node].lmax[0],tree[node].lmax[1]);
			swap(tree[node].rmax[0],tree[node].rmax[1]);
			swap(tree[node].midmax[0],tree[node].midmax[1]);
		}
		return ;
	}
	int mid=(l+r)>>1;
	push_down(node,l,r,mid);
	update(ls(node),l,mid,aim_L,aim_R,op);
	update(rs(node),mid+1,r,aim_L,aim_R,op);
	push_up(node,l,r,mid);
	return ;
}
int query1(int node,int l,int r,int aim_L,int aim_R){
	if(l>aim_R||r<aim_L)
		return 0;
//	cout<<node<<' '<<tree[node].sum<<' '<<l<<' '<<r<<endl;
	if(aim_L<=l&&r<=aim_R)
		return tree[node].sum;
	int mid=(l+r)>>1;
	push_down(node,l,r,mid);
	int lsum=query1(ls(node),l,mid,aim_L,aim_R);
	int rsum=query1(rs(node),mid+1,r,aim_L,aim_R);
	return lsum+rsum;
}
t query2(int node,int l,int r,int aim_L,int aim_R){
//	cout<<l<<' '<<r<<endl;
//	cout<<tree[node].lmax[1]<<endl;
	if(aim_L<=l&&r<=aim_R)
		return tree[node];
	int mid=(l+r)>>1;
	push_down(node,l,r,mid);
	if(mid>=aim_R)
		return query2(ls(node),l,mid,aim_L,aim_R);
	if(mid<aim_L)
		return query2(rs(node),mid+1,r,aim_L,aim_R);
	t res;
	t l_res=query2(ls(node),l,mid,aim_L,aim_R);
	t r_res=query2(rs(node),mid+1,r,aim_L,aim_R);
	res.sum=l_res.sum+r_res.sum;
	if(l_res.sum==mid-l+1)
		res.lmax[1]=mid-l+1+r_res.lmax[1];
	else
		res.lmax[1]=l_res.lmax[1];
	
	if(r_res.sum==r-mid)
		res.rmax[1]=r-mid+l_res.rmax[1];
	else
		res.rmax[1]=r_res.rmax[1];
		
	res.midmax[1]=l_res.rmax[1]+r_res.lmax[1];
	res.midmax[1]=max(res.midmax[1],l_res.midmax[1]);
	res.midmax[1]=max(res.midmax[1],r_res.midmax[1]);
	return res;
}
signed main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%lld",&a[i]);
	build(1,1,n);
	while(m--){
//		cout<<tree[14].lmax[1]<<endl;
		scanf("%lld%lld%lld",&OP,&L,&R);
		L++;
		R++;
//		cout<<OP<<' '<<L<<' '<<R<<endl;
		if(OP<=2)
			update(1,1,n,L,R,OP);
		if(OP==3)
			printf("%lld\n",query1(1,1,n,L,R));
		if(OP==4){
			t ans=query2(1,1,n,L,R);
			printf("%lld\n",ans.midmax[1]);
		}
	}
	return 0;
}

hack 数据

4 8

0 0 1 0

3 2 4

2 1 4

4 1 3

1 1 4

2 1 4

4 3 3

（注：数据下标从1开始

#include<iostream>
#include<cstdio>
#define int long long
#define ls(p) (p<<1)
#define rs(p) (p<<1)+1
using namespace std;
const int maxn=1e5+5;
int n,m,OP,L,R;
int a[maxn];
struct t{
	int sum,tag1,tag2;
	int lmax[2],rmax[2],midmax[2];
}tree[maxn<<2];
void push_up(int node,int l,int r,int mid){
	tree[node].sum=tree[ls(node)].sum+tree[rs(node)].sum;
	for(int i=0;i<=1;i++){
		tree[node].lmax[i]=tree[ls(node)].lmax[i];
		if(tree[ls(node)].sum==(mid-l+1)*i)
			tree[node].lmax[i]=tree[rs(node)].lmax[i]+mid-l+1;

		tree[node].rmax[i]=tree[rs(node)].rmax[i];
		if(tree[rs(node)].sum==(r-mid)*i)
			tree[node].rmax[i]=tree[ls(node)].rmax[i]+r-mid;
			
		tree[node].midmax[i]=tree[ls(node)].rmax[i]+tree[rs(node)].lmax[i];
		tree[node].midmax[i]=max(tree[node].midmax[i],tree[ls(node)].midmax[i]);
		tree[node].midmax[i]=max(tree[node].midmax[i],tree[rs(node)].midmax[i]);
	}
	return ;
}
void push_down(int node,int l,int r,int mid){
	if(tree[node].tag1!=-1){
		int k=tree[node].tag1;
		tree[ls(node)].sum=(mid-l+1)*k;
		tree[rs(node)].sum=(r-mid)*k;
		
		tree[ls(node)].lmax[k]=tree[ls(node)].rmax[k]=tree[ls(node)].midmax[k]=mid-l+1;
		tree[ls(node)].lmax[!k]=tree[ls(node)].rmax[!k]=tree[ls(node)].midmax[!k]=0;
		
		tree[rs(node)].lmax[k]=tree[rs(node)].rmax[k]=tree[rs(node)].midmax[k]=r-mid;
		tree[rs(node)].lmax[!k]=tree[rs(node)].rmax[!k]=tree[rs(node)].midmax[!k]=0;
		
		tree[node].tag1=-1;
		tree[ls(node)].tag1=tree[rs(node)].tag1=k;
		
		tree[node].tag2=tree[ls(node)].tag2=tree[rs(node)].tag2=0;
	}
	if(tree[node].tag2){
		tree[ls(node)].sum=(mid-l+1)-tree[ls(node)].sum;
		tree[rs(node)].sum=(r-mid)-tree[rs(node)].sum;
		
		if(tree[ls(node)].tag1!=-1)
			tree[ls(node)].tag1^=1;
		else
			tree[ls(node)].tag2^=1;
			
		if(tree[rs(node)].tag1!=-1)
			tree[rs(node)].tag1^=1;
		else
			tree[rs(node)].tag2^=1;
			
		tree[node].tag2=0;
		
		swap(tree[ls(node)].lmax[0],tree[ls(node)].lmax[1]);
		swap(tree[ls(node)].rmax[0],tree[ls(node)].rmax[1]);
		swap(tree[ls(node)].midmax[0],tree[ls(node)].midmax[1]);
		
		swap(tree[rs(node)].lmax[0],tree[rs(node)].lmax[1]);
		swap(tree[rs(node)].rmax[0],tree[rs(node)].rmax[1]);
		swap(tree[rs(node)].midmax[0],tree[rs(node)].midmax[1]);
	}
	return ;
}
void build(int node,int l,int r){
	if(l==r){
		tree[node].sum=a[l];
		tree[node].tag1=-1;
		tree[node].lmax[0]=tree[node].rmax[0]=tree[node].midmax[0]=!a[l];
		tree[node].lmax[1]=tree[node].rmax[1]=tree[node].midmax[1]=a[l];
		return ;
	}
	int mid=(l+r)>>1;
	build(ls(node),l,mid);
	build(rs(node),mid+1,r);
	push_up(node,l,r,mid);
	tree[node].tag1=-1;
	return ;
}
void update(int node,int l,int r,int aim_L,int aim_R,int op){
	if(l>aim_R||r<aim_L)
		return ;
	if(aim_L<=l&&r<=aim_R){
		if(op<=1){
			tree[node].tag1=op;
			tree[node].sum=(r-l+1)*op;
			tree[node].lmax[op]=tree[node].rmax[op]=tree[node].midmax[op]=r-l+1;
			tree[node].lmax[!op]=tree[node].rmax[!op]=tree[node].midmax[!op]=0;
		}
		else{
			tree[node].tag2^=1;
			tree[node].sum=(r-l+1)-tree[node].sum;
			swap(tree[node].lmax[0],tree[node].lmax[1]);
			swap(tree[node].rmax[0],tree[node].rmax[1]);
			swap(tree[node].midmax[0],tree[node].midmax[1]);
		}
		return ;
	}
	int mid=(l+r)>>1;
	push_down(node,l,r,mid);
	update(ls(node),l,mid,aim_L,aim_R,op);
	update(rs(node),mid+1,r,aim_L,aim_R,op);
	push_up(node,l,r,mid);
	return ;
}
int query1(int node,int l,int r,int aim_L,int aim_R){
	if(l>aim_R||r<aim_L)
		return 0;
//	cout<<node<<' '<<tree[node].sum<<' '<<l<<' '<<r<<endl;
	if(aim_L<=l&&r<=aim_R)
		return tree[node].sum;
	int mid=(l+r)>>1;
	push_down(node,l,r,mid);
	int lsum=query1(ls(node),l,mid,aim_L,aim_R);
	int rsum=query1(rs(node),mid+1,r,aim_L,aim_R);
	return lsum+rsum;
}
t query2(int node,int l,int r,int aim_L,int aim_R){
//	cout<<l<<' '<<r<<endl;
//	cout<<tree[node].lmax[1]<<endl;
	if(aim_L<=l&&r<=aim_R)
		return tree[node];
	int mid=(l+r)>>1;
	push_down(node,l,r,mid);
	if(mid>=aim_R)
		return query2(ls(node),l,mid,aim_L,aim_R);
	if(mid<aim_L)
		return query2(rs(node),mid+1,r,aim_L,aim_R);
	t res;
	t l_res=query2(ls(node),l,mid,aim_L,aim_R);
	t r_res=query2(rs(node),mid+1,r,aim_L,aim_R);
	res.sum=l_res.sum+r_res.sum;
	if(l_res.sum==mid-l+1)
		res.lmax[1]=mid-l+1+r_res.lmax[1];
	else
		res.lmax[1]=l_res.lmax[1];
	
	if(r_res.sum==r-mid)
		res.rmax[1]=r-mid+l_res.rmax[1];
	else
		res.rmax[1]=r_res.rmax[1];
		
	res.midmax[1]=l_res.rmax[1]+r_res.lmax[1];
	res.midmax[1]=max(res.midmax[1],l_res.midmax[1]);
	res.midmax[1]=max(res.midmax[1],r_res.midmax[1]);
	return res;
}
void out(int node,int l,int r){
	cout<<node<<' '<<l<<' '<<r<<endl;
	cout<<tree[node].tag1<<' '<<tree[node].tag2<<' '<<tree[node].sum<<endl;
	int mid=(l+r)>>1;
	if(l<r){
		out(ls(node),l,mid);
		out(rs(node),mid+1,r);
	}
}
signed main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%lld",&a[i]);
	build(1,1,n);
	while(m--){
		scanf("%lld%lld%lld",&OP,&L,&R);
//		L++;
//		R++;
//		cout<<OP<<' '<<L<<' '<<R<<endl;
		if(OP<=2)
			update(1,1,n,L,R,OP);
		if(OP==3)
			printf("%lld\n",query1(1,1,n,L,R));
		if(OP==4){
			t ans=query2(1,1,n,L,R);
			printf("%lld\n",ans.midmax[1]);
		}
		out(1,1,n);
	}
	return 0;
}
2021/3/10 17:35