题解：P10288 [GESP样题八级] 区间

Wy_x · 2024-04-03 18:31:32 · 题解

P10288 [GESP样题八级] 区间

My Blog

Solution：

由题可知，有 T 组数据，每组数据中给出 n 个数字，并伴随着 q 次询问，每次询问需要求区间 [l,r] 内数字 x 的出现次数。

其中，1 \le T \le 5，1 \le n,q \le 10^5，1 \le x \le 10^9。

容易想到，以 x 作为第一维，x 出现的坐标为第二维，建立记录数组。

易知，存储的坐标是由小到大单调递增的，故计算答案时，只需要在第 x 维上进行二分。\ 从该维上二分，第一个大于 r 的坐标在数组中的位置（指针）减去第一个大于等于 l 的坐标在数组中的位置（指针）。可证得，该差为非负整数，故直接输出即可。

但由于 x 的范围极大，每一维中的数据量也不定，若建满数组，空间太大。故，在实际代码中，需要用 map<int,vector<int>> mp; 代替上述解法中的数组。其余不变。

此外，由于 STL 常数比较大，数据规模也大，使用 cin 和 cout 容易超时，建议使用快读快写。

Code:

#include<stdio.h>
#include<map>
#include<vector>
#include<algorithm>

inline int read() // 快读
{
    int x=0,c=getchar(),f=0;
    for(;c<'0'||c>'9';f=c=='-',c=getchar());
    for(;c>='0'&&c<='9';c=getchar())
        x=(x<<1)+(x<<3)+(c^48);
    return f?-x:x;
}

inline void write(int x) // 快写
{
    if(x>9) write(x/10);
    putchar(x%10+'0');
}

using std::map;
using std::vector;

void solve()
{
    map<int,vector<int>> mp;
    //记录数字 x 出现的下标
    int n=read(),q;

    for(int i=1;i<=n;i++)// 输入 x 并推入 mp[x] 中
        mp[read()].push_back(i);

    q=read();
    while(q--)
    {
        int l=read(),r=read(),x=read();
        //输入[l,r]和数字 x

        //二分求数量
        //令指针相减，得出区间长度
        write(upper_bound(mp[x].begin(),mp[x].end(),r)
        -lower_bound(mp[x].begin(),mp[x].end(),l));

        putchar('\n');
    }
}

signed main()
{
    int t=read();//t 组数据 
    while(t--) solve();

    return 0;
}

题解：P10288 [GESP样题 八级] 区间

Solution：

Code:

题解：P10288 [GESP样题八级] 区间