AcWing
  • 首页
  • 题库
  • 题解
  • 分享
  • 问答
  • 活动
  • 应用
  • 吐槽
  • 登录/注册

AcWing 802. 区间和

作者: 作者的头像   CodeWater ,  2021-02-23 19:35:09 ,  阅读 12


0


没有unique(去重)函数的,可以参考这个实现:
不重复元素满足这两个性质
acwing802区间和(unique函数).png

//返回的是一个迭代器,双指针算法
/*
第一个指针j是遍历所有的数,第二个指针是指向当前存到了第几个不同的数
*/
vector<int>::iterator unique(vector<int> &a)
{
    int j = 0;
    for (int i = 0; i < a.size(); i ++ )
    //若不满足上述途中的两个性质, !i是第一个数
        if (!i || a[i] != a[i - 1])
        //把当前这个数付给前面,j指针再往后走
            a[j ++ ] = a[i];
    // a[0] ~ a[j - 1] 所有a中不重复的数

//这样就是从0到j这个位置的就是所有不同的数。
    return a.begin() + j;
}

题解代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

//pair存储每个操作
typedef pair<int,int> PII;

const int N = 300010;
//a 是存储题目给定的数  s是前缀和
int a[N], s[N];
int n , m;
//vector是所有要离散化的值
vector<int> alls;
//add插入操作  query是求操作
vector<PII> add , query;

//求一下x这个值离散化之后的结果
int find(int x){
    //从l——r之间找一个值
    int l = 0 , r = alls.size() - 1;
    while(l < r){
        //mid中点
        int  mid = l + r >> 1;
        //找到大于等于x的最小值
        if(alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    //映射到从1开始的自然数,因为这道题会用到前缀和,所用从1开始,减少一些边界情况
    return r + 1;
}

int main(){
    cin>>n>>m;
    for(int i = 0 ; i < n ; i++){
        int x , c ;
        cin>> x >> c;
        //插入操作,在下标x的位置加上c
        add.push_back({x,c});
        //要把下标x进行离散化,那么就需要把这个x加入到待离散化的数组里面去
        alls.push_back(x);
    }
    //输入进行m次操作
    for(int i = 0 ; i < m ; i++){
        int l , r;
        cin>> l >> r;

        query.push_back({l,r});
        //l 和 r坐标是需要离散化的,所以也把他们加入到待离散化的数组里面去
        alls.push_back(l);
        alls.push_back(r);
    }//这个时候就已经把所有需要离散化的下标放进了数组。

    //下一步就需要对alls数组进行去重
    //先排序
    sort(alls.begin(),alls.end());
    //把重复的元素去掉,unique函数把不重复的元素放在前面重复的放在后面,返
    //回不重复元素的最后一个位置
    alls.erase(unique(alls.begin(),alls.end()),alls.end());

    //分别处理一下两种操作
    for(auto item : add){
        //首先求一下x这个值离散化之后的结果是多少
        int x = find(item.first);
        //在离散化之后的坐标上加上要加的数
        a[x] += item.second;

    }

    //预处理一下前缀和
    for(int i = 1 ; i <= alls.size() ; i++) s[i] = s[i - 1] + a[i];

    //处理询问
    for(auto  item : query){
        //左边是item.first离散化之后的结果,item.first存的是左区间
        //r同理
        int l = find(item.first) , r = find(item.second);
        //中间所有数的个数的和,用前缀和公式来
        cout<<s[r] - s[l - 1]<<endl;

    }

    return 0;
}

0 评论

你确定删除吗?

© 2018-2021 AcWing 版权所有  |  京ICP备17053197号-1
联系我们  |  常见问题
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标
请输入绑定的邮箱地址
请输入注册信息