比赛链接：https://codeforces.ml/contest/1779

这次比赛还行吧，蓝名表现分上青了。D题有点虐，可以用dp、单调栈、rmq、树状数组、并查集做。我一个也没想到，现在弄明白了单调栈做法和rmq做法。感觉E题说不定能出，随便看两眼D题没思路，直接开E了

A水 B水但是恶心 C思路很简单就是很麻烦，两个堆来维护。

D题：

大意是给出数组a，给出数组b。给出m种操作。每次可以将a数组中的l -r  中的ai 替换成 ai = min(ai, x)。x来源于m种。

询问是否可以由a得到b。

记录每个数在b中出现的位置。如果存在bi>ai肯定no。
否则。我们去列举每个数出现的位置。如果存在相邻位置，那么操作数-1，如果两个位置中最大的数就是这个数，那么操作数-1.
找两个位置中最大的数我们可以用st表去处理这些数据。

rmq code：

void solve()
{
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++) cin>>b[i];
	map<int,int> mp;
	cin>>m;
	int tx;
	for(int i=1;i<=m;i++){
		cin>>tx;
		mp[tx]++;
	} 
	
	for(int i=1;i<=n;i++){
		if(a[i]<b[i]) {
			cno;
			return;
		}
	}
	
	ST_init();
	map<int,vector<int>>ve;
	for(int i=1;i<=n;i++){
		if(b[i]!=a[i]){
			ve[b[i]].push_back(i);
		}
	}
	for(auto iter = ve.begin();iter!=ve.end();iter++){
		int t = iter->first;
		vector<int> vv = iter->second; 
		int cur = vv.size();
		for(int i=0;i<vv.size()-1;i++){
			int x = vv[i],y=vv[i+1];
			if(x==y-1) cur--;
			else{
				int mx = stquery(x+1,y-1);
				if(mx<=t) cur--;
			}
		}
		if(cur>mp[t]){
			cno;
			return;
		}
	}
	cyes;
}

另一种做法也是比较普遍的做法就是单调栈。

这个题我们可以用单调栈去维护数据。顺序处理这些数据。如果该数比栈顶元素大。那些小的数就没有作用了。

最后栈顶如果和当前一样，我们继续保留之前的，这次不进行操作。因为进行上次操作时已经可以操作当前的数。

否则我们进行操作一次。因为之前可操作的大的数无法操作当前数。

单调栈 code：

void solve()
{
	mp.clear();
	int n,m;
	ll x;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++) cin>>b[i];
	cin>>m;
	for(int i=1;i<=m;i++){
		cin>>x;
		mp[x]++;
	}
	stack<ll> st;
	for(int i=1;i<=n;i++){
		if(a[i]<b[i]){
			cno;
			return;
		}
		while(!st.empty()&&st.top()<b[i]) st.pop();
		if((st.empty()||st.top()!=b[i])&&a[i]!=b[i]){
			st.push(b[i]);
			if(mp[b[i]]<=0){
				cno;
				return;
			}
			mp[b[i]]--;
		}
	}
	cyes;
}