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
6
5
6
4
样例解释
五个询问分别对应
[1,6][1,6][2,6][1,6][6,9]
HINT
N,Q<=50000
Source
好像写个线段树就可以维护区间信息了？？？
我写了个线段树分治啊啊啊。。。
首先对于询问在区间上打上标记，如果到了叶结点就可以停下来用整个区间的答案来更新。
每次考虑跨过中点的线段，前缀后缀扫一下就好了。
#include<cstdio>
#include<cctype>
#include<queue>
#include<cstring>
#include<algorithm>
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define ren for(int i=first[x];i;i=next[i])
using namespace std;
const int BufferSize=1<<16;
char buffer[BufferSize],*head,*tail;
inline char Getchar() {
if(head==tail) {
int l=fread(buffer,1,BufferSize,stdin);
tail=(head=buffer)+l;
}
return *head++;
}
inline int read() {
int x=0,f=1;char c=Getchar();
for(;!isdigit(c);c=Getchar()) if(c=='-') f=-1;
for(;isdigit(c);c=Getchar()) x=x*10+c-'0';
return x*f;
}
const int maxn=50010;
const int maxnode=6000010;
struct Query {int l,r,id,next;}Q[maxnode];
int n,cnt,ans[maxn],f[maxn],g[maxn],A[maxn],first[maxn*4],res[maxn*4];
void AddQuery(int o,int ql,int qr,int id) {
Q[++cnt]=(Query){ql,qr,id,first[o]};first[o]=cnt;
}
void solve(int o,int l,int r) {
int mid=l+r>>1,lc=o<<1,rc=lc|1;
if(l==r) {
for(int i=first[o];i;i=Q[i].next) ans[Q[i].id]=max(ans[Q[i].id],1);
res[o]=1;
}
else {
for(int i=first[o];i;i=Q[i].next) {
Query& T=Q[i];
if(T.r<=mid) AddQuery(lc,T.l,T.r,T.id);
else if(T.l>mid) AddQuery(rc,T.l,T.r,T.id);
else if(T.l!=l||T.r!=r) AddQuery(lc,T.l,mid,T.id),AddQuery(rc,mid+1,T.r,T.id);
}
solve(lc,l,mid);solve(rc,mid+1,r);
res[o]=max(res[lc],res[rc]);
int ok;
ok=1;f[mid+1]=1;
rep(i,mid+2,r) {
if(A[i-1]<A[i]) ok=0;
f[i]=f[i-1]+ok;
}
ok=1;if(A[mid]<A[mid+1]) ok=0;f[mid]=ok;
dwn(i,mid-1,l) {
if(A[i+1]>A[i]) ok=0;
f[i]=f[i+1]+ok;
}
res[o]=max(res[o],f[l]+f[r]);
ok=1;g[mid+1]=1;
rep(i,mid+2,r) {
if(A[i-1]>A[i]) ok=0;
g[i]=g[i-1]+ok;
}
ok=1;if(A[mid]>A[mid+1]) ok=0;g[mid]=ok;
dwn(i,mid-1,l) {
if(A[i+1]<A[i]) ok=0;
g[i]=g[i+1]+ok;
}
res[o]=max(res[o],g[l]+g[r]);
for(int i=first[o];i;i=Q[i].next) {
Query& T=Q[i];
if(T.l<=mid&&T.r>mid) ans[T.id]=max(ans[T.id],max(f[T.l]+f[T.r],g[T.l]+g[T.r]));
if(T.l==l&&T.r==r) ans[T.id]=max(ans[T.id],res[o]);
}
}
}
int main() {
n=read();rep(i,1,n) A[i]=read();
int m=read();
rep(i,1,m) {
int l=read(),r=read();
AddQuery(1,l,r,i);
}
solve(1,1,n);
rep(i,1,m) printf("%d\n",ans[i]);
return 0;
}