离散化

我的很长，你算一下

收藏本题

提交记录

题目描述

小e有一个很长很长的数组，数组的下标范围为[0,10^9][0,109]，初始时每个元素均为00。

现在，他想进行nn次操作，每次操作将某个下标ii处的元素加上xx。

然后他给出了qq次询问，每个询问格式为l\ rl r，你需要回答出下标在区间[l,r][l,r]内的所有元素的和。

输入描述

第一行：两个整数q,n,*。（1<=n,q<=1e5)

接下来n行：每行两个整数i,x。（0<=i<=1e9,0<=x1e4)

再接下q行：每行两个整数l,r*。（1<=l<=r<=1e9）

输出描述

共qq行，每行输出相应询问的答案。

输入样例1

4 2
0 2 
3 3
1 5
0 1
0 1
1 3

输出样例1

8
8

上面的题目是离散化的典型题目，这样的的题目的特点就是整个数组的大小远远大于我们的操作次数，所以我们要是对于整个数组进行遍历的话会超时，所以我们将每次的操作储存起来我们，然后二分查找对于的操作，利用前缀和进行求部分和，来实现对于数的定点加和求部分和。

同时这种我们先将数据储存在进行查询和处理的方式叫做离线

而我们正常使用的叫做在线

下面为AC代码

#include<bits/stdc++.h>
using namespace std;
#define int long long

const int N = 3e5+9;
int a[N],l[N],r[N];
stack<int> stk;
vector<int> X;
struct Q{
    int a,b;
}add[N],que[N];
int getidx(int x){
    //通过lower_bound 的二分查找第一个大于等于的的元素的迭代器
    //返回值范围为[1,X.size()]
    return lower_bound(X.begin(),X.end(),x)-X.begin()+1;
}
void solve(){
    //离散化
    int n,q;
    cin>>n>>q;
    for(int i = 1;i<=n;i++){
        int x,w;
        cin>>x>>w;
        X.push_back(x),X.push_back(x);
        add[i] = {x,w};
    }
    for(int i = 1;i<=q;i++){
        int l,r;cin>>l>>r;
        X.push_back(l),X.push_back(r);
        que[i] = {l,r};
    }
    //排序并进行去重操作
    sort(X.begin(),X.end());
    X.erase(unique(X.begin(),X.end()),X.end());
    for(int i = 1;i<=n;i++){
        int x,w;
        x = getidx(add[i].a);
        w = add[i].b;
        a[x] += w;
    }
    for(int i = 1;i<=X.size();i++) a[i] += a[i-1];
    for(int i = 1;i<=q;i++){
        int x,w;
        x = getidx(que[i].a);
        w = getidx(que[i].b);
//      auto [x,w] = {getidx(que[i].a),getidx(que[i].b)};
        cout<<a[w]-a[x-1]<<'\n';
    }
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int _ = 1;
    while(_--)solve();
    return 0;
}