社区讨论

大佬求调!线段树只AC前仨点,后面全TLE??

P2572[SCOI2010] 序列操作参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@lxeq7655
此快照首次捕获于
2024/06/14 21:29
2 年前
此快照最后确认于
2024/06/15 09:34
2 年前
查看原帖
CPP
#include <bits/stdc++.h>
using namespace std;
int n,m;
struct Node {
	int lazy;  // -1: 乱的  0:全是0  1: 全是1
	int l,r,sum;  // sum: 1的个数
	int ls1,rs1,s1;  // ls1: 左边连续1的个数   s1: 连续1的个数 
	int is_leaf;
}t[400010];
int a[100010];
void pushup (int i)
{
	if (t[i].is_leaf) return ;
	if (t[i<<1].lazy==t[i<<1|1].lazy) t[i].lazy=t[i<<1].lazy;
	else t[i].lazy=-1;
	t[i].sum=t[i<<1].sum+t[i<<1|1].sum;
	if (t[i<<1].lazy==1) t[i].ls1=t[i<<1].r-t[i<<1].l+1+t[i<<1|1].ls1; 
	else t[i].ls1=t[i<<1].ls1;
	if (t[i<<1|1].lazy==1) t[i].rs1=t[i<<1|1].r-t[i<<1|1].l+1+t[i<<1].rs1; 
	else t[i].rs1=t[i<<1|1].rs1;
	t[i].s1=max(max(t[i<<1].s1,t[i<<1|1].s1),t[i<<1].rs1+t[i<<1|1].ls1);
} 
void pushdown (int i)
{
	if (t[i].lazy==1) {
		t[i<<1].lazy=t[i<<1|1].lazy=1;
		t[i<<1].sum=t[i<<1].ls1=t[i<<1].rs1=t[i<<1].s1=t[i<<1].r-t[i<<1].l+1; 
		t[i<<1|1].sum=t[i<<1|1].ls1=t[i<<1|1].rs1=t[i<<1|1].s1=t[i<<1|1].r-t[i<<1|1].l+1; 
	}
	if (t[i].lazy==0) {
		t[i<<1].lazy=t[i<<1|1].lazy=0;
		t[i<<1].sum=t[i<<1].ls1=t[i<<1].rs1=0; 
		t[i<<1|1].sum=t[i<<1|1].ls1=t[i<<1|1].rs1=t[i<<1|1].s1=0; 
	}
}
void build (int i,int l,int r)
{
	t[i].l=l; t[i].r=r;
	if (l==r) {
		t[i].lazy=t[i].ls1=t[i].rs1=t[i].s1=t[i].sum=(a[l]==1);
		t[i].is_leaf=1;
		return ;
	}
	int mid=(l+r)>>1;
	build(i<<1,l,mid);
	build(i<<1|1,mid+1,r);
	pushup(i);
	return ;
}
void change (int i,int l,int r,int L,int R,int opt)
{
	if (L<=l && r<=R) {
		t[i].lazy=opt;
		if (opt==1) t[i].ls1=t[i].rs1=t[i].s1=t[i].sum=r-l+1;
		else t[i].ls1=t[i].rs1=t[i].s1=t[i].sum=0;
		pushdown(i);
		return ;
	} 
	pushdown(i);
	int mid=(l+r)>>1;
	if (mid>=L) change(i<<1,l,mid,L,R,opt);
	if (mid<R) change(i<<1|1,mid+1,r,L,R,opt);
	pushup(i);
	return ;
}
void Negate (int i,int l,int r,int L,int R)
{
	if (L<=l && r<=R && t[i].lazy!=-1) {
		t[i].lazy^=1;
		if (t[i].lazy==1) t[i].ls1=t[i].rs1=t[i].s1=t[i].sum=r-l+1;
		else t[i].ls1=t[i].rs1=t[i].s1=t[i].sum=0;
		pushdown(i);
		return ;
	}
	pushdown(i);
	int mid=(l+r)>>1;
	if (mid>=L) Negate(i<<1,l,mid,L,R);
	if (mid<R) Negate(i<<1|1,mid+1,r,L,R);
	pushup(i);
	return ;
}
int ask_sum (int i,int l,int r,int L,int R)
{
	if (L<=l && r<=R) return t[i].sum;
	pushdown(i);
	int mid=(l+r)>>1,ans=0;
	if (mid>=L) ans+=ask_sum(i<<1,l,mid,L,R);
	if (mid<R) ans+=ask_sum(i<<1|1,mid+1,r,L,R);
	pushup(i);
	return ans;
}
int ask_con (int i,int l,int r,int L,int R)
{
	if (L<=l && r<=R) return t[i].s1;
	pushdown(i);
	int mid=(l+r)>>1,ans=0;
	if (mid>=L) ans=max(ans,ask_con(i<<1,l,mid,L,R));
	if (mid<R) ans=max(ans,ask_con(i<<1|1,mid+1,r,L,R));
	if (mid>=L && mid<R) ans=max(ans,min(t[i<<1].rs1,mid-L+1)+min(t[i<<1|1].ls1,R-mid));
	pushup(i);
	return ans;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin>>n>>m;
	for (int i=1;i<=n;i++)
		cin>>a[i];
	build(1,1,n);
//		for (int i=1;i<=n*2;i++) {
//			cout<<t[i].lazy<<" "<<t[i].sum<<" "<<t[i].s1<<" "<<t[i].ls1<<" "<<t[i].rs1<<endl; 
//		}
//		cout<<endl;
	while (m--) {
		int opt,l,r;
		cin>>opt>>l>>r;
		l++; r++;
		if (opt<=1) change(1,1,n,l,r,opt);
		if (opt==2) Negate(1,1,n,l,r);
		if (opt==3) cout<<ask_sum(1,1,n,l,r)<<endl;
		if (opt==4) cout<<ask_con(1,1,n,l,r)<<endl;
//		for (int i=1;i<=n*2;i++) {
//			cout<<t[i].lazy<<" "<<t[i].sum<<" "<<t[i].s1<<" "<<t[i].ls1<<" "<<t[i].rs1<<endl; 
//		}
//		cout<<endl;
	}
	return 0;
}

回复

0 条回复,欢迎继续交流。

正在加载回复...