[Acwing] 802. 区间和

事先声明 代码是 @滑稽_ωﾉ (河北King 芜湖~)

前言:

区间和 ？ RMQ,线段树,树状数组,前缀和 ? (卧槽 这个数据范围好大 —>离散化)

(怎么离散化 map? 然后每次都标记 太慢了吧)

思路

• 先将 原来的 x 存入到数组里面

• 再将 需要查询的 数组也 插入到这个数组里面 (当然二分处理的好 也可以不用 只是方便理解)

• 然后对这个数组 进行排序 和 去重

• 然后就前缀和 (不过需要对sum 数组 先加c[i])

• 最后查询的时候 直接sum[r] - sum[l-1] 即可

不过为了 减少时间 所以 我们 每次 查询 离散化的表的时候 都用二分 进行查询

总结

也就是离散化的操作 难懂 但是自己过一遍也就 都懂了

就是将 大且散的 坐标x 用 一个数组存 然后排序(使得能和x坐标一样)

然后用二分 进行查询就行

C++(1400ms 自己写的话应该是300 - 500 ms)

#include 
using namespace std;
const int N = 4e5+10;
vector v;
int find(int x)
{
    return lower_bound(v.begin(),v.end(),x) - v.begin();
    /// 第一个大于等于
    /// upper 第一个大于
}

int n,m;
int x[N],c[N],l[N],r[N],sum[N];
void solve()
{
    cin>>n>>m;
    for(int i = 0 ;i>x[i]>>c[i];
        v.push_back(x[i]);
    }

    for(int i=0;i>l[i]>>r[i];
        v.push_back(l[i]);
        v.push_back(r[i]);
    }

    v.push_back(-2e9);

    sort(v.begin(),v.end());

    ///删除连续重复的值
    v.erase(unique(v.begin(),v.end()),v.end());

    for(int i =0 ;i