算法日记11：SC63（离散化）

一、题目

在这里插入图片描述

二、题解

法一：前缀和（会炸）

对于这道题目，我们的第一个朴素想法就是用前缀和来进行简化操作，这个思路非常简单，就是前缀和的标准模板题，代码如下

void solve()
{int n,q;cin>>n>>q;while(n--){int i,x;cin>>i>>x;a[i]+=x;}//前缀和for(int i=1;i<=n;i++) a[i]+=a[i-1];while(q--){int l,r;cin>>l>>r;cout<<a[r]-a[l-1]<<'\n';}
}

法二：离散化

1、通过观察我们可以发现：数组的下标范围(1e9)>>操作数据点访问(n+2q==3e5)，也就是会造成大量下标浪费，因此我们可以想到把数据进行离散化

在这里插入图片描述

2、先对数据离线操作（先把操作存储起来，在进行了某些步骤之后再进行操作），

在这里插入图片描述

2.1具体步骤如下：（目的在于找出我们到底需要访问哪些点，并且把对原始点的操作–>对离散点的操作）

在这里插入图片描述

3、对样例操作如下：

3.1:找出需要操作的点

在这里插入图片描述

	int n,q;cin>>n>>q;for(int j=1;j<=n;j++)  //输入操作{int i,x;cin>>i>>x;X.push_back(i); //存入X用来查看有效点add[j]={i,x};   //存储操作点/值}for(int j=1;j<=q;j++)   //输入询问{int l,r;cin>>l>>r;X.push_back(l); //存入X用来查看有效点X.push_back(r);que[j]={l,r};}//排序去重sort(X.begin(),X.end());X.erase(unique(X.begin(),X.end()),X.end());

3.2：此时，数据（离散化）变成了：

在这里插入图片描述

3.3：此时把对原操作—>对离散操作(二分)，也就是把对原数组数据操作一一映射到对离散数组的操作

在这里插入图片描述

int FindIndex(int x)    //二分找第一个>=x的下标
{return lower_bound(X.begin(),X.end(),x)-X.begin()+1;
}for(int i=1;i<=n;i++)   //add映射到离散数组{int i_=FindIndex(add[i].a); //第i_个元素 + x_int x_=add[i].b;a[i_]+=x_;}for(int i=1;i<=X.size();i++) a[i]+=a[i-1];   //前缀和

3.4：同理，我们也把询问的操作映射到离散数组上，求解完毕！

在这里插入图片描述

for(int i=1;i<=n;i++)   //add映射到离散数组{int i_=FindIndex(add[i].a); //第i_个元素 + x_int x_=add[i].b;a[i_]+=x_;}for(int i=1;i<=X.size();i++) a[i]+=a[i-1];   //前缀和for(int i=1;i<=q;i++)   //que映射到离散数组{int l=FindIndex(que[i].a);int r=FindIndex(que[i].b);cout<<a[r]-a[l-1]<<'\n';}

三、完整代码如下：

#include<bits/stdc++.h>
using namespace std;typedef long long ll;
const int N=3e5+7;
int a[N];	//离散化数组
vector<int>X;   //有效点数组struct Q{  //存储加/询问操作int a;int b;
}add[N],que[N];int FindIndex(int x)    //二分找第一个>=x的下标
{return lower_bound(X.begin(),X.end(),x)-X.begin()+1;
}void solve()
{int n,q;cin>>n>>q;for(int j=1;j<=n;j++)  //输入操作{int i,x;cin>>i>>x;X.push_back(i); //存入X用来查看有效点add[j]={i,x};   //存储操作点/值}for(int j=1;j<=q;j++)   //输入询问{int l,r;cin>>l>>r;X.push_back(l); //存入X用来查看有效点X.push_back(r);que[j]={l,r};}//排序去重sort(X.begin(),X.end());X.erase(unique(X.begin(),X.end()),X.end());for(int i=1;i<=n;i++)   //add映射到离散数组{int i_=FindIndex(add[i].a); //第i_个元素 + x_int x_=add[i].b;a[i_]+=x_;}for(int i=1;i<=X.size();i++) a[i]+=a[i-1];   //前缀和for(int i=1;i<=q;i++)   //que映射到离散数组{int l=FindIndex(que[i].a);int r=FindIndex(que[i].b);cout<<a[r]-a[l-1]<<'\n';}
}int main()
{int _=1;while(_--) solve();return 0;
}