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

Problem

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

Description

给定一个序列，每次询问，求内最长子串，使得该子串为不上升子串或不下降子串

Input

第一行，表示数组有多少元素
接下来一行为个整数
接下来一个整数，表示询问数量
接下来行，每行个整数

Output

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

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

样例解释
五个询问分别对应

HINT

Source

一个读错题的沙茶

标签：线段树

Solution

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

Code

#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;
}