奇怪的矩阵题解

经验分享区
1

奇怪的矩阵题解

题目描述

小 Y 手中有一个 n \times 10^{18}
的矩阵，虽然说这个矩阵实在是太大了，但是也并非毫无规律可循。小 Y 将给出这个矩阵第一列的 n 个元素，用 $a_i$表示第 i 行第一列的元素值。对于其他的位置，第 i 行第 j 列的元素值为 a_i + j - 1。现在小 Y 需要知道一些这个矩阵的信息，他会向你提问，在矩阵第 l 列到第 r 列的所有元素中，包含几个不同的值？

100pts做法

首先我们约定几个数:

  1. d = R - L + 1
  2. g(i) = a_i - a_{i - 1}

我们简单思索可以得到：当 d \le g(i) 时，说明了两者差距很大，差距无法通过 d 的增大来弥补，此时区间内没有重复的数。

当 d > g(i) 时，说明区间内出现了重复，无法全部都取到。

综上我们可以得到 ans = d + \sum_{2}^{n} \min{d, g(i)}
（与区间的位置无关之和间隔有关）

对于 g(i) \ge d 统一取 d

对于 g(i) < d 对 g(i) 排序做前缀和

附上代码：

 while (q--)
    {
        LL l, r;
        cin >> l >> r;

        if (n == 0)
        {
            cout << 0 << ' ';
            continue;
        }

        LL a_min = a[0], a_max = a.back();
        LL min_s = a_min + l - 1;
        LL max_e = a_max + r - 1;

        LL to = max_e - min_s + 1;
        if (to < 0)
        {
            cout << 0 << ' ';
            continue;
        }

        LL t = r - l + 1;
        LL k = l - r - 1;

        LL sum = 0;
        if (!d.empty())
        {
            auto pos = lower_bound(d.begin(), d.end(), t) - d.begin();
            int cnt = d.size() - pos;
            LL sum_d = (pos > 0 ? pre_sum.back() - pre_sum[pos - 1] : pre_sum.back());
            sum = sum_d + k * cnt;
        }

        LL ans = to - sum;
        if (ans < 0)
            ans = 0;
        cout << ans << ' ';
    }
    cout << endl;
1 个赞