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