我用递归写单调栈(?)

在这里插入图片描述
前言：嗯,这个题上午有的思路，敲了一中午代码，改了一下午最后超时?
题：D. Boris and His Amazing Haircut
题意：一个理发师可以把一段数组给建成一个高度，他现在每个高度的剪子都有若干个。给一个原始数组和目标数组，问能不能剪成目标数组。
奇怪的想法： 理发师最优的剪法就是先剪出来高的，然后在高的头发形成的段之间再剪次高的。直接上分治，结果超时，边界控制太难写了，
超时的代码：

#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
const int length = 2e5 + 5;
vector<int> ag;
vector<int> bg;
map<int,int> mp;
vector<int> count1;
vector<vector<int>> index1;
int tree[length << 3];
void update(int l, int r, int L, int R, int cnt, int v)
{
	if (L >= l && R <= r)
	{
		tree[cnt] = v;
		return;
	}
	if (L > r || R < l)
	{
		return;
	}
	int mid = (L + R) / 2;
	update(l, r, L, mid, cnt << 1, v);
	update(l, r, mid + 1, R, cnt * 2 + 1, v);
	tree[cnt] = max(tree[cnt * 2], tree[cnt * 2 + 1]);
}
int query(int l, int r, int L, int R, int cnt)
{
	if (L>=l&&R<=r)
	{
		return tree[cnt];
	}
	if (L > r || R < l)
		return 0;
	int mid = (L + R) / 2;
	int a = query(l, r, L, mid, cnt * 2);
	int b = query(l, r, mid + 1, R, cnt * 2 + 1);
	return max(a, b);
}
int n1;
bool DP(int l, int r)
{
	//if()
	if (l > r)
		return 1;
	int yh = query(l, r, 0, n1 - 1, 1);
	bool sum = 1;
	int lflag = ((l==0)?0:1);
	int rflag = ((r==n1-1)?0:-1);
	int cut = 0;
	//找到第一个大于等于l的数
	int a = -1;
	int b = index1[yh].size();
	while (a != b - 1)
	{
		int mid = (a + b) / 2;
		if (index1[yh][mid] < l)
			a = mid;
		else
			b = mid;
	}
	int i = b;
	int in = 0;
	for (; i<index1[yh].size()&&index1[yh][i]<=r; i++)
	{
		if (i != index1[yh].size() && mp[ag[index1[yh][i]]] != mp[bg[index1[yh][i]]]&&cut==0)
		{
			cut = 1;
			if (count1[mp[bg[index1[yh][i]]]])
				count1[mp[bg[index1[yh][i]]]]--;
			else
				return 0;
		}
		if (in == 0)
		{
			bool a=DP(l , index1[yh][i] - 1);
			sum = sum & a;
		}
		else
		{
			bool a = DP(index1[yh][i - 1] + 1, index1[yh][i] - 1);
			sum = sum & a;
		}
		if (sum == 0)
			return sum;
		in = 1;
	}
	if (i!=index1[yh].size()&&index1[yh][i] > r)
	{
		if (i != 0)
		{
			bool a = DP(index1[yh][i - 1] + 1, r);
			sum = sum & a;
		}
	}
	else if (i == index1[yh].size() && index1[yh][i - 1] != r)
	{
		bool a = DP(index1[yh][i - 1] + 1, r);
		sum = sum & a;
	}
	return sum;
}
int main(void)
{
	int t;
	scanf_s("%d", &t);
	for (int i = 0; i < t; i++)
	{
		int n;
		scanf_s("%d", &n);
		n1 = n;
		vector<int> a(n,0);
		for (int i = 0; i < n; i++)
		{
			scanf_s("%d", &a[i]);
		}
		vector<int> b(n, 0);
		for (int i = 0; i < n; i++)
		{
			scanf_s("%d", &b[i]);
		}
		int m;
		scanf_s("%d", &m);
		vector<int> c(m, 0);
		for (int i = 0; i < m; i++)
		{
			scanf_s("%d", &c[i]);
		}
		ag = a; bg = b;//全局变量赋值
		vector<int> tmp=b;
		sort(tmp.begin(), tmp.end());
		vector<int>::iterator p = unique(tmp.begin(), tmp.end());
		int off = p - tmp.begin();
		map<int, int> hk;
		int cnt = 1;
		for (int i = 0; i < off; i++)
		{
			hk[tmp[i]] = i + 1;
		}
		mp = hk;
		vector<int> tmp_count(length);
		for (int i = 0; i < m; i++)
		{
			tmp_count[mp[c[i]]]++;//统计映射之后的数量
		}
		count1 = tmp_count;
		memset(tree, 0, sizeof(tree));
		vector<vector<int>> edge(length);
		int ok = 1;
		for (int i = 0; i < n; i++)
		{
			if (a[i] < b[i])
				ok = 0;
			update(i, i, 0, n - 1, 1, mp[b[i]]);//更新区间最值以及坐标位置
			edge[mp[b[i]]].push_back(i);
		}
		if (ok == 0)
		{
			printf("NO\n");
			continue;
		}
		index1 = edge;
		int yh=DP(0, n - 1);
		if (yh)
			printf("YES\n");
		else
			printf("NO\n");
	}
}

正解：
思考源头：为啥要剪一段？省剪子啊，他的剪子都是一次性的，用完不能再用乐。并且剪成高度为 $5$ 的时候不能穿过高度为 $8$ 的。所以就用单调栈呗，注意 $a [i] == b [i]$ 的头发可以弹出数，但是不能入栈，入栈的目的就是不让两边相同高度的头发剪两次。但是 $a [i] == b [i]$ 的可以作为山丘的两端，高度低的不能穿过他。
$A C$ 代码：

#include<iostream>
#include<cstdio>
#include<map>
#include<stack>
using namespace std;
const int length = 2e5 + 5;
int a[length];
int b[length];
map<int, int> mp;
int main(void)
{
	int t;
	scanf_s("%d", &t);
	for (int i = 0; i < t; i++)
	{
		mp.clear();
		int n;
		scanf_s("%d", &n);
		for (int i = 0; i < n; i++)
		{
			scanf_s("%d", &a[i]);
		}
		for (int i = 0; i < n; i++)
		{
			scanf_s("%d", &b[i]);
		}
		int m;
		scanf_s("%d", &m);
		for (int i = 0; i < m; i++)
		{
			int a;
			scanf_s("%d", &a);
			mp[a]++;
		}
		int flag = 1;
		stack<int> s;
		for (int i = 0; i < n; i++)
		{
			if (a[i] < b[i])
			{
				flag = 0;
				break;
			}
			while (!s.empty() && s.top() < b[i])
				s.pop();
			if ((s.empty() || s.top() > b[i])&&a[i]!=b[i])
			{
				s.push(b[i]);
				if (mp[b[i]] == 0)
				{
					flag = 0;
					break;
				}
				mp[b[i]]--;
				
			}
		}
		if (flag == 0)
		{
			printf("NO\n");
		}
		else
			printf("YES\n");
	}
}