第5题 询问 查看测评数据信息
给一个长度为n的正整数数组a[1,2,...n]，一个长度为m的查询数组q[1,2,...m],q[i]=(val,minlen,maxlen)。请你按输入顺序处理这m次查询，对于第i次查询q[i[=(val,minlen,maxlen);请你输出是否存在一个a的子数组s满足min(s)≥val且s的长度在minlen和maxlen之间。
输入格式
第一行输入一个正整数n
第二行有n个正整数，a[1,2,...n]
第三行输入一个正整数m
接下来m行，每行三个正整数，表示q[i]的三个数，val,minlen,maxlen
1<=n,m<=1e5
1<=val,a[i]<=1e9
1<=minlen<=maxlen<=n
输出格式
输出m行，如果存在输出“Yes”，否则输出“No”
输入/输出例子1
输入：
3
1 3 2
6
1 1 3
1 1 2
3 2 2
3 1 2
4 1 1
2 1 2
输出：
Yes
Yes
No
Yes
No
Yes
样例解释
无
很有意思的一道压轴题。
对于正面无法很好回答的多次询问，我们可以自己构造答案，再对应询问给出构造答案
构造部分
首先可以发现，在一个区间中删去某些数，min肯定不会减小，所以maxlen没用，我们只需要minlen
比如{1,2,3,4}中的min是1，我们删去{3,4}，min还是1，删去{1,2}，min是3，无论怎么样，min不会减小，但是可能会增加
对于每个a[i]，我们都可以构造一个答案，假设构造的区间是[L, R]，只要L~R区间内每个数都>=a[i]，就可以满足构造条件，使得这个区间内的最小值是a[i]
我们构造的答案区间长度就可以确定下来。我们现在可以尝试用构造的这些答案去跟询问一一对应
所以我们构造的答案包含两个值，一个是答案区间长度（后续称为len）；一个是a[i]，也就是区间中的min值，我们假定这个构造的答案是 f[i]
构造部分就结束了，接下来我们考虑如何把构造出来的答案对应上询问
对应询问部分
我们对这些f[i]排个序，从小到大，按照min去排序，这样就对于后来询问所给出的val，我们就可以考虑去这些答案区间中二分查找min值
二分f[i].min>=val，如何看看是否满足题意，f[i].len>=minlen，即可
由于排序后，min是从小到大的，根据第一点小发现，我们可以对len搞一个长度的后缀最大值，这样才可以保证满足答案
为什么可以这样？题目只是要求min(s)≥val就行，那么比min大的数肯定也是可以满足要求的，但是比min大的数它的最终区间长度可能比min要大！
例如排完序后的f[i]是这样的：
f[1]={1, 3}
f[2]={2, 2}
f[3]={3, 3}
我们先在求val=2，minlen=3
但是我们二分查表发现f[2].min>=val，但是 f[2].len=2，是不满足的，会被误判是”No“
但是答案其实是”Yes“，因为 f[3].min>=val，也是满足题目要求”min(s)>=val，所以f[3]的长度对这个答案也是有影响的，所以我们要整一个后缀最大值
我们看看后缀最大值是否>=minlen，是的话就是"Yes"，反之亦然
这里的时间复杂度是 O(logn)，仅有一个二分而已
我们再考虑回去
如何减小构造的时间复杂度呢？暴力就是O(n^2)
我们可以不用一一枚举，用单调队列可以预处理（找第一个<a[i]的数，找极值就是单调队列嘛！），也就是 O(n)
这里给出O(n^2 log n)复杂度的做法
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
struct node
{
int min, len;
}b[N];
int n, a[N], m, val, Minlen, Maxlen;
/*
int find(int L, int R, int x)
{
for (int i=R; i>=L; i--)
if (a[i]<a[x]) return i+1;
return L;
}*/
bool cmp(node a, node b)
{
return a.min<b.min;
}
int main()
{
scanf("%d", &n);
for (int i=1; i<=n; i++) scanf("%d", &a[i]);
scanf("%d", &m);
for (int i=1; i<=n; i++)
{
int sum=0;
// L=find(1, i, i), R=find(i+1, n, i);
for (int j=i-1; j>=1; j--)
{
if (a[j]<a[i]) break;
sum++;
}
// if (i==2) printf("{%d}", sum);
for (int j=i+1; j<=n; j++)
{
if (a[j]<a[i]) break;
sum++;
}
b[i].min=a[i], b[i].len=sum+1;
}
sort(b+1, b+1+n, cmp);
for (int i=n-1; i>=1; i--) b[i].len=max(b[i].len, b[i+1].len);
/*
printf("\n");
for (int i=1; i<=n; i++) printf("%d %d\n", b[i].min, b[i].len);
printf("\n");
*/
while (m--)
{
scanf("%d%d%d", &val, &Minlen, &Maxlen);
int L=1, R=n, x=0;
while (L<=R)
{
int mid=(L+R)>>1;
if (b[mid].min>=val) x=mid, R=mid-1;
else L=mid+1;
}
//printf("{%d}", x);
if (b[x].min<val) printf("No\n");
else
{
if (b[x].len>=Minlen) printf("Yes\n");
else printf("No\n");
}
}
return 0;
}
/*
3
1 3 2
1
3 1 2
*/
标签：val,min,int,询问,新思路,构造,len,Yes From： https://www.cnblogs.com/didiao233/p/18361757