BZOJ4491 我也不知道题目名字是什么 <线段树>

Posted on Symbols count in article: 615 Reading time ≈ 2 mins.

Problem

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

Time  Limit:  10  Sec\mathrm{Time\;Limit:\;10\;Sec}
Memory  Limit:  512  MB\mathrm{Memory\;Limit:\;512\;MB}

Description

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

Input

第一行nn，表示AA数组有多少元素
接下来一行为nn个整数A[i]A[i]
接下来一个整数QQ，表示询问数量
接下来QQ行，每行22个整数l, rl,\ r

Output

对于每个询问，求[l,r][l,r]内最长子串，使得该子串为不上升子串或不下降子串

Sample Input

1
2
3
4
5
6
7
8
9
1 2 3 4 5 6 5 4 3
5
1 6
1 7
2 7
1 9
5 9

Sample Output

1
2
3
4
5
6
6
5
6
4

样例解释
五个询问分别对应[1,6][1,6][2,6][1,6][6,9][1,6][1,6][2,6][1,6][6,9]

HINT

N,Q≤50000N,Q\le 50000

Source

ByBy 一个读错题的沙茶

标签：线段树

Solution

稍有变形的基础线段树。
对于每个区间，维护其从左端开始的最长上升升下降序列、从右端开始的最长上升或下降序列、左端点键值、右端点键值、区间中最长序列长度、区间中最长上升序列长度、区间中最长下降序列长度，共99个值。然后updataupdata和downtagdowntag注意写法即可。

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
#include <bits/stdc++.h>
#define MAX_N 50000
using namespace std;
int n, m;    struct node {int lup, rup, ldn, rdn, lc, rc, l, mxup, mxdn;} tr[(MAX_N<<2)+5];
node update(node a, node b) {
    node ret;	ret.l = a.l+b.l, ret.lc = a.lc, ret.rc = b.rc;
    ret.lup = a.lup;	if (a.lup == a.l && a.rc <= b.lc)	ret.lup = a.l+b.lup;
    ret.ldn = a.ldn;	if (a.ldn == a.l && a.rc >= b.lc)	ret.ldn = a.l+b.ldn;
    ret.rup = b.rup;	if (b.rup == b.l && a.rc <= b.lc)	ret.rup = a.rup+b.l;
    ret.rdn = b.rdn;	if (b.rdn == b.l && a.rc >= b.lc)	ret.rdn = a.rdn+b.l;
    ret.mxup = max(a.mxup, b.mxup), ret.mxdn = max(a.mxdn, b.mxdn);
    if (a.rc <= b.lc)	ret.mxup = max(ret.mxup, a.rup+b.lup);
    if (a.rc >= b.lc)	ret.mxdn = max(ret.mxdn, a.rdn+b.ldn);
    return ret;
}
void build(int v, int s, int t) {
    if (s == t) {
        scanf("%d", &tr[v].lc), tr[v].rc = tr[v].lc;
        tr[v].lup = tr[v].rup = tr[v].ldn = tr[v].rdn = tr[v].l = tr[v].mxup = tr[v].mxdn = 1;
        return;
    }
    int mid = s+t>>1;
    build(v<<1, s, mid), build(v<<1|1, mid+1, t);
    tr[v] = update(tr[v<<1], tr[v<<1|1]);
}
node query(int v, int s, int t, int l, int r) {
    if (s >= l && t <= r)	return tr[v];
    int mid = s+t>>1; node ls, rs; bool fl = false, fr = false;
    if (l <= mid)	ls = query(v<<1, s, mid, l, r), fl = true;
    if (r >= mid+1)	rs = query(v<<1|1, mid+1, t, l, r), fr = true;
    return fl ? (fr ? update(ls, rs) : ls) : rs;
}
int main() {
    scanf("%d", &n), build(1, 1, n);
    scanf("%d", &m);
    while (m--) {
        int l, r;	scanf("%d%d", &l, &r);
        node ans = query(1, 1, n, l, r);
        printf("%d\n", max(ans.mxup, ans.mxdn));
    }
    return 0;
}