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
正解：线段树。
线段树傻逼题，维护$8$个标记即可。
1 //It is made by wfj_2048~ 2 #include <algorithm> 3 #include <iostream> 4 #include <cstring> 5 #include <cstdlib> 6 #include <cstdio> 7 #include <vector> 8 #include <cmath> 9 #include <queue> 10 #include <stack> 11 #include <map> 12 #include <set> 13 #define N (100010) 14 #define ls (x<<1) 15 #define rs (x<<1|1) 16 #define il inline 17 #define RG register 18 #define ll long long 19 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout) 20 21 using namespace std; 22 23 struct data{ int mx,mn,lmx,rmx,lmn,rmn,L,R; }t[4*N]; 24 25 int a[N],n,Q; 26 27 il int gi(){ 28 RG int x=0,q=1; RG char ch=getchar(); 29 while ((ch<'0' || ch>'9') && ch!='-') ch=getchar(); 30 if (ch=='-') q=-1,ch=getchar(); 31 while (ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar(); 32 return q*x; 33 } 34 35 il void pushup(RG data &x,RG data l,RG data r,RG int h,RG int t,RG int mid){ 36 x.mx=max(l.mx,r.mx); if (l.R<=r.L) x.mx=max(x.mx,l.rmx+r.lmx); 37 x.mn=max(l.mn,r.mn); if (l.R>=r.L) x.mn=max(x.mn,l.rmn+r.lmn); 38 x.lmx=(l.mx==mid-h+1 && l.R<=r.L) ? l.mx+r.lmx : l.lmx; 39 x.rmx=(r.mx==t-mid && l.R<=r.L) ? r.mx+l.rmx : r.rmx; 40 x.lmn=(l.mn==mid-h+1 && l.R>=r.L) ? l.mn+r.lmn : l.lmn; 41 x.rmn=(r.mn==t-mid && l.R>=r.L) ? r.mn+l.rmn : r.rmn; 42 x.L=l.L,x.R=r.R; return; 43 } 44 45 il void build(RG int x,RG int l,RG int r){ 46 if (l==r){ 47 t[x].mx=t[x].mn=t[x].lmx=t[x].rmx=t[x].lmn=t[x].rmn=1; 48 t[x].L=t[x].R=a[l]; return; 49 } 50 RG int mid=(l+r)>>1; build(ls,l,mid),build(rs,mid+1,r); 51 pushup(t[x],t[ls],t[rs],l,r,mid); return; 52 } 53 54 il data query(RG int x,RG int l,RG int r,RG int xl,RG int xr){ 55 if (xl<=l && r<=xr) return t[x]; RG int mid=(l+r)>>1; 56 if (xr<=mid) return query(ls,l,mid,xl,xr); 57 else if (xl>mid) return query(rs,mid+1,r,xl,xr); 58 else{ 59 RG data res; 60 pushup(res,query(ls,l,mid,xl,mid),query(rs,mid+1,r,mid+1,xr),xl,xr,mid); 61 return res; 62 } 63 } 64 65 il int find(RG int l,RG int r){ 66 RG data res=query(1,1,n,l,r); 67 return max(res.mx,res.mn); 68 } 69 70 il void work(){ 71 n=gi(); for (RG int i=1;i<=n;++i) a[i]=gi(); 72 build(1,1,n); Q=gi(); 73 for (RG int i=1,l,r;i<=Q;++i) 74 l=gi(),r=gi(),printf("%d ",find(l,r)); 75 return; 76 } 77 78 int main(){ 79 File("substring"); 80 work(); 81 return 0; 82 }