2.1 题目描述#

Mavis 有一个序列（不必在乎这些细节），对于每个数都有一个在序列中的优美值，这个优 美值的定义是：找到序列中最长的一段，满足包含这个数并且这个数是这一段的中位数（以数 值为第一关键字，下标为第二关键字排序, 这样的话这一段的长度只有可能是奇数），那么这一

段的长度就是它的优美值。Mavis 说：“对于我每次手贱点出的左右端点[l, r]，我都要找到[l, r] 中的所有数中，最大的优美值” 但是Mavis 只会喊口号，不能解决问题，所以这个问题就交给你了

2.2 输入格式#

第一行输入n 接下来n 个整数，代表ai 接下来Q，代表有Q 个区间接下来Q 行，每行 两个整数l, r(l <= r)，表示区间的左右端点

2.3 输出格式#

对于每个区间的询问，输出答案

2.4 Sample Input#

8
16 19 7 8 9 11 20 16
8
3 8
1 4
2 3
1 1
5 5
1 2
2 8
7 8

2.5 Sample Output#

7
3
1
3
5
3
7
3

2.6 数据范围及约定#

对于30% 的数据满足：1 <= n;Q <= 50 对于70% 的数据满足：1 <= n;Q < 2000 对于100% 的数据满足，1 <= n <= 2000, 1 <= Q <= 100000, 1 <= ai <= 200

题解#

可以先预处理出一个数的最大的优美值
然后就查询就可以了，，区间最大

关键是预处理
可以用可持久化Trie N^2logN 求出每个区间的中位数
然后这个问题就解决了

先sort一遍在标号

#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
struct data
{
    int a, pos;
    bool operator<(const data &b) const
    {
        return a == b.a ? pos < b.pos : a < b.a;
    }
} a[2005];
int comp(const data &a, const data &b)
{
    return a.pos < b.pos;
}
int full = 13;
struct Trie
{
    struct Trie_Node
    {
        Trie_Node *ch[2];
        int s;
        Trie_Node()
        {
            ch[0] = ch[1] = NULL;
            s = 0;
        }
    } * root[2005], *null;
    Trie()
    {
        null = new Trie_Node();
        null->ch[0] = null->ch[1] = null;
        root[0] = new Trie_Node();
        root[0]->ch[1] = root[0]->ch[0] = null;
    }
    Trie_Node *NewNode()
    {
        Trie_Node *rt = new Trie_Node();
        rt->ch[0] = rt->ch[1] = null;
        return rt;
    }
    void copy(Trie_Node *&a, Trie_Node *b)
    {
        if (b == null)
            a = null;
        else
            a = NewNode(), *a = *b;
    }
    void Insert(int x, int cnt)
    {
        copy(root[cnt], root[cnt - 1]);
        Trie_Node *rt1 = root[cnt], *rt2 = root[cnt - 1];
        for (int i = full; i >= 0; i--)
        {
            int k = (x >> i) & 1;
            copy(rt1->ch[k], rt2->ch[k]);
            if (rt1->ch[k] == null)
                rt1->ch[k] = NewNode();
            rt1 = rt1->ch[k], rt2 = rt2->ch[k];
            rt1->s++;
        }
    }
    int kth(int k, int l, int r)
    {
        int res = 0;
        Trie_Node *rt1 = root[r], *rt2 = root[l - 1];
        for (int i = full; i >= 0; i--)
        {
            if (k > rt1->ch[0]->s - rt2->ch[0]->s)
            {
                k -= (rt1->ch[0]->s - rt2->ch[0]->s);
                res |= (1 << i);
                rt1 = rt1->ch[1], rt2 = rt2->ch[1];
            }
            else
            {
                rt1 = rt1->ch[0], rt2 = rt2->ch[0];
            }
        }
        return res;
    }
} root;
int pos[2005];
int Maxn[2005 << 2];
int Max[2005 << 2];
#define lch l, m, rt << 1
#define rch m + 1, r, rt << 1 | 1
void Update(int rt)
{
    Max[rt] = max(Max[rt << 1], Max[rt << 1 | 1]);
}
void buildtree(int l, int r, int rt)
{
    if (l == r)
    {
        Max[rt] = Maxn[l];
        return;
    }
    int m = l + r >> 1;
    buildtree(lch);
    buildtree(rch);
    Update(rt);
}
int Query(int L, int R, int l, int r, int rt)
{
    if (L <= l && R >= r)
        return Max[rt];
    int m = l + r >> 1;
    int MAX = 0;
    if (L <= m)
        MAX = max(MAX, Query(L, R, lch));
    if (R > m)
        MAX = max(MAX, Query(L, R, rch));
    return MAX;
}
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i].a);
        a[i].pos = i;
    }
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i++)
    {
        a[i].a = i;
        pos[a[i].a] = a[i].pos;
    }
    sort(a + 1, a + n + 1, comp);
    for (int i = 1; i <= n; i++)
        root.Insert(a[i].a, i);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            if ((i - j + 1) & 1)
            {
                int k = pos[root.kth((i - j + 1) / 2 + 1, j, i)];
                Maxn[k] = max(Maxn[k], (i - j + 1));
            }
        }
    }
    buildtree(1, n, 1);
    int Q, l, r;
    scanf("%d", &Q);
    while (Q--)
    {
        scanf("%d%d", &l, &r);
        printf("%d\n", Query(l, r, 1, n, 1));
    }
}