1 条题解

  • 1
    @ 2023-4-6 21:26:52

    线段树

    #include<bits/stdc++.h>
    using namespace std;
    int n,m,x;
    struct w{
    	int l,r;
    }s[1000011];
    int cnt,ans[2000011];//ans[]:记录所有能到达的ans
    int t[1600002],laz[1600002];//t[]:线段树  laz[]:延迟下传 
    void down(int now)
    {
    	//下传laz数组 
    	t[now*2]=max(t[now*2],laz[now]);
    	t[now*2+1]=max(t[now*2+1],laz[now]);
    	laz[now*2]=max(laz[now],laz[now*2]);
    	laz[now*2+1]=max(laz[now],laz[now*2+1]);
    	laz[now]=0;
    	return;
    }
    void down2(int now)
    {
    	//下传laz数组
    	t[now*2]=min(t[now*2],laz[now]);
    	t[now*2+1]=min(t[now*2+1],laz[now]);
    	laz[now*2]=min(laz[now],laz[now*2]);
    	laz[now*2+1]=min(laz[now],laz[now*2+1]);
    	laz[now]=1061109567;
    	return;
    }
    void update(int now,int l,int r,int x,int y,int k)
    {
    	if(y<l||x>r)
    		return;
    	if(l>=x&&r<=y)
    	{
    		//当前now能到达的最大点 
    		t[now]=max(t[now],k);
    		laz[now]=max(laz[now],k);
    		return;
    	}
    	down(now);
    	int mid=(l+r)/2;
    	update(now*2,l,mid,x,y,k);
    	update(now*2+1,mid+1,r,x,y,k);
    	//维护线段树最大值 
    	t[now]=max(t[now*2],t[now*2+1]);
    	return;
    }
    void update2(int now,int l,int r,int x,int y,int k)
    {
    	if(y<l||x>r)
    		return;
    	if(l>=x&&r<=y)
    	{
    		//当前now能到达的最小点 
    		t[now]=min(t[now],k);
    		laz[now]=min(laz[now],k);
    		return;
    	}
    	down2(now);
    	int mid=(l+r)/2;
    	update2(now*2,l,mid,x,y,k);
    	update2(now*2+1,mid+1,r,x,y,k);
    	//维护线段树最小值 
    	t[now]=min(t[now*2],t[now*2+1]);
    	return;
    }
    int query(int now,int l,int r,int x,int y)
    {
    	//查询区间最大值 
    	if(y<l||x>r)
    		return 0;
    	if(x<=l&&y>=r)
    		return t[now];
    	down(now);
    	int mid=(l+r)/2;
    	return max(query(now*2,l,mid,x,y),query(now*2+1,mid+1,r,x,y));
    }
    int query2(int now,int l,int r,int x,int y)
    {
    	//查询区间最小值
    	if(y<l||x>r)
    		return 1061109567;
    	if(x<=l&&y>=r)
    		return t[now];
    	down2(now);
    	int mid=(l+r)/2;
    	return min(query2(now*2,l,mid,x,y),query2(now*2+1,mid+1,r,x,y));
    }
    int main()
    {
    //	freopen("station.in","r",stdin);
    //	freopen("station.out","w",stdout);
    	ios::sync_with_stdio(false);
    	cin.tie(0);
    	cin>>n>>m>>x;
    	//建最大值线段树 
    	for(int i=1;i<=m;i++)
    	{
    		cin>>s[i].l>>s[i].r;
    		//线段树更新l~r最大走到r 
    		update(1,1,n,s[i].l,s[i].r,s[i].r);
    	}
    	//从x开始向后跳 
    	int maxto=x;
    	while(maxto<=n)
    	{
    		//向后走到maxto能达到的最后的点 
    		int nowmax=query(1,1,n,maxto,maxto);
    		if(nowmax<=maxto)
    			break;
    		maxto=nowmax;
    	}
    	//若能到达maxto 则x~maxto之间所有的终点r都能到达 
    	for(int i=1;i<=m;i++)
    		if(s[i].r>x&&s[i].r<=maxto)
    			ans[++cnt]=s[i].r;
    	//重建最小值线段树 
    	memset(t,0x3f,sizeof(t));
    	memset(laz,0x3f,sizeof(laz));
    	for(int i=1;i<=m;i++)
    		update2(1,1,n,s[i].l,s[i].r,s[i].l);
    		//线段树更新l~r最小走到l 
    	maxto=x;//从x开始向前跳 
    	while(maxto>=1)
    	{
    		//向前走到maxto能达到的最前的点 
    		int nowmax=query2(1,1,n,maxto,maxto);
    		if(nowmax>=maxto)
    			break;
    		maxto=nowmax;
    	}
    	//若能到达maxto 则maxto~x之间所有的终点l都能到达 
    	for(int i=1;i<=m;i++)
    		if(s[i].l>=maxto&&s[i].l<x)
    			ans[++cnt]=s[i].l;
    	sort(ans+1,ans+cnt+1);//排序 
    	for(int i=1;i<=cnt;i++)
    		if(ans[i]!=ans[i-1])//去重 
    			cout<<ans[i]<<" ";
    	return 0;
    }
    

    信息

    ID
    1254
    时间
    1000ms
    内存
    512MiB
    难度
    9
    标签
    递交数
    10
    已通过
    4
    上传者