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 
    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 
        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 
        return query(ls[u], ls[v], l, mid, k);
    }
    else
    {
        return query(rs[u], rs[v], mid + 1, r, k - x);
    }
}
map
    cin > n >> m;
    int idx = 0; // 扩充数组的索引
    int x;
    for (int i = 1; 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 
        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