2024 Jiangsu Collegiate Programming Contest E. Divide 题解 主席树
Divide
题目描述
Given an integer sequence
a
1
,
a
2
,
…
,
a
n
a_1,a_2,\ldots,a_n
a1,a2,…,an of length
n
n
n. For an interval
a
l
,
…
,
a
r
a_l,\ldots,a_r
al,…,ar in this sequence, a Reduce operation divides the maximum value of the interval by
2
2
2 (rounding down). If there are multiple maximum values, choose the one with the smallest index. There are
q
q
q queries. Given three integers
l
,
r
,
k
l,r,k
l,r,k each time, query the maximum value of the interval after performing
k
k
k Reduce operations on the
a
l
,
…
,
a
r
a_l,\ldots,a_r
al,…,ar interval. The queries are independent of each other. That is to say, each time the query starts from the initially given sequence.
输入描述
The two integers
n
,
q
n,q
n,q (
1
≤
n
,
q
≤
1
0
5
1\le n,q\le 10^5
1≤n,q≤105) in the first line represent the sequence length and the number of queries.
The second line contains
n
n
n integers
a
1
,
a
2
,
…
,
a
n
a_1,a_2,\ldots,a_n
a1,a2,…,an (
0
≤
a
i
≤
1
0
5
0\le a_i\le 10^5
0≤ai≤105).
The next
q
q
q lines each have three integers
l
,
r
,
k
l,r,k
l,r,k (
1
≤
l
≤
r
≤
n
,
0
≤
k
≤
1
0
9
1\le l\le r\le n,0\le k\le 10^9
1≤l≤r≤n,0≤k≤109), representing a query.
输出描述
For each query, output an integer in one line, representing the maximum value of the interval since the operation started from the initial sequence.
样例 #1
样例输入 #1
3 2
2 0 2
2 3 0
1 3 0
样例输出 #1
2
2
样例 #2
样例输入 #2
6 6
9 5 0 3 6 7
1 4 7
3 3 233
6 6 0
3 4 4
4 5 15
1 1 0
样例输出 #2
1
0
7
0
0
9
思路
将题目所给数组进行扩充。例如，对于样例#2，数组 9 5 0 3 6 7 可通过对每个数不断除以
2
2
2 直至为
0
0
0 (
0
0
0也加入扩充后数组) 扩充为 9 4 2 1 0 5 2 1 0 0 3 1 0 6 3 1 0 7 3 1 0。这样，对于每个询问，相当于在扩充后的数组中寻找第
k
+
1
k+1
k+1 大值。但由于询问中的区间是原数组中的区间，所以我们需利用 map 构建原数组区间到扩充后数组区间的映射。此外，对于询问中
k
+
1
k+1
k+1 的值大于扩充后区间中元素个数的情况，需要特判答案为
0
0
0。
代码
#include
using namespace std;
using i64 = long long;
typedef long long ll;
const int maxn = 2e6;
int tot, n, m;
int sum[(maxn << 5) + 10], rt[maxn + 10], ls[(maxn << 5) + 10], rs[(maxn << 5) + 10];
int a[maxn + 10], ind[maxn + 10], len;
int getid(const int &val)
{
return lower_bound(ind + 1, ind + len + 1, val) - ind;
}
int build(int l, int r)
{
int root = ++tot;
if (l == r)
{
return root;
}
int mid = l + r >> 1;
ls[root] = build(l, mid);
rs[root] = build(mid + 1, r);
return root;
}
int update(int k, int l, int r, int root)
{
int dir = ++tot;
ls[dir] = ls[root], rs[dir] = rs[root];
sum[dir] = sum[root] + 1;
if (l == r)
{
return dir;
}
int mid = l + r >> 1;
if (k <= mid)
{
ls[dir] = update(k, l, mid, ls[dir]);
}
else
{
rs[dir] = update(k, mid + 1, r, rs[dir]);
}
return dir;
}
int query(int u, int v, int l, int r, int k)
{
int mid = l + r >> 1;
int x = sum[ls[v]] - sum[ls[u]];
if (l == r)
{
return l;
}
if (k <= x)
{
return query(ls[u], ls[v], l, mid, k);
}
else
{
return query(rs[u], rs[v], mid + 1, r, k - x);
}
}
map<int, pair<int, int>> mp; // 构建原来数组中下标到扩充后数组中下标的映射
void init()
{
cin >> n >> m;
int idx = 0; // 扩充数组的索引
int x;
for (int i = 1; i <= n; i++)
{
cin >> x;
mp[i].first = idx + 1; // 一个原数组中的元素x经扩充后的区间的左端点
while (x) // 元素x扩充，扩充到区间[mp[i].first,mp[i].second]里面
{
a[++idx] = x;
x /= 2;
}
a[++idx] = 0; // ai可能等于0，所以要单独将0加入扩充后区间
mp[i].second = idx; // 一个原数组中的元素x经扩充后的区间的右端点
}
// 离散化构建主席树，主席树可用来求出扩充后数组的区间第k小值
memcpy(ind, a, sizeof(ind));
sort(ind + 1, ind + idx + 1);
len = unique(ind + 1, ind + idx + 1) - ind - 1;
rt[0] = build(1, len);
for (int i = 1; i <= idx; i++)
{
rt[i] = update(getid(a[i]), 1, len, rt[i - 1]);
}
}
int l, r, k;
void work()
{
while (m--)
{
cin >> l >> r >> k;
k++; // 当k=i时，求的是第i+1大数，所以k需要++
// 主席树询问区间：左开右闭
int left = mp[l].first - 1;
int right = mp[r].second;
// 因为左开右闭，所以区间长度即为right-left，而当区间长度小于k+1时，第k+1大值一定为0
if (right - left < k)
cout << 0 << '
';
else
cout << ind[query(rt[left], rt[right], 1, len, right - left + 1 - k)] << '
'; // right - left + 1 - k的运算是将求第k大值转化为求第right - left + 1 - k小值
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
init();
work();
return 0;
}
