4491: 我也不知道题目名字是什么
Time Limit: 10 Sec Memory Limit: 512 MB
Submit: 317 Solved: 174
[Submit][Status][Discuss]
Description
给定一个序列A[i]，每次询问l,r，求[l,r]内最长子串，使得该子串为不上升子串或不下降子串
Input
第一行n，表示A数组有多少元素
接下来一行为n个整数A[i]
接下来一个整数Q，表示询问数量
接下来Q行，每行2个整数l，r
Output
对于每个询问，求[l,r]内最长子串，使得该子串为不上升子串或不下降子串
Sample Input
9
1 2 3 4 5 6 5 4 3
5
1 6
1 7
2 7
1 9
5 9
1 2 3 4 5 6 5 4 3
5
1 6
1 7
2 7
1 9
5 9
Sample Output
6
6
5
6
4
//样例解释
五个询问分别对应
[1,6][1,6][2,6][1,6][6,9]
6
5
6
4
//样例解释
五个询问分别对应
[1,6][1,6][2,6][1,6][6,9]
HINT
N,Q<=50000
Source
想法：每个点存下$L_i$往左边最长合法，$R_i$往右边最长合法。$[l,r]$的答案即为$max\{R[l],R[l+1]...R[r-L[r]],min(L[r],r-l+1)\}$
用RMQ解决区间最值。
如果这道题有修改怎么做？需要支持区间赋值，求区间最值的线段树。
#include<cstdio> typedef long long ll;
template<class T>
inline void read(T&x)
{
x=;bool f=;char c=getchar();
while((c<''||c>'')&&c!='-') c=getchar();if(c=='-')f=, c=getchar();
while(c>=''&&c<=''){x=x*+c-''; c=getchar();}
x=f?-x:x;
}
const int MAXN();
int n,l,r,Ans,a[MAXN],T[MAXN],R[MAXN],L[MAXN],Q;
int max(int a,int b){return a>b?a:b;}
int F[][MAXN],logg[MAXN];
void DealRMQ()
{
for(int i=;i<=n;i++)logg[i]=logg[i>>]+;
for(int i=;i<=n;i++)F[][i]=R[i];
for(int j=;j<=logg[n];j++)
for(int i=;i<=n;i++)
{
int w=<<(j-); if(i+w>n)break;
F[j][i]=max(F[j-][i],F[j-][i+w]);
}
}
int Ask(int l,int r)
{
int k=logg[r-l+]; int w=<<k;
// fprintf(stderr,"%d %d\n",F[k][l],F[k][r-w+1]);
return max(F[k][l],F[k][r-w+]);
}
int main()
{
// freopen("C.in","r",stdin);
read(n);
for(int i=;i<=n;i++)read(a[i]);
for(int i=n;i>=;i--) T[i]=+(a[i+]>=a[i])*T[i+],R[i]=max(R[i],T[i]);
for(int i=n;i>=;i--) T[i]=+(a[i+]<=a[i])*T[i+],R[i]=max(R[i],T[i]);
for(int i=;i<=n;i++) T[i]=+(a[i-]<=a[i])*T[i-],L[i]=max(L[i],T[i]);
for(int i=;i<=n;i++) T[i]=+(a[i-]>=a[i])*T[i-],L[i]=max(L[i],T[i]);
// for(int i=1;i<=n;i++)
// printf("i:%d\n L:%d\n R:%d\n",i,L[i],R[i]);
DealRMQ();
read(Q);
for(int i=;i<=Q;i++)
{
read(l);read(r);
if(r-L[r]+<=l)Ans=r-l+;
else
{
Ans=L[r]; r=r-L[r];
// fprintf(stderr,"l:%d r%d\n",l,r);
Ans=max(Ans,Ask(l,r));
}
printf("%d\n",Ans);
}
return ;
}