区间数据离散化

2022/4/27 数据离散化区间操作二分

区间区间又是区间…

对于一类范围很大，而实际用到的范围又很小的题目，如下题，数轴上的范围2*10^9次，而实际上有操作过的个数最多有n个，如果用前缀和计算该题的话在数据小的情况下是可以做的，但是本题范围若有前缀和的话遍历加每一个值也必然会tle，这时候我们就用到了离散化这个方法

**AcWing 802. 区间和 **

假定有一个无限长的数轴，数轴上每个坐标上的数都是 0。

现在，我们首先进行 n 次操作，每次操作将某一位置 x 上的数加 c。

接下来，进行 m 次询问，每个询问包含两个整数 l 和 r，你需要求出在区间 [l,r] 之间的所有数的和。

输入格式

第一行包含两个整数 n 和 m。

接下来 n 行，每行包含两个整数 x 和 c。

再接下来 m 行，每行包含两个整数 l 和 r。

输出格式

共 m 行，每行输出一个询问中所求的区间内数字和。

数据范围

−10^9≤x≤10^9
1≤n,m≤10^5
−10^9≤l≤r≤10^9
−10000≤c≤10000

输入样例：

输出样例：

8
0
5

题解：

把需要操作的位置都放到 all 数组里，对于操作的数据我们放在 add 内，对于要查询的区间我们放在 query 内，此外我们定义一个 find（x）函数来查找数值为x的值在 all 数组内的下标，在放完所有数据之后，我们要对 all 数组内的值整理一次，先用sort使数据有序排列，这样才能保证在用find查找下标的时候有效进行，然后还得对 all 数组内相同的数据进行清除，然后遍历 add 内的值，给a数组进行赋值，再对all遍历计算有效前缀和，最后遍历query输出答案

例如:
 
在最以下数据进行操作之后
   1 2
   3 6
   7 5
 
   1 3
   4 6
   7 8
 
读取数据之后各vector的内容
 
   add{{1,2},{3,6},{7,5}}
 
   query{{1,3},{4,6},{7,8}}
 
   all{1,3,7,1,3,4,6,7,8}
 
对all排序去重之后为
   
   all{1,3,4,6,7,8}   //即在数轴上就用到了这些位置
   
   先遍历add对a数组进行操作后
 
    a {2， 6 ，0， 0 ， 5 ，0 }
   
   然后用sum计算a内的前缀和
   
   sum{2 , 8 , 8 , 8 , 13, 13 }   
   
   然后遍历query内的值，对sum中的范围进行求差（得用find查找all中下标）
   
   而对应的sum下标和值即为
 
        0   1   2   3   4   5
   sum {2 , 8 , 8 , 8 , 13, 13 } 
    all{1,  3,  4,  6,   7,  8 }  
   所以对以下三个区间
      1 3
      4 6
      7 8
   三个用find查找的下标区间为
      0 1
      2 3
      4 5
   计算得出答案

代码呈上😉😉😉😉

#include <bits/stdc++.h>
#define repp(i,n,m) for(int i=n;i<=m;++i)
#define reps(i,n,m) for(int i=n;i>=m;--i)
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N=300010;
int a[N],sum[N];
vector<PII> add,query;
vector<int>all;
int find(int x){    //离散化查找下标
 int l=0,r=all.size()-1;
 while(l<r){
     int mid=l+r>>1;
     if(all[mid]>=x)r=mid;
     else l=mid+1;
 }
 return r+1;
}
int main()
{
 ios::sync_with_stdio(0);cin.tie(0);
 int n,m;cin>>n>>m;
 repp(i,1,n){        //数据读入
     int x,y;cin>>x>>y;
     add.push_back({x,y});
     all.push_back(x);
 }
 repp(i,1,m){
     int x,y;cin>>x>>y;
     query.push_back({x,y});
     all.push_back(x);
     all.push_back(y);
 }
 
 sort(all.begin(),all.end());        //排序+去重
 all.erase(unique(all.begin(),all.end()),all.end());
 
 for(auto it:add){        //赋值操作
     int x=find(it.first);
     a[x]+=it.second;
 } 
 
 repp(i,1,all.size()) sum[i]=sum[i-1]+a[i];   //前缀和计算
 
 for(auto it : query) {                       //区间和
     int l=find(it.first),r=find(it.second);
     cout<<sum[r]-sum[l-1]<<endl;
 }
 return 0;
}

LOADING

区间数据离散化