不知道为什么会tle
查看原帖
不知道为什么会tle
819682
Exile_Code楼主2023/10/2 14:59
#define  _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cstdlib>
#include <algorithm>
#include <list>
#include <string>
#include <cmath>
#include <bitset>
#include<stack>

#define ll long long

#define N 200005



void solve() {
	int n; cin >> n;
	ll a[N], b[N]; 
	int cnt = 0;
	for (int i = 0; i < n; i++)
		scanf("%lld", &a[i]);
	map<int, int>use;
	map<int, int>need;
	bool flag = 0;
	pair<int, int> pi[N];
	for (int i = 0; i < n; i++) {
		scanf("%lld", &b[i]);
		if (b[i] > a[i])
			flag = 1;
		if (b[i] != a[i]) {
			pi[cnt] = { b[i],i };
			need[b[i]]++;
			cnt++;
		}//记录位置
	}

	int m; cin >> m;
	for (int i = 0; i < m; i++) {
		ll num; scanf("%lld", &num);
		use[num]++;
	}

	if (flag) {
		cout << "NO" << endl;
		return;
	}


	ll f[N][20];//st表记录区间最大值
	memset(f, 0, sizeof(f));
	for (int j = 0; j < 18; j++)
		for (int i = 0; i + (1 << j) - 1 < n; i++) {
			if (!j)f[i][j] = b[i];
			else
				f[i][j] = max(f[i][j - 1], f[i + 1 << (j - 1)][j - 1]);
		}

	sort(pi, pi + cnt);
	auto p1 = 0, p2 = 1;//进行区间合并
	while (p2 < cnt) {
		if (pi[p1].first != pi[p2].first) {
			p1++; p2++;
			continue;
		}
		else {
			int k = log2(pi[p2].second - pi[p1].second + 1);
			
			if (max(f[pi[p1].second][k]
				, f[pi[p2].second - (1 << k) ][k]) <= pi[p1].first)
				need[pi[p1].first]--;//st表查询区间最大值

			p1++; p2++;
		}
	}

	for (auto nd : need) {
		if (nd.second > use[nd.first]) {
			cout << "NO" << endl;
			return;
		}
	}

	cout << "YES" << endl;

}
int main() {

	int t; cin >> t;
	while (t--)
		solve();

	return 0;
}


2023/10/2 14:59
加载中...