2024 Jiangsu Collegiate Programming Contest E. Divide 题解 主席树

Divide

题目描述

Given an integer sequence $a_1,a_2,\dots ,a_n$ of length $n$. For an interval $a_l,\dots ,a_r$ in this sequence, a Reduce operation divides the maximum value of the interval by $2$ (rounding down). If there are multiple maximum values, choose the one with the smallest index. There are $q$ queries. Given three integers $l,r,k$ each time, query the maximum value of the interval after performing $k$ Reduce operations on the $a_l,\dots ,a_r$ 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$ ($1\le n,q\le 10^5$) in the first line represent the sequence length and the number of queries.

The second line contains $n$ integers $a_1,a_2,\dots ,a_n$ ($0\le a_i\le 10^5$).

The next $q$ lines each have three integers $l,r,k$ ($1\le l\le r\le n,0\le k\le 10^9$), 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$ 直至为 $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$ 大值。但由于询问中的区间是原数组中的区间，所以我们需利用 map 构建原数组区间到扩充后数组区间的映射。此外，对于询问中 $k+1$ 的值大于扩充后区间中元素个数的情况，需要特判答案为 $0$。

代码

#include <bits/stdc++.h>
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大值一定为0if (right - left < k)cout << 0 << '\n';elsecout << ind[query(rt[left], rt[right], 1, len, right - left + 1 - k)] << '\n'; // right - left + 1 - k的运算是将求第k大值转化为求第right - left + 1 - k小值}
}int main()
{ios::sync_with_stdio(0);cin.tie(0);init();work();return 0;
}