beautiful - NekoMio's Blog

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一遍在标号

1
#include <algorithm>
2
#include <cstdio>
3
#include <cstring>
4
using namespace std;
5
struct data
6
{
7
    int a, pos;
8
    bool operator<(const data &b) const
9
    {
10
        return a == b.a ? pos < b.pos : a < b.a;
11
    }
12
} a[2005];
13
int comp(const data &a, const data &b)
14
{
15
    return a.pos < b.pos;
16
}
17
int full = 13;
18
struct Trie
19
{
20
    struct Trie_Node
21
    {
22
        Trie_Node *ch[2];
23
        int s;
24
        Trie_Node()
25
        {
26
            ch[0] = ch[1] = NULL;
27
            s = 0;
28
        }
29
    } * root[2005], *null;
30
    Trie()
31
    {
32
        null = new Trie_Node();
33
        null->ch[0] = null->ch[1] = null;
34
        root[0] = new Trie_Node();
35
        root[0]->ch[1] = root[0]->ch[0] = null;
36
    }
37
    Trie_Node *NewNode()
38
    {
39
        Trie_Node *rt = new Trie_Node();
40
        rt->ch[0] = rt->ch[1] = null;
41
        return rt;
42
    }
43
    void copy(Trie_Node *&a, Trie_Node *b)
44
    {
45
        if (b == null)
46
            a = null;
47
        else
48
            a = NewNode(), *a = *b;
49
    }
50
    void Insert(int x, int cnt)
51
    {
52
        copy(root[cnt], root[cnt - 1]);
53
        Trie_Node *rt1 = root[cnt], *rt2 = root[cnt - 1];
54
        for (int i = full; i >= 0; i--)
55
        {
56
            int k = (x >> i) & 1;
57
            copy(rt1->ch[k], rt2->ch[k]);
58
            if (rt1->ch[k] == null)
59
                rt1->ch[k] = NewNode();
60
            rt1 = rt1->ch[k], rt2 = rt2->ch[k];
61
            rt1->s++;
62
        }
63
    }
64
    int kth(int k, int l, int r)
65
    {
66
        int res = 0;
67
        Trie_Node *rt1 = root[r], *rt2 = root[l - 1];
68
        for (int i = full; i >= 0; i--)
69
        {
70
            if (k > rt1->ch[0]->s - rt2->ch[0]->s)
71
            {
72
                k -= (rt1->ch[0]->s - rt2->ch[0]->s);
73
                res |= (1 << i);
74
                rt1 = rt1->ch[1], rt2 = rt2->ch[1];
75
            }
76
            else
77
            {
78
                rt1 = rt1->ch[0], rt2 = rt2->ch[0];
79
            }
80
        }
81
        return res;
82
    }
83
} root;
84
int pos[2005];
85
int Maxn[2005 << 2];
86
int Max[2005 << 2];
87
#define lch l, m, rt << 1
88
#define rch m + 1, r, rt << 1 | 1
89
void Update(int rt)
90
{
91
    Max[rt] = max(Max[rt << 1], Max[rt << 1 | 1]);
92
}
93
void buildtree(int l, int r, int rt)
94
{
95
    if (l == r)
96
    {
97
        Max[rt] = Maxn[l];
98
        return;
99
    }
100
    int m = l + r >> 1;
101
    buildtree(lch);
102
    buildtree(rch);
103
    Update(rt);
104
}
105
int Query(int L, int R, int l, int r, int rt)
106
{
107
    if (L <= l && R >= r)
108
        return Max[rt];
109
    int m = l + r >> 1;
110
    int MAX = 0;
111
    if (L <= m)
112
        MAX = max(MAX, Query(L, R, lch));
113
    if (R > m)
114
        MAX = max(MAX, Query(L, R, rch));
115
    return MAX;
116
}
117
int main()
118
{
119
    int n;
120
    scanf("%d", &n);
121
    for (int i = 1; i <= n; i++)
122
    {
123
        scanf("%d", &a[i].a);
124
        a[i].pos = i;
125
    }
126
    sort(a + 1, a + n + 1);
127
    for (int i = 1; i <= n; i++)
128
    {
129
        a[i].a = i;
130
        pos[a[i].a] = a[i].pos;
131
    }
132
    sort(a + 1, a + n + 1, comp);
133
    for (int i = 1; i <= n; i++)
134
        root.Insert(a[i].a, i);
135
    for (int i = 1; i <= n; i++)
136
    {
137
        for (int j = 1; j <= i; j++)
138
        {
139
            if ((i - j + 1) & 1)
140
            {
141
                int k = pos[root.kth((i - j + 1) / 2 + 1, j, i)];
142
                Maxn[k] = max(Maxn[k], (i - j + 1));
143
            }
144
        }
145
    }
146
    buildtree(1, n, 1);
147
    int Q, l, r;
148
    scanf("%d", &Q);
149
    while (Q--)
150
    {
151
        scanf("%d%d", &l, &r);
152
        printf("%d\n", Query(l, r, 1, n, 1));
153
    }
154
}