sort（区间排序）题解

· · 个人记录

题意简述：给定一个分好段且每一段长度都相同的数列，要求支持段内排序和查询前缀和。

朴素做法

按照题意模拟。排序操作时用 sort 进行排序，查询前缀和时直接从 1 到 x 累加。显然超时，预期得分：32 pts，实际可以卡到 60+ pts。

    cin >> n >> m >> len;
    for (int i = 1; i <= n; i++) scanf("%d", a + i);
    while (m--) {
        int op, x;
        cin >> op >> x;
        if (op == 1) 
            sort(a + 1 + (x - 1) * len, a + 1 + x * len);
        else {
            int ans = 0;
            for (int i = 1; i <= x; i++) ans += a[i];
            printf("%d\n", ans);
        }
    }

特殊性质 1

考虑只存在操作 2 的情况（即 9\sim 11 个数据点）。

没有排序，那么 O(n) 直接预处理出前缀和，然后 O(1) 查询。

特殊性质 2

考虑 len = 1 情况（即 12\sim 14 个数据点）。

既然 len = 1，那么每一个块的长度都是 1，那么每次排序必然也只有一个数排序。因此不用管排序操作，与特殊性质 1 一样前缀和乱搞即可。

无特殊性质

其实对于每一个 1 的操作，没有必要都排一次序，为什么呢？

比如有一个长度为 10 的数列，len = 2，那么这个数列可以分成 5 块。

现在假设有 5 个操作：

  1. 对第一块进行排序。
  2. 对第二块进行排序。
  3. 对第三块进行排序。
  4. 查询前 8 个数的和。
  5. 查询前 5 个数的和。

首先可以发现，第 8 个数字在第四块，那么我们其实可以直接预处理出前缀和，然后输出。因为即使前三块排了序，但是前三块只有 6 个数，这 6 个数一定还在数列的前 6 的位置。而我们需要求的是前 8 个数的和，这 8 个数一定包含前 6 个数字，所以直接输出前缀和，不需要进行处理。

再考虑第二个询问，查询前 5 个数的和。那么前五个数一定包含前四个数，即前四个数字之间不管怎么调换，都不影响结果。这个时候，我们只需要单独将第三个块排序，因为影响结果的只可能是第三个块。由于预处理了前缀和，所以前四个数可以 O(1) 求出。我们需要求出前 5 个数的和，那么还需要求出 5 - 4 = 1个数，即朴素求出第三个块的前 1 个数。

当然了，此做法会被卡：假如上面这个例子添加第 6 个操作，第 6 个操作也是查询前 5 个数的和。那么我们也对第 3 个块进行排序，但是显然这是不必要的，因为我们在操作 5 中已经将第 3 块排好了序。所以开一个桶，如果已经排过序了，就不用再次排序。然而很玄学的事情发生了，不加这个优化，跑得反而比加上优化更快

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1e6 + 10;

int n, m, len;
int a[N];
int f[N], s[N];

bool t[N];

int get(int x) {
    if (x % len == 0) return x / len;
    else return x / len + 1;
}

int main() {
    cin >> n >> m >> len;
    for (int i = 1; i <= n; i++) scanf("%d", a + i);
    int cnt = 0;
    for (int i = 1; i <= n / len; i++) 
        for (int j = 1; j <= len; j++) f[i] += a[++cnt];
    for (int i = 1; i <= n / len; i++) s[i] = s[i - 1] + f[i];//预处理出前缀和
    while (m--) {
        int op, x;
        cin >> op >> x;
        if (op == 1) t[x] = true;//标记第 x 断需要排序。显然，如果 t[x] 等于 0，那么第 x 断就不需要排序了
        else {
            if (x % len == 0) { 
                cout << s[x / len] << endl;
                continue;
            }
            int ans = s[x / len];//不需要排序的块的和
            int k = get(x); //判断第 k 个数是第几段
            if (t[k]) sort(a + 1 + (k - 1) * len, a + 1 + k * len), t[k] = false; //如果注释掉 t[k] = false，能跑得更快，离谱
            for (int i = (k - 1) * len + 1; i <= x; i++) ans += a[i];//暴力求出新排序的块的和
            printf("%d\n", ans);
        }
    }
    return 0;
}