来自FallDream的博客，未经允许，请勿转载，谢谢，

---

给定一个序列A[i]，每次询问l,r，求[l,r]内最长子串，使得该子串为不上升子串或不下降子串

n,q<=50000

线段树维护区间左右是谁，从左端开始／到右端结束的最长上升／下降子串长度即可。

复杂度nlogn

#include
     
      #include
      
       #define MN 50000using namespace std;inline int read(){    int x = 0 , f = 1; char ch = getchar();    while(ch < '0' || ch > '9'){ if(ch == '-') f = -1;  ch = getchar();}    while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}    return x * f;}struct data{
   int l1,l2,r1,r2,ans,L,R,len;    data(){}    data(int x){l1=l2=r1=r2=ans=len=1;L=R=x;}    friend data operator +(const data&a,const data&b)    {        data c;c.L=a.L;c.R=b.R;c.len=a.len+b.len;        c.ans=max(max(a.ans,b.ans),max(a.r2,b.l2));        if(b.L>=a.R) c.ans=max(c.ans,a.r1+b.l1);        if(b.L<=a.R) c.ans=max(c.ans,a.r2+b.l2);        c.l1=a.l1==a.len?a.l1+(b.L>=a.R?b.l1:0):a.l1;        c.l2=a.l2==a.len?a.l2+(b.L<=a.R?b.l2:0):a.l2;        c.r1=b.r1==b.len?b.r1+(b.L>=a.R?a.r1:0):b.r1;        c.r2=b.r2==b.len?b.r2+(b.L<=a.R?a.r2:0):b.r2;        return c;    }};struct Tree{
   int l,r;data x;}T[MN*4+5];int n,m,a[MN+5];void build(int x,int l,int r){    if((T[x].l=l)==(T[x].r=r)){T[x].x=data(a[l]);return;}    int mid=l+r>>1;    build(x<<1,l,mid);build(x<<1|1,mid+1,r);    T[x].x=T[x<<1].x+T[x<<1|1].x;}data Query(int x,int l,int r){    if(T[x].l==l&&T[x].r==r) return T[x].x;    int mid=T[x].l+T[x].r>>1;    if(r<=mid) return Query(x<<1,l,r);    else if(l>mid) return Query(x<<1|1,l,r);    else return Query(x<<1,l,mid)+Query(x<<1|1,mid+1,r);}int main(){    n=read();    for(int i=1;i<=n;++i)a[i]=read();    m=read();build(1,1,n);    for(int i=1;i<=m;++i)    {        int l=read(),r=read();        data x=Query(1,l,r);        x.ans=max(x.ans,max(x.l1,x.l2));        x.ans=max(x.ans,max(x.r1,x.r2));        printf("%d\n",x.ans);    }    return 0;}