线段树还不让过(^~^)

#include<bits/stdc++.h>
#define lt i<<1
#define rt i<<1|1
using namespace std;
const int N = 1e5 + 5;
int n, w[N], m;
struct segment_tree {
	int l, r, mn;
}tr[N * 4];
int val, maxlen, minlen;

struct node {
	int a, b;
	node() {}
	node(int a, int b) :a(a), b(b) {}
	bool operator<(const node m)const { 
		return a < m.a;
	}

}arr[N];


void build(int i, int l, int r)
{
	tr[i].l = l, tr[i].r = r;
	if (l == r) { tr[i].mn = w[l]; return; }

	int m = l + r >> 1;

	build(lt, l, m);
	build(rt, m + 1, r);
	tr[i].mn = min(tr[lt].mn, tr[rt].mn);
}

int section_min(int i, int l, int r)
{
	if (l <= tr[i].l && tr[i].r <= r)
		return tr[i].mn;
	if (tr[i].l > r || tr[i].r < l)
		return 0;
	int ans = INT_MAX;
	if (tr[lt].r >= l)
		ans = min(ans, section_min(lt, l, r));
	if (tr[rt].l <= r)
		ans = min(ans, section_min(rt, l, r));
	return ans;
}

int main(void)
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) { cin >> w[i]; arr[i] = { w[i],i }; }
	build(1, 1, n);
	sort(arr + 1, arr + 1 + n);
	cin >> m;
	while (m--)
	{
        
		cin >> val >> minlen >> maxlen;
		int idx = lower_bound(arr + 1, arr + 1 + n, node(val, 0)) - arr - 1;
		bool bol = 0;
		for (; idx <= n; idx++)
		{
			int pos = arr[idx].b;
			int l, r;
			if (pos - minlen + 1 < 1) {
				l = 1; r = l + minlen - 1;
			}
			else if (pos + minlen - 1 > n) {
				r = n; l = r - minlen + 1;
			}
			else{
				r = pos; l = r - minlen + 1;
			}
			for (; r <= n; r++, l++){
				if (section_min(1, l, r) >= val) { bol = 1; cout << "Yes" << '\n'; break; }
			}
			if (bol)break;
		}
		if (!bol)cout << "No" << '\n';
	}
	return 0;
}

全部评论
你 O(n^2) 凭什么过
1 回复 分享
发布于 06-07 22:09 江苏

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务