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

Data Range

对于所有数据, 满足:\(n, Q \leq 50000\)

Explanation

这道题一眼就能看出来是区间维护连通性对不对, 然后可以 \(O(1)\) 转移连通性的那种最水 的巨水数据结构题;

但是怎么写是个问题......

本蒟蒻作死最开始试图不用 struct status {...} 来写这道题, 结果 Splay 合并的时候简直吐血...... 外面的 Splay 写了 150 多行里面特判就不止 200 行这还只写完了一半......

于是掀桌子直接翻盘, 用 status 来维护状态 (听取了 @hld67890 大神的指导)

但是还是厚脸无耻地写 Splay 因为感觉比较好 (因为这道题是静态只查询不修改不插入的 完全完全的裸题所以可以直接 50 行以内写出线段树)

结果 Splay 分分钟炸掉;

后来发现还是作死......int build_tree(...) 的时候居然没有更新父亲导致旋转之后整棵树马上炸掉, 根本没法 splay(...); 所以修好以后简直不能忍;

又一个晚上调掉了单增单减的维护结果对拍一下分分钟爆掉;

最后只能用长度来维护, 魔改了几行以后居然就 AC 了......

这是得有多弱才能写出这样的玩意儿;

另外给大家一个忠告: 凡是遇到这种状态特别多的数据结构题, 一定要在 struct 里面 维护信息转移, 效果拔群

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
typedef long long lli;
const int maxn = 50010;

template <typename _T>
_T max(_T a, _T b, _T c) { return max(max(a, b), c); }

template <typename _T>
_T max(_T a, _T b, _T c, _T d) { return max(max(a, b), max(c, d)); }

template <typename _T>
_T& maximize(_T& a, _T b) { a = max(a, b); return a; }

struct status {
    int len, lval, rval;
    int lseqi, mseqi, rseqi;
    int lseqd, mseqd, rseqd;
    status(void) {
        len = 1;
        lseqi = mseqi = rseqi = 1;
        lseqd = mseqd = rseqd = 1;
        return ;
    } status(int val) {
        lval = rval = val; len = 1;
        lseqi = mseqi = rseqi = 1;
        lseqd = mseqd = rseqd = 1;
        return ;
    }
};

status union_status(status a, status b)
{
    status c;
    c.lval = a.lval;
    c.rval = b.rval;
    c.len = a.len + b.len;
    // Sticking on the left
    c.lseqi = a.lseqi;
    if (a.lseqi == a.len && a.rval <= b.lval)
        maximize(c.lseqi, a.len + b.lseqi);
    c.lseqd = a.lseqd;
    if (a.lseqd == a.len && a.rval >= b.lval)
        maximize(c.lseqd, a.len + b.lseqd);
    // Sticking on the right
    c.rseqi = b.rseqi;
    if (b.lseqi == b.len && b.lval >= a.rval)
        maximize(c.rseqi, b.len + a.rseqi);
    c.rseqd = b.rseqd;
    if (b.lseqd == b.len && b.lval <= a.rval)
        maximize(c.rseqd, b.len + a.rseqd);
    // In the middle
    c.mseqi = max(a.mseqi, b.mseqi);
    if (a.rval <= b.lval)
        maximize(c.mseqi, a.rseqi + b.lseqi);
    c.mseqd = max(a.mseqd, b.mseqd);
    if (a.rval >= b.lval)
        maximize(c.mseqd, a.rseqd + b.lseqd);
    // Finished
    return c;
}

class SplayTree
{
public:
    int arr_i[maxn][5];
    #define lc(_x) arr_i[_x][0]
    #define rc(_x) arr_i[_x][1]
    #define ch(_x,_y) arr_i[_x][_y]
    #define par(_x) arr_i[_x][2]
    #define size(_x) arr_i[_x][3]
    #define val(_x) arr_i[_x][4]
    status arr_s[maxn][1];
    #define state(_x) arr_s[_x][0]
    int ncnt, root;
    int make_node(int v)
    {
        int p = ++ncnt;
        lc(p) = rc(p) = par(p) = 0;
        size(p) = 1;
        val(p) = v;
        state(p) = status(v);
        return p;
    }
    void update_lazy(int p)
    {
        // Update interval size
        size(p) = size(lc(p)) + 1 + size(rc(p));
        // Incremental statistics
        if (!lc(p) && !rc(p)) {
            state(p) = status(val(p));
        } else if (!lc(p) && rc(p)) {
            state(p) = union_status(status(val(p)), state(rc(p)));
        } else if (lc(p) && !rc(p)) {
            state(p) = union_status(state(lc(p)), status(val(p)));
        } else if (lc(p) && rc(p)) {
            state(p) = union_status(state(lc(p)),
                union_status(status(val(p)), state(rc(p))
            ));
        }
        return ;
    }
    void rotate(int p)
    {
        int q = par(p), g = par(q);
        int x = p == rc(q), y = q == rc(g);
        ch(q, x) = ch(p, !x); if (ch(q, x)) par(ch(q, x)) = q;
        ch(p, !x) = q; par(q) = p;
        if (g) ch(g, y) = p; par(p) = g;
        update_lazy(q);
        update_lazy(p);
        return ;
    }
    void splay(int p, int t)
    {
        for (int q = 0; (q = par(p)) && q != t; rotate(p))
            if (par(q) && par(q) != t)
                rotate((p == rc(q)) == (q == rc(par(q))) ? q : p);
        if (t == 0) root = p;
        return ;
    }
    int find(int x)
    {
        int p = root;
        while (p) {
            if (x <= size(lc(p))) {
                p = lc(p);
                continue;
            } x -= size(lc(p));
            if (x <= 1) {
                return p;
            } x -= 1;
            p = rc(p);
        }
        return p;
    }
    int query(int l, int r)
    {
        int lp = find(l);
        int rp = find(r + 2);
        splay(lp, 0);
        splay(rp, root);
        int p = lc(rp);
        int res = max(state(p).mseqi, state(p).mseqd);
        return res;
    }
    int build_tree(int l, int r, int arr[])
    {
        if (l > r) return 0;
        int mid = (l + r) >> 1;
        int p = make_node(arr[mid - 1]);
        lc(p) = build_tree(l, mid - 1, arr);
        rc(p) = build_tree(mid + 1, r, arr);
        par(lc(p)) = p;
        par(rc(p)) = p;
        update_lazy(p);
        return p;
    }
    void init(int n, int arr[])
    {
        ncnt = 0;
        root = build_tree(1, n + 2, arr);
        return ;
    }
} st;

int n, Q;
int arr[maxn];

int main(int argc, char** argv)
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &arr[i]);
    st.init(n, arr);
    scanf("%d", &Q);
    for (int idx = 1; idx <= Q; idx++) {
        int l, r, res;
        scanf("%d%d", &l, &r);
        res = st.query(l, r);
        printf("%d\n", res);
    }
    return 0;
}