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