算法日记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;
}