P1503 鬼子进村

本文主要是介绍P1503 鬼子进村，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题面

县城里有 \(n\) 个用地道相连的房子，初始时全部房屋未被摧毁，第 \(i\) 个只与第 \(i-1\) 和第 \(i+1\) 个相连。这时有 \(m\) 个消息依次传来：

1. 若消息为 D x：鬼子将 \(x\) 号房子摧毁了，地道被堵上。

2. 若消息为 R ：村民们将鬼子上一个摧毁的房子修复了。

3. 若消息为 Q x：有一名士兵被围堵在 \(x\) 号房子中。

李云龙收到信息很紧张，他想知道每一个被围堵的士兵通过地道能够到达的房子有几个。请注意，如果士兵所在的房子已被摧毁，那么他无法行动。

\(1\leq n,m\leq 5\times 10^4\)。

思路

这道题我先想到了一个 std::set 做法，但是不想写二分，于是想到了一个正经的平衡树做法。

首先，我们用一个栈和一个平衡树来维护被摧毁的元素，然后用一个状态数组维护房屋是否被摧毁。

• 如果是一个摧毁操作，那么将 \(x\) 放入栈、平衡树中。然后标记。
• 如果是一个修复操作，那么将栈顶元素从平衡树中删除，并取消标记，然后出栈。
• 如果是要给询问操作，可见这就是在询问平衡树中 \(x\) 的前驱后继的距离（也就是到被破坏的距离）减 \(2\)（首尾被破坏）。直接在平衡树上处理即可。

注意，可能当前没有房屋被破坏，直接询问会出锅，我们可以插入虚拟节点 \(0,n+1\)，由于它们不存在，把它们看成摧毁了的房屋是可以的。

平衡树这里使用的我最近学习的 \(\textbf{FHQ Treap}\)。

时间复杂度 \(O(m\log n)\)。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

namespace FHQTreap{
	const int SIZE = 5e4+5;
	int son[SIZE][2];
	int val[SIZE],rk[SIZE],siz[SIZE],root,points;
	mt19937 randomer(time(0));
	
#define ls(i) (son[(i)][0])
#define rs(i) (son[(i)][1])
	
	void pushup(int i){
		siz[i]=siz[ls(i)]+siz[rs(i)]+1;
	}
	
	int newnode(int v){
		val[++points]=v;
		rk[points]=randomer();
		siz[points]=1;
		return points;
	}
	
	void split(int p,int v,int &left,int &right){
		if(!p){
			left=right=0;
			return;
		}
		if(val[p]<=v){
			left=p;
			split(rs(p),v,rs(left),right);
		}
		else{
			right=p;
			split(ls(p),v,left,ls(right));
		}
		pushup(p);
	}
	
	int merge(int left,int right){
		if(!left||!right){
			if(left)return left;
			else if(right)return right;
			else return 0;
		}
		if(rk[left]<rk[right]){
			ls(right)=merge(left,ls(right));
			pushup(right);
			return right;
		}
		else{
			rs(left)=merge(rs(left),right);
			pushup(left);
			return left;
		}
	}
	
	void insert(int v){
		int left=0,right=0;
		split(root,v-1,left,right);
		root=merge(merge(left,newnode(v)),right);
	}
	
	void remove(int v){
		int left=0,mid=0,right=0;
		split(root,v,left,right);
		split(left,v-1,left,mid);
		mid=merge(ls(mid),rs(mid));
		root=merge(merge(left,mid),right);
	}

	int pre(int v){
		int now=root,ret=0;
		while(1){
			if(!now){
				return ret;
			}
			else if(v<=val[now]){
				now=ls(now);
			}
			else{
				ret=val[now];
				now=rs(now);
			}
		}
	}
	
	int next(int v){
		int now=root,ret=0;
		while(1){
			if(!now){
				return ret;
			}
			else if(v>=val[now]){
				now=rs(now);
			}
			else{
				ret=val[now];
				now=ls(now);
			}
		}
	}
}

namespace solution{
	int n,m;
	stack<int> destoried;
	bool status[50005];
	int solution(){
		cin>>n>>m;
		FHQTreap::insert(0);
		FHQTreap::insert(n+1);
		while(m--){
			char op;int x;
			cin>>op;
			if(op=='D'){
				cin>>x;
				destoried.push(x);
				FHQTreap::insert(x);
				status[x]=true;
			}
			else if(op=='R'){
				FHQTreap::remove(destoried.top());
				status[destoried.top()]=false;
				destoried.pop();
			}
			else{
				cin>>x;
				if(status[x]){
					cout<<0<<'\n';
				}
				else{
					cout<<(FHQTreap::next(x)-FHQTreap::pre(x)-1)<<'\n';
				}
			}
		}
		return 0;
	}
}

signed main(){
	ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
	return solution::solution();
}

AC Record

这篇关于P1503 鬼子进村的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！