Neovim-如何使用编辑器的神

保序离散化

保序离散化适合如下情况:

• 题目中的数值的范围过大, 例如在$[-10^9, 10^9]$这种, 但是出现次数比较少.

保序离散化是指将这些过大的数值映射到从0开始递增的自然数的过程.

模板代码:

#include <vector>
#include <algorithm>

/* 定义离散化数组 */
vector<int> alls;

/* 找到x对应的离散化后的数值 */
/* <= x的最大值 */
int find(int x)
{
  int l = 0, r = alls.size() - 1;
  while (l < r)
  {
    int mid = l + (r - l) / 2 + 1;
    if (alls[mid] > x) r = mid - 1;
    else l = mid;
  }
  /* 如果要映射到从0开始的, 就return r, 如果从1开始就return r+1 */
  return r;
}

int main()
{
  /* other code */

  /* 将需要离散化的数值全部放入alls中 */
  /* 排序 */
  sort(alls.begin(), alls.end());
  /* 去重 */
  alls.erase(unique(alls.begin(), alls.end()), alls.end());


  return 0;
}

区间和

https://www.acwing.com/problem/content/804/

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

using namespace std;

const int N = 100010 * 3;

typedef pair<int, int> PII;

int n, m;

vector<int> alls;
vector<PII> add;
vector<PII> query;
int a[N];

int find(int x)
{
    int l = 0, r = alls.size() - 1;
    while (l < r)
    {
        int mid = l + (r - l) / 2 + 1;
        if (alls[mid] > x) r = mid - 1;
        else l = mid;
    }
  /* 注意这个题是前缀和, 要从1开始映射 */
    return r + 1;
}

int main()
{
    cin >> n >> m;

    for (int i = 0; i < n; i ++)
    {
        int x, c;
        cin >> x >> c;
        add.push_back({x, c});
        alls.push_back(x);
    }

    for (int i = 0; i < m; i ++)
    {
        int l, r;
        cin >> l >> r;
        query.push_back({l, r});
        alls.push_back(l);
        alls.push_back(r);
    }

    sort(alls.begin(), alls.end());
    alls.erase(unique(alls.begin(), alls.end()), alls.end());

    for (auto item: add)
    {
        int x = item.first, c = item.second;
        a[find(x)] += c;
    }

    for (int i = 1; i <= alls.size(); i ++) a[i] += a[i - 1];


    for (auto item: query)
    {
        int l = item.first, r = item.second;
      /* 注意这里不是a[find(l-1)] */
        cout << (a[find(r)] - a[find(l) - 1]) << endl;
    }

    return 0;
}