二分+线段树求助
查看原帖
二分+线段树求助
654958
Light_az楼主2023/10/13 19:59

已经坐牢 2 个小时了,感觉节点值维护错了,急急急

维护区间修改和区间查询最长连续的 0,时间复杂度没问题,可能上下传懒标记时候维护错了

#include<bits/stdc++.h>
#define ll long long
#define F(i,j,n) for(ll i=j;i<=n;i++)
#define ps push_back
#define sz(x) ((ll)x.size())
#define mem(f,x) memset(f,x,sizeof(f))
#define all(x) x.begin(),x.end()
#define V vector
#define Test ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
const int N=1e6+10;
ll n,m,k,x,y,u,v,w,cnt,ans,t,l,r,len,T,id;
ll mn=INT_MAX,mx=0,p,opt;
char ch;
struct Node{
	ll num[2];
	ll l,r,mx;
	ll len;
}tr[N];
ll Q[N];
void push(ll id){
	if(Q[id]){
		Q[id*2]=Q[id];
		Q[id*2+1]=Q[id];
		if(Q[id]==1){
			tr[id*2].l=tr[id*2].r=tr[id*2].mx=tr[id*2].len;
			tr[id*2].num[1]=0;
			tr[id*2].num[0]=tr[id*2].len;
			tr[id*2+1].l=tr[id*2+1].r=tr[id*2+1].mx=tr[id*2+1].len;
			tr[id*2+1].num[1]=0;
			tr[id*2+1].num[0]=tr[id*2+1].len;
		}
		else{
			tr[id*2].l=tr[id*2].r=tr[id*2].mx=0;
			tr[id*2].num[1]=tr[id*2].len;
			tr[id*2].num[0]=0;
			tr[id*2+1].l=tr[id*2+1].r=tr[id*2+1].mx=0;
			tr[id*2+1].num[1]=tr[id*2+1].len;
			tr[id*2+1].num[0]=0;
		}
		Q[id]=0;
	}
} 
void up(ll id){
	tr[id].num[0]=tr[id*2].num[0]+tr[id*2+1].num[0];
	tr[id].num[1]=tr[id*2].num[1]+tr[id*2+1].num[1];
	tr[id].l=tr[id*2].l;
	if(tr[id*2].l==tr[id*2].len) tr[id].l=tr[id*2].l+tr[id*2+1].l;
	tr[id].l=min(tr[id].l,tr[id].len);
	tr[id].r=tr[id*2+1].r;
	if(tr[id*2+1].r==tr[id*2+1].len) tr[id].r=tr[id*2+1].r+tr[id*2].r;
	tr[id].r=min(tr[id].r,tr[id].len);
	tr[id].mx=max(max(tr[id*2].mx,tr[id*2+1].mx),tr[id*2].r+tr[id*2+1].l);
}
Node make(Node L,Node R){
	Node ans;
	ans.l=L.l;
	if(L.l==L.len) ans.l=L.l+R.l;
	ans.r=R.r;
	if(R.r==R.len) ans.r=R.r+L.r;
	ans.mx=max(ans.l,ans.r);
	return ans;
}
void build(ll id,ll l,ll r){
	tr[id].num[0]=tr[id].num[1]=0;
	tr[id].l=tr[id].r=tr[id].mx=0;
	tr[id].len=r-l+1;
	if(l==r){
		tr[id].num[1]=1;
		return ;
	}
	ll mid=(l+r)/2;
	build(id*2,l,mid);
	build(id*2+1,mid+1,r);
	up(id);
}
void update(ll id,ll l,ll r,ll x,ll y,ll k){
	if(r<x||l>y) return ;
	if(x<=l&&r<=y){
		Q[id]=k+1;
		tr[id].l=tr[id].r=tr[id].mx=tr[id].len*(k^1);
		tr[id].num[k^1]=0;
		tr[id].num[k]=tr[id].len;
		return ;
	}
	push(id);
	ll mid=(l+r)/2;
	if(tr[id*2].num[k^1]) update(id*2,l,mid,x,y,k);
	if(tr[id*2+1].num[k^1]) update(id*2+1,mid+1,r,x,y,k);
	up(id);
}
ll query1(ll id,ll l,ll r,ll x,ll y,ll k){
	if(r<x||l>y) return 0;
	if(x<=l&&r<=y) return tr[id].num[k];
	push(id);
	ll mid=(l+r)/2;
	return query1(id*2,l,mid,x,y,k)+query1(id*2+1,mid+1,r,x,y,k);
}
Node query2(ll id,ll l,ll r,ll x,ll y){	
	if(r<x||l>y) return {0,0,0,0,0,0};
	if(x<=l&&r<=y) return tr[id];
	push(id);
	ll mid=(l+r)/2;
	Node L=query2(id*2,l,mid,x,y);
	Node R=query2(id*2+1,mid+1,r,x,y);
	return make(L,R);
}
void solve1(){
	cin>>l>>r;
	update(1,1,n,l,r,0);
}
void solve2(){
	cin>>l>>r>>x>>y;
	ll num=query1(1,1,n,l,r,1);
	if(num==0) return ;
	update(1,1,n,l,r,0);
	ll L=x,R=y,id=y;
	while(L<=R){
		ll mid=(L+R)/2;
		if(query1(1,1,n,x,mid,0)>=num) id=mid,R=mid-1;
		else L=mid+1;
	}
	update(1,1,n,x,id,1);
}
void solve3(){
	cin>>l>>r;
	cout<<query2(1,1,n,l,r).mx<<"\n";
}
int main(){
	cin>>n>>m;
	build(1,1,n);
	F(i,1,m){
		cin>>opt;
		if(opt==0) solve1();
		if(opt==1) solve2();
		if(opt==2) solve3();
	}
	return 0;
}
2023/10/13 19:59
加载中...