我也不知道题目名字是什么

Time Limit: 10 Sec Memory Limit: 512 MB

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

Sample Output

6
　6
　5
　6
　4

HINT

N,Q<=50000

Solution

直接上线段树，记录一下一个区间内：左边最长，右边最长，整体最优。再分一下不下降和不上升即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<bits/stdc++.h>
using namespace std;

const int ONE = 500005;
const int INF = 2147483640;

int n,Q;
int x,y;
int a[ONE];

struct power
{
    int len;
    int Lval, Rval;
    int Lup,Ldn, Rup,Rdn;
    int Maxup, Maxdn;

    friend power operator +(power a, power b)
    {
        power A;
        A.len = a.len + b.len;
        A.Lval = a.Lval;    A.Rval = b.Rval;

        A.Lup = a.Lup;    if(a.Lup == a.len && a.Rval <= b.Lval) A.Lup += b.Lup;
        A.Ldn = a.Ldn;    if(a.Ldn == a.len && a.Rval >= b.Lval) A.Ldn += b.Ldn;

        A.Rup = b.Rup;    if(b.Rup == b.len && a.Rval <= b.Lval) A.Rup += a.Rup;
        A.Rdn = b.Rdn;    if(b.Rdn == b.len && a.Rval >= b.Lval) A.Rdn += a.Rdn;

        A.Maxup = max(a.Maxup, b.Maxup);
        A.Maxdn = max(a.Maxdn, b.Maxdn);

        if(a.Rval <= b.Lval) A.Maxup = max(A.Maxup, a.Rup+b.Lup);
        if(a.Rval >= b.Lval) A.Maxdn = max(A.Maxdn, a.Rdn+b.Ldn);

        return A;
    }
}Node[ONE];

int get()
{
    int res=1,Q=1;char c;
    while( (c=getchar())<48 || c>57 )
        if(c=='-')Q=-1;
    res=c-48;
    while( (c=getchar())>=48 && c<=57 )
        res=res*10+c-48;
    return res*Q;
}

void Build(int i,int l,int r)
{
    if(l == r)
    {
        Node[i].Lval = Node[i].Rval = a[l];
        Node[i].len = 1;
        Node[i].Lup = Node[i].Rup = Node[i].Ldn = Node[i].Rdn = 1;
        Node[i].Maxup = Node[i].Maxdn = 1;
        return;
    }

    int mid = l+r>>1;
    Build(i<<1, l,mid);    Build(i<<1|1, mid+1,r);
    Node[i] = Node[i<<1] + Node[i<<1|1];
}

power Query(int i,int l,int r,int L,int R)
{
    if(L==l && r==R) return Node[i];
    int mid = l+r>>1;
    if(mid+1 > R) return Query(i<<1, l,mid,L,R);
    else if(L > mid) return Query(i<<1|1, mid+1,r,L,R);
    else return Query(i<<1, l,mid,L,mid) + Query(i<<1|1, mid+1,r,mid+1,R);
}

int main()
{
    n = get();
    for(int i=1; i<=n; i++) a[i] = get();
    Build(1,1,n);

    Q = get();
    while(Q--)
    {
        x = get();    y = get();
        power res = Query(1,1,n,x,y);
        printf("%d\n", max(res.Maxup, res.Maxdn) );
    }
}